Information-Theoretic Analysis of Unsupervised Domain Adaptation
Authors: Ziqiao Wang
Yongyi Mao
Venue: ICLR 2023 poster (2023)
Keywords: unsupervised domain adaptation
generalization
information theory
regularization

Abstract: This paper uses information-theoretic tools to analyze the generalization error in unsupervised domain adaptation (UDA). We present novel upper bounds for two notions of generalization errors. The first notion measures the gap between the population risk in the target domain and that in the source domain, and the second measures the gap between the population risk in the target domain and the empirical risk in the source domain. While our bounds for the first kind of error are in line with the traditional analysis and give similar insights, our bounds on the second kind of error are algorithm-dependent, which also provide insights into algorithm designs. Specifically, we present two simple techniques for improving generalization in UDA and validate them experimentally.

Published as a conference paper at ICLR 2023
INFORMATION- ANALYSIS OF UNSUPER- VISED DOMAIN ADAPTATION
Ziqiao Wang & Yongyi Mao
University of Ottawa
(zwang286, ymao @euottwwa.c..o
ABSTRACT
This paper uses information-theown tools to analyze the generalization error in unsupervised domain adaptation (UDA). We present novel upper bounds for two notions of generalization errors. The first notion measures the gap between the population risk in the target domain and that in the source domain, and the sec- ond measures the gap between the population risk in the target domain and the empirical risk in the source domain. While bounds for the first kind of error are in line with the traditional analysis and give similar insights, our bounds on the second kind of error are aggoritmm-depender algorithm designs. Specifically, we present two simple techniques for improving generalization in UDA and validate them experimentally.
which also provide insights into
INTRODUCTION
This paper focuses the unsupervised domain adaptation (UDA) task, where the learner is con- fronted with a source domain and a target domain and the algorithm is allowed to access to a labeled training sample from the source domain and unlabeled training sample from the target domain. The goal is to find predictor that performs well on the target domain.
A main obstacle in such task is the discrepancy between the two domains. Some recent works (Ben-David et al., 2006; 2010; Mansour et al., 2009; Zhao et al., 2019; Zhang et al., 2019; Shen al., 2018; Germain al., 2020; Acuna et al., 2021; Nguyen et al., 2022) have proposed various measures to quantify such discrepancy, either for the UDA setting or for the more general domain generalization tasks, and many learning algorithms are proposed. For example, Nguyen et (2022) uses a (reverse) KL divergence to measure the misalignment of the two domain distributions, and motivated by their generalization bound, they design an algorithm that penalizes the KL divergence between the marginal distributions of two domains in the representation space. Despite that this "KL guided domain adaptation" algorithm is demonstrated to outperform many existing marginal align- ment algorithms (Ganin et al., 2016; Sun & Saenko, 2016; Shen et al., 2018: Li et al., 2018), it is not clear whether KL-based alignment of marginal distributions is adequate for UDA, and more funda- mentally, what role the unlabelled target-domain sample should play in cross cross-domain generalization. Notably, most UDA algorithms are heuristically designed and intuitively justified. Moreover, most existing generalization bounds are Segortthm-independee both deeper theoretical understanding and more principled algorithm design.
Then there appears significant room for
In this paper, we analyze the generalization ability of hypotheses and learning algorithms for UDA tasks using an information-theoreiie framework developed in (Russo & Zou, 2016; Xu & Raginsky, 2017). The foundation of our technique the Donsker-Varadhall Varadhan representation of KL divergence (see Lemma I) We present novel upper bounds for two notions of generalization errors. The first notion ("population-to- popopulltin (PP) generalization error") measures the gap between the popu- lation risk in the target domain and that in the source domain for a hypothesis, and the second ("ex- pected pappirical-t-populaatee risk in the target domain and the empirical risk in the source domain for learning algorithm. We show that the PP generalization error for all hypotheses are uniformly bounded by a quantity gov- erned by the KL divergence between the two domain distributions, which. under bounded losses, recovers the the bound in Nguyen et al. (2022). We then show that this KL term upper-bounds some other measures including Total- Variation distance (Ben-Davie et al., 2006), Wasserstein dis-
(EP) generalization error") measures the gap between the population

---

Published as a conference paper at ICLR 2023
tance (Shen et al., 2018) and domain disagreement (Germain et al., 2020). Thus, minimizing KL- divergence forces the minimization of other discrepancy measures as well. This, together with the ease of minimizing KL (Nguyen et (al.) explains the effectiveness of the KL-guided alignment approach. For expected EP generalization error, we develop several algorithm-dependee ization bounds. These Iggorithm-dependen bounds further inspire the design of two new and yet simple strategies that can further boost the performance of the KL guided marginal alignment algo- rithms, Experiments are performed to verify the effectiveness of these strategies.
general-
RELATED WORK
Domain Adaptation Many domain adaptation generalization bounds have been developed (Ben- David et al., 2006; 2010: David et al., 2010; Mansour et al., 2009; Shen et al., 2018; Zhang al., 2019; Germain et al., 2020; Acuna et al., 2021), and various discrepancy measures are introduced to derive these bounds including total variation (Ben-David et al., 2006; 2010; David et al., 2010; Man- sour et al., 2009), Wasserstein distance (Shen et al., 2018), 1)), domain disagreement (Germain et al., 2020) and so on. In particular, bounds based on H.H. in Ben-David et al. (2010) are restricted to a binary classification setting and assume a deterministic labeling function. Furthermore, Ben-David et al. (2010) also assumes the loss the I,2 distance between the predicted label and true label (which is bounded). Our bounds work for the general supervised learning problems with any labelling mechanism (e.g., stochastic labelling), and we do not require the specific choice of the loss (even un- bounded). Recently, Shui et al. (2020) proposed generalization bounds using Jensen-Shanme divergence, which bear a relation to our Corollary 4.2. While other georrthm--deenden bounds have been proposed for different transfer learning settings (e.g., Wang et al. (2019)), they not directly comparable to our own bounds. For more details about the domain adaptation theory, we refer readers Redko al. (2020) for comprehensive survey. In addition, the most common meth- ods for domain adaptation involve aligning the marginal distributions of the representations hetween the source and target domains, for example, using an adversarial training mechanism (Ganin al., 2016 6 Shen et al., 2018; 8; Acuna et al., 2021) or aligning the first two moments of the representation distribution (Sun & Saenko, 2016). There are numerous other domain adaptation algorithms, and we refer readers to (Wilson& & Cook, 2020; Zhou et al., 2021; Wang et al., 2021 for recent advances.
(JS)
Information-Theored Generalization Bounds Information-theoreee bound the expected generalization error of supervised learning, where the training and testing data come from the same distribution (Russo & Zou, 2016; 2019; Xu & Raginsky. 2017; 7; Bu et al., 2019; Negrea et al., 2019; Steinke & Zakynthinou, 2020; Rodríguez Gálvez et al., 2021). Exploiting the chain rule of mutual information, these bounds are successfully applied to characterize the gener- alization ability of stochastic gradient based optimization algorithms (Pensia al., 2018; Negrea et al., 2019; Haghifam et al., 2020; Wang et al., 2021a; Neu et al., 2021; Wang & Mao, 2022a;b). Recently, this framework has also been used in other learning settings including meta-learning (Jose & Simeone, 2021a; Jose et al., 2021; Rezazadeh et al., 2021; Chen et al., 2021), semi- sumissuper learning (He al., 2021; Aminian al., 2022) and transfer learning (Wu al., 2020: Jose & Sime- one, 2021a;b; Masiha et al., 2021; Bu et al., 2022). In particular, (Wu et al., 2020; Jose & Simeone, 202 consider a different problem setup with ours. Specifically, their expected generalization er- ror is the gap between the target population risk and a weighted empirical risk combining both the source and the target empirical risks, while our "EP" error is the gap between the target population risk and the source empirical risk. That is, we focus the role of the unlabelled target data in cross-domain generalization when the source empirical risk is taken as a training objective, whereas their works assume the existence of labelled target data and study their role in domain adaptation.
analysis is usually used to
3 PRELIMINARY
Unless otherwise noted, a random variable will be denoted by a capitalized letter, and its realization is denoted by the corresponding lower-case letter. Consider a prediction task with instance space
2 = X' x y, where X and y are the input space and the label (or output) space, respectively. Let F be the hypothesis space of interest, in which each f E F is function predictor mapping X' to D. We assume that each hypothesis f E F is parameterized by some weight parameter w in some space W and may write f as fw as needed.
2

---

Published as a conference paper at ICLR 2023
Let j and ye' be two distributions 2, unknown to the learner, where μ characterizes the source domain and j' characterizes the target domain. We may also write μ as P2 or Pxy and μ as Pz Pxiy', which defines random variables Z = (X, Y) and Z' (X', , Y"), respectively. Let y be labeled source-domain sample and 5x
S (2, unlabelled target-domain sample. The objective UDA is to design an algorithm that takes and S'x' the input and outputs weight W W, giving rise predictor fw E F that "works well" on the target domain. Note that the algorithm A is characterized by a conditional distribution PwIs.S'x'
Px be an
Let f: v: x x - Ri be a loss function. The population risk for each w E W in the target domain defined as
(w) Ez' ((n(oo(')) Y')
and good UDA algorithm hopes to return a weight w that minimizes this risk. Since pl is unknown, one often uses recourse to the empirical risk in the source domain, defined as
(s(w) & 1 Σ (X.))..
Generalization error in this setting measures how well the hypothesis returned from the algorithm generalizes from the source-domain training sample to the target-domain unknown distribution μ². Taking into account the stochastic nature of the algorithm A, natural notion of generalization error for UDA can defined by
Err - TEw.s (R, Rs(W)) E.sss,, (R) Rs(W)),
where the expectation in the first expression is taken over the joint distribution of (W.S) Pwis x , and the expectation of the second expression is taken over the joint distribution of (W,S, S.x)) ~ Pw s. x p g P
There is another notion of generalization error, more traditional in the domain adaptation literature, defined as the gap between the population risk in the target domain and that in the source domain:
Err(w) Ry (w) R.(w).
where (w) A Rz[e(S (X), Y)). apparent that Err(w) and Err are related by the following triangle inequality: R (w) Rs(w) I (w) - (w + (w) Rs(w)).
where the second term the right hand side is the standard generalization error in the source domain, which can be bounded by classical learning-theoretic tools, e.g., Rademacher complexity (Bartlett & Mendelson, 2002). Thus, bounding Frr(w) helps bounding Err.
This paper studies both notions of generalization error for UDA. Specifically, starting from Sec- tion 5, we will mainly use iiformation-thhoreed tools to bound Err directly, without going through Err(w). For the ease of reference, alization error for w and Err as the expected empiricaltto-pppulatioo (EP) generalization error.
refer to Err(w) the popalation-tto-populaiii (PP) gener-
The following definitions are useful.
Definition 3.1 (Disintegrated Mutual Information). Let X, Y and Z be random variables and be a realization of Z. The disintegrated mutual information of X and Y given Z = is (=(X 2
DKL (Px, z= xy|
Note that the conditional mutual information T(X;Y|Z) 12
Definition 3.2 (Lautum Information (Palomar & Verdú, 2008)). The lautum information between X and Y is defined as L(X;Y) A (PxPr]
4 UPPER BOUNDS FOR PP GENERALIZATION ERROR
We now present some upper bounds for Err(w). The key techniques used in developing these bounds the information-theoretie tools in the style of Lemma A.1. These bounds adopt certain
3

---

Published as a conference paper at ICLR 2023
KL divergence to measure the discrepancy between the source and target domains. Notably, some previously established bounds are recovered under weaker conditions. Additionally, we demonstrate that under certain conditions, the KL-based bound is an upper bound of several other discrepancy measures and hence minimizing the KI. divergence forces the minimization of these other measures.
We first list some common assumptions on the loss function, which we consider in this paper. Assumption (Boundedness), ((.,)) is bounded in [0,M]
Assumption (Subgaussianity). (X), Y) is R-subgaussian' under ja for any W.
Remark 4.1. Note that Assumption implies Assumption 2, i.e., if (Xf Y) is bounded in [0, M then it is also M/ // ////uubbaussiin Thus, Assumption 2 is weaker than Assumption 1.
Assumption& (Lipschitzness)) ((fooX)) is 3-Lipschitz continuous in 2 with respect to a metric d on 2 for any E W, ie., (e(f (x1). (x(f((z)): V1) {(fw( S Bd(zz, ; 22) for some metric d on Z. Remark 4.2. Note that Assumption I implies Assumption 3 when d(21,2)) = 121t22 i.e, if is bounded in [0, M. then it is also M-Lipschitz under the discrete metric.
Y) (X), Assumption 4 (Triangle and Symmetrie). E((5-) satisfies the following: f(y1, = E(y2, vi and Egy1. y2) S E(y1 Ma) Eygs y2) for any y1 92: y3 Ey.
4.1 GENERALIZATION BOUNDS VIA THE SUBGAUSSIAN CONDITION
The following generalization bound is established by combining Lemma A.1 and Assumption 2, and its corresponding sample complexity bound discussed in Appendix B.8.
Theorem 4.1. If Assumption holds, then for any W, Err(w) 22RDDL (p' Ip).
Notably this result can be turned into generalization upper bound providing guidance to algorithm design, and at the same time it provides lower bound of the generalization error, highlighting some fundamental difficulty of the learning task. To illustrate this, we present a corollary while noting that similar development can also be applied to other bounds presented later in this paper.
Consider that each fw is expressed as the composition g o h, where to representation space T and g is function mapping TT to y. For any given h X - T, denote by μlh the distribution on T x y obtained by pushing forward via h, that is, μun (t, y) 8(t (((=))dp(z y), where ó is the Dirac measure on T. Similarly, let μh denote the distribution on T x y obtained by pushing forward μ via h.
a function mapping X
Corollary 4.1. Suppose that fw g ool. h and that Assumption 2 holds, then for any W.
Ra(w) - DR2 & (w) S Rg(ww) + 2R (P)))))).
In this result, the lower bound of Ry (w) indicates fundamental difficulty in UDA learning in that, using the same predictor mapping far there is no way for the population risk in the target domain to be lower than that of the source domain less than a constant which depends only on the domain difference. On the other hand, the upper bound suggests that it is possible to squeeze the gap between the two population risks by choosing an appropriate representation map h evidently such a map should be attempting to align p41 with μ4 or to align their respective proxies.
It is also noteworthy that under Assumption and due to Remark 4.1, Theorem 4.1 implies
Err(w)] < V2 (KI.(Px: Px) + DKL. DRL. (Pyi || PY]x).
/
M
(3)
Similarly applying this result in the representation space T, we see that Eq. (3) recovers the bound in Proposition 1 of Nguyen al. (2022). Notice that unlike Nguyen al. (2022), Theorem 4.1 ( (or Eq. (3)) does not require the loss to be the cross-entropy loss.
Theorem 4.1 and Nguyen et al. (2022) both the KL divergence from source domain to target domain, D Ilp), and in fact, Err(w) can also be upper bounded by DKL (All))))) This can (rather than (X), Y)); for bounded loss, the subgaussianality of (X'), Y') is also satisfied. Then we obtain the following corollary.
be done by invoking the subgaussianality of (X'),, Y')
(X'),")))
random variable X is R-subgaussian if for any p. log Rexp (x EX)) S R² R2/2. /2.
4

---

Published as a conference paper at ICLR 2023
Corollary 4.2. If Assumption 1 holds,
Err( w)
min (DL (ulla"), DKL (1
M (DKlllll)) + DKL(H()lp)
2 Remark 4.3. In the second inequality of Corollary 4.2. DKL(Hl)u() + DKL(H') (A) is known as the symmetrized KL divergence,
Jeffrey's divergence (Jeffreys, 1946), and in fact, Nguyen et al. (2022) penalizes this measure between the source and target distributions in the representation space. Notice that bounds in Shui et al. (2020) are based the JS divergence. Since there is sharp upper bound of the JS divergence based on Jeffrey's 's divergence (Crooks, 2008), minimizing Jeffrey's 's divergence (in the representation space) will simultaneously penalize the JS divergence.
In UDA, since Y' is completely unavailable to the algorithm A, it is impossible to minimize the misalignment of conditional distributions, i.e. (I where T and T are represen- tations of source domain and target domain, respectively. A common method is to assign pseudo labels to target data based on a learned source classifier (Liang et al., 2020). However, it may also cause additional issues (Shen et al.. 2022). For concreteness, suppose the trained model Q can well approximate the real mapping between and Y on source domain (i.e. QYT Pr(r), which is usually the training objective. Let Y be the pseudo label of 7 generated by the trained model, i.e.. Qrir = QyIr. Let Qr Pr. Pr.QTIT then the following holds,
Pr Pr.. = DKI. + DRL. 11pp(1)11p))(0)))pp))) (4)
DRL. (eT = Pr log
Pry Pry
For specific t¹, if P(Y'= = 3/'' =t) 0 and Q("'=''''''"" = =1) = O, then the second term in RHS of Eq. (4), DKL (PL(pr1r1111 (()
co. In this case, even when the marginal distributions are perfectly aligned, the overall value of the upper bound is large. Thus, incorrect pseudo labels may even have negative impact on the target domain performance.
In fact, the misalignment of the conditional distributions appears to be the main difficulty of UDA (Ben-David et al., 2006; Acuna et al., 2021). The next corollary suggests that this difficulty may be alleviated when the loss function satisfies the triangle property, namely, Assumption 4. It can be verified that this assumption is satisfied by the 0-1 loss 2; this assumption has also been considered in previous works (Mansour et al., 2009; Shen et al., 2018).
Theorem 4.2. If Assumption 4 holds and let E( (X), (x)( be R-subgaussian for any w, w' E W. Then for any w, Err(w)= S /2R=DKL (Pxx + where X min Ry
(w) (w)+ + R2 (w).
Here X measures the possibility of whether the domain adaptation algorithm will succeed under the oracle knowledge of μ and p'. In particular, the hypothesis space is large enough, the minimizer w for the "joint population risk" R (w) + Ry (w) may give rise to (w=) then we're likely to generalize well on the target domain. Then the KI. divergence DKL. (Px [Px)
Ry((")) = O,
between the two Am-marginals alone bounds the PP generalization error uniformly for all w E W.
This theorem motivates the strategy of penalizing DKL (Pr (|r) in the representation space for UDA. The next theorem suggests that such an approach also penalizes other notions of domain dis- crepancy, for example, the key quantity in the PAC-Bayes type of domain adaptation generalization bounds (Germain et al., 2020), that is defined as
(ix, Px.) A |Ew:w [Exx [([[w(X') fw: (X[,, Ew,w, [Ex [e(Jw(X) Jw [X (5)
Theorem 4.3. If (( (X)) is R-subgaussian for any fwo fa E F, then dis(Px,PX) < 22RLDKL (Px:
Note that unlike Germain et al. (2020), here we do not require the loss function to be the 0-1 loss.
4.2 GENERALIZATION BOUNDS VIA THE LIPSCHITZ CONDITION
We now present such generalization bound for UDA under the Lipschitz continuity assumption of the loss function, where W(..) denotes the Wasserstein distance.
Theorem 4.4. If Assumption 3 holds, then Err(w) S (p',
Some losses that only satisfy general version of Assumption 4 are discussed in Appendix B.10
5

---

Published as a conference paper at ICLR 2023
Theorem 4.4 can be related the KL-based bounds in the previous section when the Wasserstein distance is defined with respect to the discrete metric d. In this case and under bounded loss function, which is also Liptschitz continuous, Theorem 4.4 follows. On the other hand, Wasserstein distance also equivalent to the total variation in this case, while the latter is connected to the KI. diver- gence via Pinsker's inequality (Polyanskiy & Wu, 2019, Theorem 6.5) and the Bretagnolle-Huber inequality (Bretagnolle & Huber, 1979, Lemma 2.1). Thus, we arrive at the following result. Corollary 4.3. If Assumption holds holds and let d be the discrete metric, then
Brr(w) s MTVV 14) s MV Mymnn min (Kl(llll))) E--e--
Note that results here are inspired by the work of Rodríguez Gálvez al. (2021). Corollary 4.3 provides a tighter bound than the one in Eq. (3), as can be directly verified.
Parallel to Theorem 4.2, if the loss function satisfies the triangle property, may establish the bound below, which recovers a similar result in (Shen et al., 2018, Theorem 1.) but without restrict- ing the task be binary classification or requiring the loss to be the L1 distance.
any fwr (X)) is 3-Lipschitz in X for any w, w' E W, Theorem 4.5. If Assumption 4 holds and (X), then for any w E W, Err(w) S (W Px) + X", where X = min Ry + R (w))
These results justify the strategy of minimizing domain discrepancy in the representation space. Since the KL-based bounds upper-bound those based on other measures of domain differences, pe- nalizing the KL divergence will also penalize those other measures. This is practically advantageous since it is usually easier and more stable to minimize the KI. divergence (Nguyen et al., 2022).
UPPER BOUNDS FOR EP GENERALIZATION ERROR AND APPLICATIONS
There limitations in the bounds the PP generalization error developed far and in the tra- ditional analysis of UDA. First, such bounds are independent of w and hence algorithm-independemt Second, although these bounds may inspire strategies exploit the unlabelled target sample, e.g., aligning the source and target distributions in the representation space, they only provide very lim- ited knowledge on the role that the unlabelled target sample plays. Inspired by the works of Negrea et al. (2019) and Rodríguez-Gáil Gálvez et al. (2021), we derive upper bounds for the EP generalization error that take better advantage the dependence of the algorithm's 'ss output on the unlabelled target data. Applications of these bounds in designing the learning al algorithms are also presented.
5.1 EP GENERALIZATION BOUNDS
Theorem 5.1. Assume E(fw (X'), Y') is R-subgaussian under Pw.Z for any a'y E X, then
Err| < num 3=1==1
Ex, (W; 2.) (W V2RDDKu((H1lT))
Remark 5.1. It is worth noting that the unlabelled target data contributes to the first term of the bound. Increasing the amount of source and target data will result in reduction of the first term in the bound. Specifically, moving the expectation inside the square root function by Jensen's 's inequality and since Zi 1L X3. the equations L(W; Zx)X I(W; Z,lX,) + 1(Z; (f) 1(W; ; Zi) + I(X;; W)) hold by the chain rule. The term I(W; Z4) will vanish as n + oo and the term I(X;; WW) will also vanish as n, m + Do.
The theorem can be turned into a version that is more practically relevant, in which the KL term is replaced with their representation-spacc counter- part (following similar argument used for deriving Corollary 1). In addition, note that although larger sample sizes allow better estimation that KI. term, utilizing pseudo-labels for estimation may have negative impact (as discussed in Section 4), which can be amplified by the larger sample size.
Corollary 5.1. Let Assumption I hold. Then
|Erl| < 22m
M
ΣΣ
m
a
Ex3 V min ( 21), ( V2
M
/min (DKL(ulu")) DKL (k(()()))

---

Published as a conference paper at ICLR 2023
Theorem 5.2. Assume E is Lipschitz,fo both w W and Z, i... (ff( (((((()'' (d1 2 for all 2, E Z and [z( y) - ((fwr( y) _ (w, w') for all w, w E W. then
B
Er
Ex Ex W W( Pwix;; + (H p').
Y27
This bound is tighter than the bound in Theorem 5.1, as can be indicated by the following corollary. Corollary 5.2. Let Assumption 1 hold. Then
Err
M
E Ex
(V(PWIZ.x;,PPIxx)) + MTV(H,)))
Tem
j=1 i=1
M
DRL Dxu(Pi1z.,;(IPPMxx) + V (KI(H))e))
M2
Ex,
mm
Notice that to recover Theorem 5.1 from Corollary 5.2 (under Assumption 1), we can use Jensen's inequality move the expectation over Z; inside the square root function.
5.2 GRADIENT PENALTY AS AN UNIVERSAL REGULARIZER
The the disintegrated mutual information X (W: Z,). In the stochastic gradient based optimization algorithms, this term can be controlled by penalizing the gradient norm. To see this, we now consider "noisy" iterative algorithm for updating W, e.g., SGLD. At each time step t, let the labelled mini-batch from the source domain be BB let the unlabelled mini-batch from the target domain be X',,, and let g(W,,1, ZB, X (B,) be the gradient at time t. Thus, the updating rule of W is W, W - Mgg(W, ZB Bb) N2 where T, is the learning rate and N₂ (O, o²Ia) an isotropic Gaussian noise. Inspired by Pensia et al. (2018), we have the following bound.
bound in Theorem 5.1 tells us that one can reduce the EP error by limiting
Theorem 5.3. Let the total iteration number T and let G. gW,,1, ZB, X's,) then
R
T
W [[G,-- EZz, [GJ]I|] + /2R2DKI(AAllP)) oi
Th o Es
Err <
Remark 5.2. Considering a noisy iterative algorithm here is merely for simplifying analysis. In fact, it is also possible analyze the original iterative gradient optimization method without noise injected. For example, one can follow the same development in (Neu et al., 2021; Wang & Mao, 2022a) analyze vanilla SGD. In that case, there will be some residual terms in the bound.
Theorem 5.3 hints that to reduce the generalization error, one can simply restrict the gradient norm at each step (so that (G,-EZz, [G.]]² is reduced). This strategy will also restrict the distance between the final output Wt and the initialization Wn. effectively shrinking the hypothesis space accessible by the algorithm. We also note that the importance of gradient penalty has been theoretically justified in the supervised learning setting (Negrea et al., 2019; Haghifam et al., 2020; Smith et al., 2021; Rodríguez-Gaie Gälvez et al., 2021: Neu et al., 2021: Wang Mao, 2022a:b).
Indeed, adding gradient penalty can be applied to any existing UDA algorithm and it is simple but effective in practice. Later on we will show that even when the algorithm A does not access to any target data, in which case IWW; Xx)) reduces to I(W; Z+) and g(W, ZB. X²e becomes g(W.11 BB,), ). minimizing the empirical loss of source domain sample while penalizing gradient norm will still improve the performance. Notice that gradient penalty has been used in standard supervised learning as a regularization technique (Geiping al., 2022; Jastrzebski et al.. 2021). It is also used in Wasserstein distance based adversarial adaptation (Gulrajani et al., 2017: Shen et al., 2018), and their motivation is to stabilize the training to avoid gradient vanishing problem. Here we suggest, with strong theoretical justification, that gradient penalty is a universal technique for improving the generalization performance in UDA for any gradient- based learning method.
Notably the bound in Theorem 5.3 only depends on the size n of labelled source sample and does not explicitly depend on m, the size of unlabelled target sample. With more careful design, if we
7

---

Published as a conference paper at ICLR 2023
consider the mutual information as the expected KL divergence of posterior and prior, based on 1 (W; Z4) in Theorem 5.1, it possible to create a larged-data-deeeedeet prior and derive tighter bound based on some quantity similar to "gradient incoherence" in Negrea et al. (2019).
5.3 CONTROLLING LABEL INFORMATION FOR KL GUIDED MARGINAL ALIGNMENT
Consider instances in the representation space, (T,Y) and Z' = (T", Y). Theorem 5.1 also encourages us to align the distributions of two domains in the representation space, argued ear- lier. Then the KI. guided marginal alignment algorithm proposed in Nguyen et (2022) can be invoked here. One may notice that Theorem 5.1 uses DKL (ull)e') while Nguyen et al. (2022) uses DKL (Kl(llluu) As already discussed in Section 4, this inconsistency can be ignored when the loss is bounded (see Corollary 5.1).
Most domain adaptation algorithms aim to align the marginal distributions of two domains in the representation space. However, without accessing to Y', it remains unknown if an UDA algorithm will work well since we cannot guarantee that discrepancy between conditional distribution Pyir and Py won't become too large when we align the marginals. In Nguyen et al. (2022), the authors show that D (P can be upper- bounded by ( (PPrpxx/lPPyyx// [y]x), ( IXX;; (T;Y). The authors then argue that penalizing the KI. divergence of the marginals is safe.
We now argue that in practice the condition Y( I(T; Y) can be difficult to satisfy the cross-entropy loss is used to define the source-domain empirical risk.
By data processing inequality on - T, we know that ((;Y) 2 I():Y) Thus, to let I(T; reach its maximum, one must minimize H(Y[T). On the other hand, let Qylr,w be the predictive distribution of labels in the source domain generated by the classifier. The expected cross-entropy loss for each Zi in the representation space is then
Ew,z, [((fw(I) Yi) Ez, [Ew 2, [-log Qy.T..w]]
which also decomposes as (Achille & Soatto, 2018; Harutyunyan et al., 2020)
Z. [((fw YJ] = (Y[))))+ + Ey.w [DKL (P (fr..r,,.www
Y(T.). (6)
Then minimizing the expected cross-entropy loss may not adequately reduce (Y, but rather cause I(W; Y/(T:) to significantly increase. particularly when the model capacity is large. This may have two negative effects. First, the condition [(X; Y) I(T; Y) is significantly violated, and Hence, aligning the two
DRL. DRI (Pyr)) is no longer upper bounded by DKL. (Pyixx marginals alone may not be adequate. Second, large / (W; Y.(T;) indicates W just simply memorizes the label Y, resulting form of overfitting and hurting the generalization performance.
The key take-away from the above analysis is that when aligning the marginals in UDA, controlling the source label information in the weights can be important to achieve good cross-domain gen- eralization. A similar message can also be deduced from Theorem 5.1, when it is viewed in the representation space and noting (T) (W; 2,) IT) (W; + 1 (W; (())).
To control label information, Harutyumyan et al. (2020) proposed an approach called LIMIT. How- ever, this method is rather complicated and arguably hard to train in domain adaptation (see Ap- pendix C.8). We now derive a simple alternative strategy for this purpose.
Notice that I (W: YT): s infq Er, DKL (PWI........Tyy ((Q which is simple ex- tension of variational representation of mutual information (Polyanskiy & Wu, 2019, Corollary 3.1.). Here Q could be any distribution. By assuming N(W, Ia, T,, Tÿ (4) and taking Q N(W, LaIalTi, T3- 1)), we have
(W; V.T.) < inf Fr; Q
x I 2
Thus, we may create an auxiliary classifier fa that is not allowed access to the real source label Y. In each iteration, we use the pseudo labels of target data (and source data) assigned by fa to train fa and adding ||W I12 as regularizer in the training of W. The algorithm is given in the Appendix. Remarkably the regularizer here resembles "Projection Norm" designed in Yu et al. (2022) for distii-distoobution generalization.
8

---

Published as a conference paper at ICLR 2023
Table I: RotatedMNISST and Digits. Results of baselines are reported from Nguyen et al. (2022).
RotatedMNIST (0"
as source domain)
Digits
Method
15"
30"
45'
60"
75"
Ave
M -
->
M
S - M
Ave
ERM
97.5+0.2
84.1
53.9=0.7
34.2+0.4
22.3+0.5
58.4
73.1=4.2
54,8
65.9+1.4
64,6
DANN
97.340.4
90.621.1
68.724.2
30.810.6
19.020.6
61.3
90.720.4
91.24:0.8
71.140.5
84.3
MMD
97.5+0.1
95.340.4
73.622.1
44.2+1.8
32.1+2.1
68.6
91.320.3
94.420.5
82.840.3
89.7
CORAL
97.120.3
82.3+0.3
56.022.4
30.8+0.2
27.12117
58.7
88.02199
83.340.1
69.340.6
80.2
WD
96.720..3
93.1=1.2
64.1
41.417.6
27.6a2.0
88.2
68.4
72.3
KL
97.8+0.1
97.1
93.4+0.8
75.5+2.4
68.1+1.8
86.4
98.2=0.2
97,340.5
92.5+0.9
96.0
ERM-GP 97.5+0.11
86,240.5
62.0&1.9
34.842.1
26.1+1.2
61.2
91.321.6
72.7444.2
68.410.2
77.5
KI-GP
98.2+0.2
96.940.1
95.0=0.6
88.0+8.1
78.1
91.2
98.8=0.1
97.8+0.1
93.8+1.11
96.8
KL-CL
98.4+0.2
97.3+002
95.6=0.1
83.0+8.2
73.644.0
89.6
98.9=0.1
97.7+0.1
93.0+0.3
96.5
6 EXPERIMENTAL RESULTS
We perform experiments to verify the proposed techniques inspired by our theory.
Datasets We select two popular small datasets, RotatedMNIST and Digits, to compare the differ- ent methods. RotatedMNIST is built based on the MNIST dataset (LeCun et al., 2010) and consists of six domains, each containing 11, 666 images. These six domains are rotated MNIST images with rotation angle 0", ,5 45" 60 and 75% respectively. We will take the original MNIST dataset (0%) as the source domain and take other five domains as target domains. Hence, there are five domain adaptation tasks on RotatedMNIST. Digits consists of three sub-datasets, namely MNIST, USPS (Hull, 1994) and SVHN (Netzer et al., 2011), and the corresponding domain adaptation tasks are MNIST-+USH (M-U), -NISTM (U-M),, SVHN -MNIST (S MM).
Compared Methods Baseline methods are some popular marginal alignment UDA methods in- cluding DANN (Ganin et al., 2016), MMD (Li et al., 2018), CORAL (Sun & Saenko, 2016), WD (Shen et al., 2018) and KL (Nguyen et al., 2022). We also choose ERM as another baseline, in which only the source-domain sample is accessible during training. To verify the strategies inspired by our theory, we first add the gradient penalty to the ERM algorithm (ERM-GP), and we then combine gradient penalty (GP) and controlling label information (CL) with the recent proposed KL. guided marginal alignment method, which are denoted by KL-GP and KL-CL, respectively.
Implementation Details Most of our implementation is based on the DomainBed suite (Gulrajani & Lopez-Pare Paz, 2021). Other settings exactly follow Nguyen et al. (2022) and the results of baseline methods are taken from Nguyen et al. (2022). Specifically, each algorithm is run three times and we show the average performance with the error bar. Every dataset has validation set, and the model selection scheme is based on the best performance achieved on the validation set of target domain during training (oracle). The hype-parameter searching process is also built upon the implementation in the DomainBed suite. Other details and additional experiments can be found in Appendix.
Results From Table 1, we first notice that gradient penalty allows ERM to perform more compara- bly to other marginal alignment methods. For example, on RotatedMNIST, ERM-GP outperforms CORAL and performs nearly the same with DANN. On Digits, ERM-GP outperforms WD. When GP and CL combined with KL guided algorithm, can see that the performance can be further boosted. This justifies the discussion in Section 5.2 and Section 5.3.
7 CONCLUSION
Despite that the numerous learning techniques have been developed for domain adaptation, signifi- cant room exists for more in-depth theoretical understanding and more principled design of learning algorithms. This paper presents the information -oormatton--thoretiic analysis for unsupervised domain adapta- tion, where we query two notions of the generalization errors in this context and present novel learn- ing bounds. Some of these bounds recover the previous KL-based bounds under different conditions and confirm the insights in the learning algorithms that align the source and target distributions in the representation space. Our other bounds are algorithm-depent dependent, better exploiting the unlabelled target data, which have inspired novel and yet simple schemes for the design of learning algorithms. We demonstrate the effectiveness of these schemes on standard benchmark datasets.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work is supported partly by an NSERC Discovery grant and a National Research Council of Canada (NRC) Collaborative R&D grant (L4D-CORE007) Ziqiao Wang is also supported in part by the NSERC CREATE program through the Interdisciplinaryy Math and Artificial Intelligence -NTER-MATH-AI) project. The authors would like to thank the anonymous reviewers for their careful reading and valuable suggestions.
REFERENCES
Alessandro Achille and Stefano Soatto. Emergence of invariance and disentanglement in deep rep- resentations. The Journal of Machine Learning Research, 19(1):1947-1980, 2018.
David Acuna, Guojun Zhang, Mare T Law, and Sanja Fidler. f-domain adversarial learning: Theory and algorithms. In International Conference on Machine Learning, pp. 66-75. PMLR, 2021.
Rohit Agrawal and Thibaut Horel. Optimal bounds between f-divergences and integral probability metrics. In International Conference Machine Learning, pp- 115-124. PMLR, 2020.
Gholamali Aminian, Mahed Abroshan, Mohammad Mahdi Khalili, Laura Toni, and Miguel Ro- drigues. An informatioon-theorttial approach semi-supervised learning under covariate-shift. In International Conference on Artificial Intelligence and Statistics, pp. 7433-7449. PMLR, 2022.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463445 2002.
Shai Ben-David John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. Advances neural information processing systems, 19, 2006.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine Learning, 19(1-2):15 2010.
Jean Bretagnolle and Catherine Huber. Estimation des densités: risque minimax. Zeitschrift für Wahhescheinnlickkettttheorr und verwandte Gebiete, 47(2):119-137, 1979.
Yuheng Bu, Shaofeng Zou, and Venugopal Veeravalli. Tightening mutual information based bounds on generalization error. In 2019 IEEE International Symposium on Information Theory (ISIT), pp. 587-591. IEEE, 2019.
Yuheng Bu, Gholamali Aminian, Laura Toni, Gregory W Wornell, and Miguel Rodrigues. Charac- terizing and understanding the generalization error of transfer learning with gibbs algorithm. In International Conference Artificial Intelligence and Statistics, pp. 8673-8699, PMLR, 2022.
Clément Canonne. A short note on an inequality between kl and tv. arXiv preprint arXiv:2202.07 198. 2022.
Qi Chen, Changjian Shui, and Mario Marchand. Generalization bounds for meta-learning: An information-thhoruee analysis. Advances in Neural Information Processing Systems, 34, 2021.
Corinna Cortes. Spencer Greenberg, and Mchryar Mohri. Relative deviation learning bounds and generalization with unbounded loss functions. Annals of Mathematics and Artificial Intelligence, 85(1):45-70, 2019.
Thomas M. Cover and Joy A. Thomas. Flements of Information Theory (Wiley Series in Telecom- munications and Signal Processing). -iley-Interscience, USA, 2006. ISBN 0471241954.
Koby Crammer, Michael Kearns, and Jennifer Wortman. Learning from multiple sources. Journal of Machine Learning Research, 9(8), 2008
Gavin Crooks. Inequalities between the jenson- and jeffreys divergences. Tech. Note 004, 2008.
10

---

Published as a conference paper at ICLR 2023
Villani Cédric. Optimal Transport: Old and New (Grundlehren der mathematischen Wissenschaften, 338). Springer, 2008.
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.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural net- works. The journal of machine learning research, 17(1):20962003) 2016.
Jonas Geiping, Micah Goldblum, Phil Pope, Michael Moeller, and Tom Goldstein. Stochastic train- ing not necessary for generalization. In International Conference on Learning Representations, 2022.
Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant, Pac-bayes and domain adaptation. Neurocomputing, 379:379-397, 2020.
Ishaan Guirajani and David Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representations, 2021.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Im- proved training of wasserstein gans. Advances in neural information processing systems, 30, 2017.
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. Advances in Neural Information Processing Systems, 2020.
Hrayr Harutyunyan, Kyle Reing, Greg Ver Steeg, and Aram Galstyan. Improving generalization by controlling label-noise information neural network weights. In International Conference on Machine Learning, pp. 4071-4081. PMLR, 2020.
Haiyun He, Hanshu Yan, and Vincent YF Tan. eeformation-theoreti generalization bounds for iterative semi-supervised learning, arXiv preprint 1rXiv:2110.00922: 2021.
Jonathan J. Hull. A database for handwritten text recognition research. IEEE Transactions on pattern analysis and machine intelligence, 16(5):550-554, 1994.
Stanislaw Jastrzebski, Devansh Arpit, Oliver Astrand, Giancarlo Kerg, Huan Wang, Caiming Xiong, Richard Socher, Kyunghyun Cho, and Krzysztof J Geras. Catastrophic fisher explosion: Early phase fisher matrix impacts generalization. International Conference on Machine Learn- ing. PMLR, 2021.
Harold Jeffreys, An invariant form for the prior probability in estimation problems. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 186(1007):453-461, 1946.
Jiantao Jiao, Yanjun Han, and Tsachy Weissman. Dependence measures bounding the exploration bias for general measurements. In 2017 IEEE International Symposium on Information Theory (ISIT), pp. 1475-1479. IEEE, 2017.
Sharu Theresa Jose and Osvaldo Simeone. Information-theeortiicc generalization bounds for meta- learning and applications. Entropy, 23(1):126, 2021a.
Sharu Theresa Jose and Osvaldo Simeone. Information- theeoretic bounds on transfer generalization gap based on gensen-shannee divergence. In 2021 29th European Signal Processing Conference (EUSIPCO), pp. 1461-1465. IEEE, 2021b.
Sharu Theresa Jose, Osvaldo Simeone, and Giuseppe Durisi. Transfer meta-learning Information- theoretic bounds and information meta-risk minimization. IEEE Transactions on Information Theory, 68(1 6811):4745001 2021.

---

Published as a conference paper at ICLR 2023
Diederik P Kingma and Max Welling arXiv:1312.6114, 2013.
Auto-ennoding variational bayes.
arXiv preprint
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http:/yymm.lecum http://aam.ecc....co/eebmbmmii 2, 2010.
Haoliang Li, Sinno Jialin Pan, Shiqi Wang, and Alex C Kot. Domain generalization with adver- sarial feature learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5400-5409, 2018.
Jian Liang, Dapeng Hu, and Jiashi Feng. Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation. In International Conference on Machine Learning. pp. 6028-6039. PMLR, 2020.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In The 22nd Conference on Learning Theory, 2009.
Mohammad Saeed Masiha, Amin Gohari, Mohammad Hossein Yassace, and Mohammad Reza Aref. Learning under distribution mismatch and model misspecification. In 2021 IEEE International Symposium on Information Theory (ISTT), pp. 2912-2917. IEEE, 2021.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning- MIT press, 2018.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. information-theorete generalization bounds for sgld via data-dependent estimates. Advances in Neural Information Processing Systems, 2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Read- ing digits in natural images with unsupervised feature learning. In NeurlPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M Roy. Information- theoretic generalization bounds for stochastic gradient descent. In Conference on Learning The- ory. PMLR, 2021.
A. Tuan Nguyen, Toan Tran, Yarin Gal, Philip Torr, and Atilim Gunes Baydin. KL guided domain adaptation. In International Conference on Learning Representations, 2022.
XuanLong Nguyen, Martin J Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 566 36(11):5847-586 2010.
Daniel Palomar and Sergio Verdú. Lautum information. IEEE transactions on information theory, 54(3):964-977 975, 2008.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32: 8026-80377 2019.
Xingchao Peng, Ben Usman, Neela Kaushik, Judy Hoffman, Dequan Wang, and Kate Saenko. Visda: The visual domain adaptation challenge. arXiv preprint arXiv:1710.06924, 2017.
Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy, iterative algo- rithms. In 2018 IEEE International Symposium Information Theory (ISIT). IEEE, 2018.
Yury Polyanskiy and Yihong Wu. Lecture notes on information theory. Lecture Notes for 6.441 (MIT), ECE 563 (UIUC), STAT 364 (Yale), 2019., 2019.
levgen Redko, Emilie Morvant, Amaury Habrard, Mare Sebban, and Younes Bennani. A survey on domain adaptation theory. arXiv preprint arXiv:2004 1829, 2020.
12

---

Published as a conference paper at ICLR 2023
Arezou Rezazadeh, Sharu Theresa Jose. Giuseppe Durisi, and Osvaldo Simeone. Conditional mutual information- based generalization bound for meta learning. In 2021 IEEE International Sympo- sium Information Theory (ISIT), pp. 1176-1181 IEEE, 2021.
Borja Rodríguez-Gálvez Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. On random subset generalization error bounds and the stochastic gradient langevin dynamics algorithm. In 2020 IEEE Information Theory Workshop (ITW), pp. 1-5. IEEE, 2021.
Borja Rodríguez Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. Tighter expected generalization error bounds via wasserstein distance. Advances in Neural Information Processing Systems, 34, 2021.
Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics. PMLR, 2016.
Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302-323, 2019.
Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. In Thirly-second AAAI conference artificial intelligence, 2018.
Maohao Shen, Yuheng Bu, and Gregory Wornell. On the benefits of selectivity in pseudo-labeling for unsupervised multi-source-free domain adaptation. arXiv preprint arXiv:2202.007%. 2022.
Changjian Shui, Qi Chen, Jun Wen, Fan Zhou, Christian Gagné, and Boyu Wang. Beyond H-divergence: Domain adaptation theory with jensen-shannon divergence. arXiv preprint arXiv:2007.15567 2020.
Samuel L Smith, Benoit Dherin, David Barrett, and Soham De. On the origin of implicit regular- ization in stochastic gradient descent. In International Conference on Learning Representations, 2021.
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference Learning Theory. PMLR, 2020.
Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation. In European conference on computer vision, pp. 443-450. Springer, 2016.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008
Vladimir Vapnik. Statistical learning theory. Wiley, 1998. ISBN 978-0-471-03003-44
Boyu Wang, Jorge Mendez, Mingbo Cai, and Eric Eaton. Transfer learning via minimizing the performance gap between domains. Advances in Neural Information Processing Systems, 32, 2019.
Hao Wang, Rui Gao, and Flavio P Calmon. Generalization bounds for noisy iterative algorithms using properties of additive noise channels. arXiv preprint arXiv:2102.00996,, 2021a.
Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Wenjun Zeng. and Tao Qin. Generalizing to unseen domains: survey on domain generalization. arXiv preprint arXiv:2103.00 103.03097 2021b.
Ziqiao Wang and Yongyi Mao. On the generalization of models trained with SGD: Information- theoretic bounds and implications. In International Conference on Learning Representations, 2022a.
Ziqiao Wang and Yongyi Mao. Two facets of sde under an information-theerriic lens: Generalization of sgd via training trajectories and via terminal states. arXiv preprint arXiv:2211. 2022b.
Ziqiao Wang and Yongyi Mao. Tighter information-theorede generalization bounds from supersam- ples. arXiv preprint arXiv:2302.02432. 2023.
Garrett Wilson and Diane J Cook. A survey of unsupervised deep domain adaptation. ACM Trans- actions Intelligent Systems and Technology (TTST), 11(5):1 2020.
13

---

Published as a conference paper at ICLR 2023
Xuetong Wu, Jonathan H. Manton, Uwe Aickelin, and Jingge Zhu. Information -hheoorttcc analysis for transfer learning. In 2020 IEEE International Symposium on Information Theory (ISIT), pp- 2824. IEEE, 2020.
Aolin Xu and Maxim Raginsky. Information-theoretic analysis of generalization capability of learn- ing algorithms. Advances in Neural Information Processing Systems, 2017.
Yaodong Yu, Zitong Yang, Alexander Wei, Yi Ma, and Jacob Steinhardt. Predicting out-of- distribution error with the projection norm. arXiv preprint arXiv:2202.058844 2022.
Yuchen Zhang. Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. In International Conference Machine Learning, pp. 7404-7413. PMLR, 2019.
Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon. On learning invariant representations for domain adaptation. In International Conference on Machine Learning, pp. 7523-7532. PMLR, 2019.
Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization: A survey. arXiv e-prints, pp. arXiv-2103, 2021.
14

---

Published as a conference paper at ICLR 2023
Appendix
Table of Contents
A Some Prerequisite Definitions and Useful Lemmas
15
B Omitted Proofs and Additional Results in Section 4
17
B.1 Proof of Theorem 4.1
17
B.2 Proof of Corollary 4.2
17
B.3 Proof of Theorem 4.2
17
B.4 Proof of Theorem 4.3
18
B.5 Proof of Theorem 4.4
18
B.6 Proof of Corollary 4.3
18
B.7 Proof of Theorem 4.5
19
B.8 Additional Results: Sample Complexity Bounds
19
B.9 Additional Discussions the Convergence of Empirical KL Divergence
20
B.10 Generalize Approximate Triangle Inequality
21
C Omitted Proofs and Additional Discussions in Section 5
21
C.I Additional Discussion on Theorem 5.1
21
C.2 Proof of Theorem 5.1
22
C.3 Proof of Corollary 5.1
23
C,4 Proof of Theorem 5.2
25
C.5 Proof of Corollary 5.2
25
C.6 Proof of Theorem 5.3
25
C.7 Derivation of Eq. (6).
27
C.8 Additional Discussion on LIMIT
27
D Experiment Details
27
D.1 Objective Functions of Gradient Penalty and Controlling Label Information
27
D.2 Algorithm of Controlling Label Information and Additional Results of ERM-CL
28
D.3 Architectures and Hyperparameters
29
D.4 Additional Experimental Results
29
D.5 Ablation Study on the Effect of Gradient Penalty Hyperparameter
29
D.6 Visualization Results
29
D.7 Results on VisDA17
30
D.8 Dynamics of Jeffrey's divergence
31
A SOME PREREQUISITE DEFINITIONS AND USEFUL LEMMAS
Definition A.1 (Wasserstein Distance). Let d(., be metric and let P and Q be probability mea- sures on X. Denote T(P, Q) the set of all couplings of and Q (i.e. the set of all joint distri- butions on X X with two marginals being P and Q), then the Wasserstein Distance of order one between P and Q is defined as W(P. Q) & inf Sxxx d(x, x ) x²).
Remark A.I. Similar to Rodríguez Gálvez al. (2021), here mainly focus on 1-Wasserstein dis- tance but all the upper bounds based on I-Wasserstein distance also holds for higher order Wasser- stein distance by Hölder's inequality (Cédric, 2008, Remark 6.6).
Definition A.2 (Total Variation), The total variation between two probability measures P and Q TV(P.Q) - supg PPF)) Q(F.),, where the supremum is all measurable set F.
15

---

Published as a conference paper at ICLR 2023
Remark A.2. Note that the total variation equals to the Wasserstein distance under the discrete metric (or Hamming distortion) d(z,x') = 1z4s' where is the indicator function (Cédric. 2008, Theorem 6.15).
The key quantity in the most iiformation-thhoreee generalization bounds is the mutual information between algorithm's 's imput and output. Specifically, the core technique behind these bounds is the well-known Donsker- Varadhan representation of KL divergence (Polyanskiy & Wu, 2019, Theo- rem 3.5).
Lemma A.1 (Donsker and Varadhan's variational formula). Let Q, P be probability measures O. for any bounded measurable function f R, we have (KL(Q] = sup, Re-q [f()] log Ea-p f f())]-
Remark A.3. Motivated by the classic f-divergence, Acuna et al. (2021) proposed a discrepancy measure called D Disdiccrepyncy (or Dj, disceeiicc)))ncy).. As KL. divergence belongs to the family of f-divergences and both Acuna et al. (2021) and our work use the variational representation of divergence, there appears to be connection between our work (in Section 4) and theirs. However, it's important to note that the variational characterization of f-divergence used in Acuna et al. (2021) is based the results of Nguyen et al. (2010), while the Darsker-Varadhan Varadhan representation of KL divergence (see Lemma A used in our paper cannot be directly obtained from their variational characterization (Jiao et al., 2017; Agrawal & Horel, 2020). In fact, simply choosing x log z as the conjugate function would result in a weaker bound than Lemma A.I. Therefore, while there is some similarity between results and those of Acuna al. (2021), I), our results in Section 4 cannot be directly derived from theirs.
Similar to Xu & Raginsky (2017, Lemma 1.), we need the following lemma as a main tool.
Lemma A.2. Let Q and P be probability measures Q Let O' Q and P. 90) is R-subgaussian, then,
EEr~Q [a((') - Ea- [a(0)]] S V2R (QIIP)
Proof. Let f =t= g for any t R. by Lemma A. we have
(KI(()1P)) 2 sup Ee Q [(){ log Ea- (exp / g(0]
sup Ee - [l)( log Eu-p (exp (g)(0) - Eg~p [g( + Ee-p (0)))
ssup Eq [lg(0')] Ea- [lg(0)) - log Eynp (exp (g(()) Eg P [g (0)))
2 sup/ / (R [0()') - Ea- [0)) - 12 /2,
where the last inequality is by the subgaussianity of g(0).
Then consider the case > and 6 < 0 (t = is trivial), by AM-GM inequality (i.e. the arithmetic mean is greater than equal to the geometric mean), the following is straightforward,
[Erra 19(0") Es- < V (Q)P))
This completes the proof.
The following lemma is the Kanborvvich-Rubinstenn Rubinstein duality of Wasserstein distance (Cédric, 2008).
Lemma A.3 (KR duality). For any two distributions P. and Q, we have
W(P.Q) = sup 1 JaP 1 SdQ,
sEI-Lip(p)
where the supremum is taken over all 1-Lipschitz functions in the metric d, i.e. If(x) f(x') < d(x,,') f'r for any x, x' X.
To connect total variation with KL divergence, will use Pinsker's inequality (Polyanskiy & Wu, 2019, Theorem 6.5) and Bretagnolle-Hun Huber inequality (Bretagnolle & Huber, 1979, Lemma 2.1) in this paper, for more discussion about these two inequalities, we refer readers to Canonne (2022).
16

---

Published as a conference paper at ICLR 2023
S X
S
W
/
Figure 1: The relationship between random variables in UDA, where F = Ry Rs(W).
Lemma A.4 (Pinsker's inequality). QV(P,Q) & (2DK((PIQQ.
Lemma A.5 (Bretagnolle-Hiee Huber inequality). TV(P, Q) S vI - e PxL((110
Below is the variational formula (or golden formula) of mutual information.
Lemma A.6 (Polyanskiy Wu (2019, Corollary 3.1.). For two random variables X and Y, we have
T(X; Y)
inf [DKL(QyxxlPP)]
P
where the infimum is achieved at P = Qy-
B OMITTED PROOFS AND ADDITIONAL RESULTS IN SECTION 4
B.1 PROOF OF THEOREM 4.1
Proof. Let Q = = P= y and f, then Theorem 4.1 comes directly from Lemma A.2.
B.2 PROOF COROLLARY 4.2
Proof. As discussed in Remark 4.1, when the loss is bounded in [0, Ml. guaranteed to be 2 subgaussian for any E W. Then, similar to the proof of Theorem 4.1, let Q n. P n¹ and 2 then the following bound holds by Lemma A.2,
g = l and
M
Err( w)) &
(KL(H)le)).
2
Then, by min(A, B} < (AA+ B), the remaining part straightforward,
M
M
Err(w) < / (Dlaa DKL (('lle)) s VDKL(Hllu") + DKI (w')ll))
2
V2
This completes the proof.
B.3 PROOF OF THEOREM 4.2
Proof. Let w' arg win Ez [X'f, Y")] Ez B2 By Lemma A.1,
DKL (Px 2 sup
Ex [tl( (X'). log (X](f(((),,x,xx0
tER
Recall that (X), fm.. is R-subgaussian, by using Lemma A.2 (let Q = Pxi, P = Px and
g(.) = E(Swr Sm (.)),, we have
Ex [X(f fw (X Ex (X), (x)]] / (Px. (7)
17

---

Published as a conference paper at ICLR 2023
For any fu F, by the symmetric and triangle property of the loss, have
Ex [((f((('),
Sxx (XX)) (x (e (X"e
3Ex
+ Ez [e( (X'), Y
(8)
1. (AA.: Ez (w (X'), Y
[. (1 ( Px + Ez [e(fw-(X') yn)
22R2DKL
< /
+ C1,, (10 (2 Bz [e( (X'), Y
-E2 (((f(()) Y) + E2 [ fo (X)) + ( + Ez [e(fw- (((f==(X'), where Eq. (8) is by Eq. (7) and Eq. (9) is again by the triangle property of the loss function. Thus, Err(w)= S 22 Px) + X", which completes the proof.
B.4 PROOF OF THEOREM 4.3
Proof. By Lemma A.I,
(RL(Px||Px)) 2 sup Ex (X') fw - log Ex ( WE
2 sup Bw. Ex [t([Jw(()))) fww(('))) log Ex (c(tUw(())
2 Ww. Ex [tl[fw (X'), fw (X')) log Ew.w Ex [ eER
where the last inequality is by applying Jensen's inequality to the logarithm function, which is concave.
By the subgaussian assumption,
[Ew,w [Ex, ((JJ(X') [wx)('))]] Ewww Fx This concludes the proof.
S (Px
B.5 PROOF OF THEOREM 4.4
Proof. From the definition, we have
Eir(w) = |E2/ -
(H,
where the last inequality is by the KR duality of Wasserstein distance (see Lemma A.3).
B.6 PROOF OF COROLLARY 4.3
Proof. When d is the discrete metric, Wasserstein distance is equal to the total variation, then by Theorem 4.4,
Err(w) S BTV (H(,p),
The remaining part is by using Lemma A.4 and Lemma A.5:
BTV 1d) s BV min ( (KLLLlll))) e-DKI(H"ll))
Then, if 8 is bounded by M. replace by M above, which completes the proof.
18

---

Published as a conference paper at ICLR 2023
B.7 PROOF OF THEOREM 4.5
Proof. Let w² = arg win Ez (X'), YO] + Ez (((fm.())) ()),
If (X), Sar (X)) is B-Lipschitz in X' for any w, w W, then similar to Theorem 4.4, it's easy to show that
Ex (e( f" (X), Ex
(W Px)
(10)
For any fw E F, by the symmetric and triangle property of the loss, we have
Ez. (x() Y")
Ex (X(Fuo(''),, (x + Ez [e(su. (X'), Y']
Ex (X), (X)) + BW Ez [e(f (X'),'')
(11)
SEz (X), Y) + Ez fw. (X)) 3W (P'x Px) Ez (X(), Y')),
where Eq. (11) is by Eq. (10) and the last inequality is again by the triangle property of the loss function. This completes the proof.
B.8 ADDITIONAL RESULTS: SAMPLE COMPLEXITY BOUNDS
One of the main ingredients to derive our sample complexity bound is the following lemma, where a concentration bound for a class of unbounded functions is given.
Lemma B.1 (Cortes et al. (2019, Corollary 9)), Let K. > 2 and (g s.t. E,, [e9(2]] <
too}. Assume E [a(Z)=] < +oo for all E G. Let ju be the empirical distributions consist of n data points sampled i.i.d. from μ. If G has the finite pseudo-dimensien following inequality holds for all E 9 with probability at least - 5,
then for Vo (0, 1). the
1
2en 4 53)
En [o([))] < Ep [o(2)) + 2A(R) V E. (1(2)))
dolg d
+ log
where A(x) = (1) 2
Below is another useful lemma for the bounded case, which comes from Mohri et al. (2018, The- orem 11.8) with a slight modification (by invoking different VC-dimension based generalization bound from Vapnik (1998)).
Lemma B.2. Let
Assume Ey [S())] < M for all J E F for some constant M > O. Let ji be the empirical distributions consist of n. data points sampled i..d. from Js. If F has the finite sseudo-dimension d, then for vd E (0, 1), the following inequality holds for all f e F with probability at least 1 1-6 5,
(J 2 2-
1
2en 4 d (
E, [f(Z)) S Ep [f()] + 2M
dlog
log
We are now position to state our sample complexity bound. Theorem B.1. Let f and je be the empirical distributions consist of n source data and target data sampled i.idd. from and μ², respectively. Lei G = {g Z - R s.I. E2 [e9(2]] < x with finite aseudo-dimension di, and let the pseudo-dimension of (exp gig E G} be dz. Let > 2 and assume that E,, [g(Z)*] < too for all g G. Assume there exists constant s minges (E.p [e9(2]] 1,92,)],E,, Ep, [co(2]]], Then for v8 E (0,1) the following bound holds with probability at least 1-5-
2en di log di
+ log :) +Ca(aay 1 m [(d dz log d2
2em
+ log 4
DRL(H - (A'llA) & (1(())
2- gegg EE (1(2) and C2(a) = Sup Ey, [69(2]].
where (i(s)
19

---

Published as a conference paper at ICLR 2023
Proof. Recall Lemma A.1, we have
DRL("llu) = sup E,r [g(2")] - log BB [cotec]
959
and
(KL(llll2) = sup Ear [9(Z")] - log Mp [e012)] 9EG
Then, with the probability at least ò, 6,
(KL ((lllx) - (x'1(2))
sup Bw [a(Z')] log E, [0022)]
sup Epr [a(2") log Ea [c0te2]
DEG
9EG
I sup En [g()") log E,
[c0t21]
Ear [a(2z) - -log Ep (2012)
gEG
sup By [g((")] Epr [g(2))] )] log Ba
[0(22]]
log By
[9(2)]
S sup [E [9(2')] - Ep [o((')| + sup gEg
log E,
3EG
S sup EE [o(2")] - Ep (g( (2))l + sup DEG a
Ep
[
Ep [0022]]
(12)
gEG
(C((1)) / (dr log d1
2en + +log 8) ;) + Calaa)
2em
log 4 8)
d2 d2 log
(13)
m
d2
where Eq. (12) is derived below.
W.L.O.G. assume that Ep [e9(2)) Ey [c0(2)]), ) then
I E2 [e9(22) (and Eq. (12) still holds when E& [c9(2)]
= log E,, [e9(2]]
Ey [e9(2]]
log Ep [c012]] log E2 [e012]]
log
1 1+
1
E₁ [e9(21]
Ep [E9(2)]
E, [e9(2))
E2 [ea(2]]
FF [20(2)]
E, [
Eg [ea(Z]]]
Bu (
[
Ep
Eq. (13) is by Lemma B.1 and Lemma B.2. This concludes the proof.
With Theorem B.1 and Theorem 4.1, we immediately have the following corollary. Corollary B.1. Let the conditions in Theorem B. and Theorem 4. hold, then for any W.
1
1
Zen + log 1 2)) + +Calaoy d2 log di
4 5 2em + log 1 dd (d2log
Brr(w) s V2RR (
d2
where Ci(s)) and C2(2)) are the same as in Theorem B. 1.
B.9 ADDITIONAL DISCUSSIONS ON THE CONVERGENCE OF EMPIRICAL KL DIVERGENCE
Characterizing the convergence of the empirical KL divergence to the real KL is challenging task that often requires several additional assumptions, as demonstrated in Theorem B. However, is worth noting that the convergence rate of the empirical distribution to the real distribution in the KL sense is already established in the discrete space. This fact is supported by classic result in (Cover & Thomas, 2006, Theorem 1 11.2.1), which state in the following theorem:
20

---

Published as a conference paper at ICLR 2023
Theorem B.2. Let and fi' be defined in Theorem B.I. Assume the space of Z is finite (i.e. [2] & 00), then for E (0, 1), with probability at least 1 - 6,
1 log (n + 1) log 8' (KL(AllA) & n
2 m
DKL(H -
log (m + 1) log 8"
Thus, it suffices to ensure that the empirical KL converge to the real KL with the similar rate, although do not know if there might exist faster convergence rate.
B.10 GENERALIZE TO APPROXIMATE TRIANGLE INEQUALITY
In Section 4, some results require that the loss obeys the triangle inequality (i.e. Assumption 4), such as Theorem 4.2 and Theorem 4.5. While the loss may not. Thus, to generalize Theorem 4.2 and Theorem 4.5, we invoke approximate triangle inequality, which originally defined in Crammer al. (2008).
loss satisfies Assumption 4, some other
Assumption 5 (a-Triangle). ((:-)) symmetric and satisfies the following a-triangle inequality: f(1,,92 v2) I a (f(gn, Us) + E(ys.U) y2)) for any y1, y2, V, where a 2 is constant that may depend on the hypothesis space W and the loss
Remark B.1. We note that the squared loss satisfies 2-triangle inequality.
Thus, Theorem 4.2 can be easily generalized below.
Theorem B.3. If d'Assumption 5 holds and let E(S (X), (X)) be R-subgaussian for any w, w' W. Then for any w,
Err(w) S (a² - R1) + av DR Pxx Px) where X minlaew By (w)) + (w).
Theorem 4.5 can generalized the similar way. While Theorem B.3 strictly speaking is not generalization bound, it includes R, in the bound, it shares the same underlying concept as Theorem 4.2. Namely, to minimize the population risk in the target domain, essential for the source domain and target domain be similar, and for both Ry and X to be kept small.
C OMITTED PROOFS AND ADDITIONAL DISCUSSIONS IN SECTION
C.1 ADDITIONAL DISCUSSION THEOREM 5.1
To derive the bound in Theorem 5.1, we need to make use of the second equality in Eq. (1). In fact, by the definition of Err (the first equality in Eq. (1)), the unlabelled sample S'x; does not explicitly appear, one can easily apply the similar information-theorrtic analysis starting from the first equality in Eq. (1), and obtain an upper bound that consists of (W; Z,) and (ull)'). Precisely, the following bound holds.
Theorem C.1. Assume (Xfw(X'), Y.) is R-subgaussian for any W. Then
Err| < E EVVRR-IW:2 2.) (2R-DKL(Mlll)))
The proof of Theorem C.1 is nearly the same to the proof of (Wu et al., 2020, Corollary 2) and (Masiha et al., 2021, Corollary 1).
It's important to note that although
I(W; 2.) < [(W: Ex; [w:
the bound in Theorem 5.1 is incomparable to the bound based on I(W; Z,). This is mainly due to the fact that we use the disintegrated version of mutual information, [ Z,). and the expectation X3 is outside of the square root, which convex function. Using X (W; 7z) instead of
21

---

Published as a conference paper at ICLR 2023
[WW; Zz) allows us to figure out more details about the role of unlabelled target data in the algorithm. Additionally, one can also prove a bound based on I(W; ; Z Xx) (e.g., simply applying Jensen's s inequality to Theorem 5.1), which is close to individual and UDA version of (Bu et al., 2022, Theorem 3).
Furthermore, the first term in Theorem 5.1 characterize the expected generalization gap on the source domain (i.e. Ew,s RR, (W) - Rs(W))), then the bound suggests us that it's possible to invoke the unlabelled target data further improve the performance on source domain, and the simplest case is the semi-supervised learning (when μ = jt).
Compared with (Wu et al., 2020; Jose & Simeone, 2021b). Notably, bounds in (Wu et al., 2020; Jose & Simeone, 2021b) fail to characterize the dependence between W and S'x More pre- cisely, the algorithm-dependent term in their bounds is [W; Ze) I(W;S), while our algorithm- dependent term X (W; Zj) that directly depends on the unlabelled target data. Moreover, while the disintegrated mutual information (W; Z,) (W;
and the unconditional mutual information T(W; Zz) cannot be directly compared, recent work by Wang & Mao (2023) provides empirical evi- dence comparing similar terms in the supervised learning setting. Specifically, they demonstrate that when the empirical risk is small, such as in realizable case, the disintegrated mutual information is smaller than the unconditional mutual information. Conversely, when the empirical risk is large, the unconditional mutual information the smaller of the two.
More Discussion on the Vanishing of I(X;; Z.(W) in Remark 5.1. Note that S depends on S'x' given W, so intuitively the dependence between each individual instance Z, and X; is weaker when n and m become larger. More precisely, W.L.O.G let i = j = 1, and recall that W A(s when n, m - oc, taking S and 5xx as the input of the algorithm is nearly equivalent computing W based on the source distribution μ and the target distribution Pxx, thus, W will only depend on the two distributions, without depending on the realizations Z1 and X drawn respectively from the two distributions, that is, T(2;; X (W)
T(71; X1|A(H Pxx)) = T(Z;; X;) 0. In addition, one may argue that what if W = constant that does not really depend on the input data. In this case, ((IW) then W A(X Z1), and the quantity 1(21; (XX, 21)) should be large. When and m increase, it becomes I I(21: X A(X 1:m: Z1:n)). Now we want to guess Z₁ from X1, this should be easier when having the knowledge of A(X;; Z1) compared with when having the knowledge of A( A(Xi.m i.mi Z.m)
I (1) = O will hold trivially. In the other extreme, if n = 1 and m = 1,
C.2 PROOF OF THEOREM 5.1
Proof. By Lemma A.I,
DKL (Pwizzlx/=0/) |I Pwiz1x;=23)
-DKL (Pw.z.l;:=3) Pwixx=0; 1IPIXx Pz:
(14)
2 sup Brw.z,xz3=1) [[e(Sw (Xt), Vi) log E E. x Per lexp (Ll(S((()()) Y')l
sup Er Br [te(fw (X.), YJ) -rriingnn [ty RR&2/22 /2,
where Eq. (14) is by the independence between algorithm output W and unseen target domain data Z', and the last inequality is by the subgaussian assumption.
Thus,
(X),),))) Ep B...21i3-- (X,,, YJ) - EPwix3-3 Ry (W)] & $ 2R || P2:
(15)
22

---

Published as a conference paper at ICLR 2023
Exploiting the fact that
Err]
Ew (e(f Y.) - EE,z [e(fw(x)), Y
xx
Ew.zix; [[(fw(X)), Y.) 1,22 (X((w(X'))))))
Ex
Ew.zix; Re(w (X.), Y.) Ew,zix; (e(ff (X)))))
]=1
Ex
Ew.zixy [e(f (X.), YJ] -Ewix [R (W)]
7m
where the last two inequalities are by the Jensen's 's inequality for the absolute function.
Notice that
log Pw.zix;--r PwIxy=u; Pz:
DKL (Pw221x==2]IIWxxx=
P Pzz
log Pwix/==3 P2:
Pwizz.x3=0s
Pz. log Pz
-BPW.ziA0--6 -as =I(W; Zi|x; = x²)) + (KI(H))K))
log
Erz.
Pwixy=e3
Recall Eq. (15), we then have
m
Em
S
Exy
Ew.zix; (X.fw(X.)), YJ) Ewix; (W))
nm
j=l
Exp1
2R'DRL (Pw.z,ix)l PIwxxx,
TUT
j=1
Exy
(2 23) + (kll())lee))
mM
Ex Exy
Bx 2R (W; 2,) + D2
This completes the proof.
C.3 PROOF OF COROLLARY 5.1
Proof. We now modify the proof in Theorem 5.1.
Recall that
n Ex; Ew.z.Iy, (X,, Y.) Ewix; (Ry (W))
Errl <
nm
j=1
23

---

Published as a conference paper at ICLR 2023
We first decompose the right hand side,
Ew,zix33 o [X(f Yi)] - Ewix3 - (W')
[w.,z1x3=-a [((ffw(X)) Yi]] Ewix3-or RR (W)) + E BwIx (W)) Ewixy=s3 [ (W)]
[ (((/w(Xx)) Yi] BwIx [R (W))
[ (W) Ry.((W)
M
< Ew.zIx3=aa (X.W((.))))))) YJ) - E [R2
/nin DKr. (x'l())
where the last inequality is by Corollary 4.2. Then for the first term in RHS, notice that
DKL 1W.21X/==//PWW/IIX:-
Pz -KKL P21P,,,;;
2 sup E mixx,=e; 12 [e([S (X),)) loog E Er W.z (xxpt((w((x)) YJ)
2 sup Ep 3 Pz [te(fw (X) EP P (X.),, Xi)
(x)
(100))))))))
log E 2w.z,1x3-4/ e
2 sup Ep Eixx (R)] - EP 11 (e(swW((W (Xi), Yi)l - -M21?/8,
where the last inequality is due to the fact that & is bounded by M and ((fw Yi) M/2- subgaussian.
Thus,
M
1ww.2ixx==/((WWW(XX. - Ewix3=at [W,( SV DKL. (PWIxx=;;
M²
=V (W. =x²))
Plugging this inequality with the decomposition into the inequality at the beginning of the proof, we have
M
M
Em
E
X
x
(W, (W,
2x)
+
min Dir.
2
2
Similar development also holds for DKL (PWxx,:= as in the proof of Theo- rem 5. thus
M
M
Emrl <
Ex
min {
(W: 2.),
min (al(())))) ((L())))))
2mm
/2
This completes the proof.
24

---

Published as a conference paper at ICLR 2023
C.4
PROOF OF THEOREM 5.2
Proof.
Similar to the proof of Corollary 5.1, recall Theorem 4.4,
Errl
m
Exy
Ew,zix; (X.), Xi) Ewix; (R)) + Ewix; [R)( Ewix; [R (W))
mm
j=1
Exy Bw.Z.x;; (X,[ YJ)l - Bwixs [R) + (,,(,,
mm
i=1
Exy.zz EWIzz,,; (X.),
(X.), Yi) - Ewix, (X)) (X)),,))) +,W().))
j=1 i=1
8'
B Bxy. W W(Pwixx,2, Pw;x;) + (w,
where the last inequality is by Lemma A.3. This concludes the proof.
C.5 PROOF OF COROLLARY 5.2
Proof. Similar to the proof of Corollary 4.3, replacing Wasserstein distance by the total variation and replacing 3 and 3 by M, will give us the first inequality.
M
Err
Ex 2. ( PwIx)) + (TV(H,
TUTE
The second inequality is by Lemma A.4,
M
D (Puu(1/,,xx1 + V 2 DRL(alla))
M
Err
Ex, 2
E
Again, one can also apply Lemma A.5 here. This concludes the proof.
C.6 PROOF OF THEOREM 5.3
Proof. Recall Theorem 5.1 and by Jensen's 's inequality we have
Errl < nm
Exy 2 + DR
2R
I(W: (W;Z + DeL
Let X/ X 1....
5'x
X Notice that
I(W; Z,15xx)
=[(W; Z1(5x) + T(X 1..... 1-14 Zz(X3)
=1(W: ZZWx) 1(X' ( 11.1--1111... ZilX', W)
2/(W: (ZI))
Thus, 1(W; 21x)) < I(W; 5.)5) Then
ΣΣ
m
1(W
ΣΣ
IW: Z[8)) - Σ
I(W: Z.1x)))..
YLT
nm
25

---

Published as a conference paper at ICLR 2023
Then, since S TL S'x, and Zi -T Z for any i [nd,, by the chain rule of mutual information, have
(W; = Σ T(W 214-1)
7W; 71--1)+ T(7;; 714-1)
1
I(W; Sxx + I(2: Z Z W)
(W)))))))
Thus, the generalization error bound becomes
2R n
Emrl
I(W: ((:: (2
Recall the updating rule of W and notice that Wo is independent of S and S'x,, the following process is by using the chain rule of mutual information and data processing inequality recurrently,
IWTr;
(wrr-1--rgWrr---ee Br. XBB,) ) + Nr; S1x') + NT; S1S'x)
-1(Wr-1;515xx) + ( Z B',, + Nr; S1S;; Wr-1)
Σ (mng(W.1,,7n, Xbb) S,
For each ē [T], denote 9W ZB. Xb,) as Gr, then
[(ng(W--1, ZB, X'x,) S15 W,-1) = -Esy xn W.-.. 1.S
DKL m (.s.,Sy.....1 Get Ny 18 W...
E Se 1,
DKL DKI(PG.t G.+ S. w.,, | P [s. N 1s..
r/ Egg 20
xx W.-1. [IGG - Es [G.]1
where the inequality is by Lemma A.6 and the last equality is by the KI. divergence hetween two Gaussian distributions.
Finally, putting everything together,
T R²
Th
[[GG, - Es [G:]1[]] + (2R2Dxi,(ullp))
Errl S
E
Eg
n
o
which concludes the proof.
26

---

Published as a conference paper at ICLR 2023
C.7 DERIVATION OF EQ. (6)
Recall the expected cross-entropy loss, we have
Ew.z, [e(fw (T.), Yi) Ez,w w
log QYIT,
PYIT.,W
Ez,,w
log
QY.IT.W PYITT.W
HY, W) + Ex,w [DRI. P [x
Pr,m, Pwiz:
-B,,w
log
+ Er.w [DKl(Py, m,,1111mmm...)
PrIr.w Pyitr Pwinn
Py, Pwin.
E2,,w log
+ Br,w (Pai,
PY,.WIT; PYaIT:
(T) - I(W; (((,) + +E,,w (Di.(P))m..wwl0x/y....
C.8 ADDITIONAL DISCUSSION ON LIMIT
In Section 5, we discussed the LIMIT approach proposed by Harutyunyan al. (2020) means of controlling label information memorization during training. Roughly speaking, to update the classifier parameters. LIMIT constructs an auxiliary network that predicts gradients instead of using the true gradients, which avoids direct use of the true labels for training. To obtain accurate gradients, the auxiliary network needs to be trained using the true labels. We found that the training of LIMIT is unstable and difficult to tune the hyperparameters when used under UDA settings. Therefore, we opted to use the pseudo label strategy proposed in Section instead the pseudo gradient strategy.
D EXPERIMENT DETAILS
We implemented our approach using PyTorch (Paszke et al., 2019) and conducted all experiments on NVIDIA Tesla V100 GPUs with 32 GB of memory. Our code builds largely on the implementation from Gulrajani Lopez-Paz (2021)² and Nguyen al. (2022)*.
D.1 OBJECTIVE FUNCTIONS OF GRADIENT PENALTY AND CONTROLLING LABEL INFORMATION
For every iteration, the objective function after adding the gradient penalty becomes min L(W, X'2,) + Aullg W, X W
where i.W, BB, XB,) is some loss function for the source and target domain data in the current mini-batch and A1 is the trade-off coefficient. For example, if combine ERM with gradient penalty then L(W, ZB, X²,,) - Moreover, if we combine KI. guided marginal alignment algorithm (Nguyen al., 2022) with gra- dient penalty then the objective function is
[..] Σten, {(Sw (Xx), Ys) and could be the cross-entropy loss.
min W.
Σ e(fw (Tk), Y2) (Pr-(P))))))) (Prl(Pr) All Zp. X1,,11
Xg.
B
AEB,
where 0 the parameters of the representation network and the gradient
g(W, LB. X'B.)
(aa KEB.
B
In Nguyen et al. (2022), the representation distribution is modelled as an Gaussian distribution, i.c., N N(po, x) and T" N(Jo, X'"). Additionally, let the batch size be = Br], the
"Available at:
Available http///gthaa.ccmmaauuggggeennl
27

---

Published as a conference paper at ICLR 2023
Table 2: RotATedMNNST and Digits Experiments of ERM-CL, Results of ERM are reported from Nguyen et al. (2022).
RetaledMNIST
domain)
Digits
Method
15
30
M
ERM
97.510.2
84.140.8
53.920.7
34,240.4
22.3a0.5
58.4
73.124.2
54,816.2
65.9414
64.6
ERM-GP FRM-CL
97,5=0.1
86,220,5
62.0=1.9
34.8+2.1
26.1#1.2
61.2
91.3:1.6
72.764.2
68.410.2
77.5
97.3+0.1
84.1+0.1
56.9+2.5
34.2+1.9
25.5+1.6
88.9=04
71,2+3.6
73.5+1.4
77.9
empirical KI, divergence is estimated by the mini-batch data, as given in Nguyen al. (2022),
DK (Pr Pr) 82D (Prl|PPr)
3131 Σ
[og Pr:- - log Pr.] 82
1
Σ
blog Pr. - log Pril
kEB,
kEB.
= 31
log Σ
P log
P
+ B2
log Σ KEB,
Prix, log
Prylx%
KEB,
KEB,
AEB
KE F3
AEB:
where Pr, oN {3) and Prix,; (uo,, ogLa(-X()) To be more precise, μ4ر and de the outputs of the representation network. Since the forward pass requires the sampling of and T. we need to use the reparameterization trick (Kingma & Welling, 2013) for the backward pass.
When we train the model with controlling label information, the objective function becomes
min L(W, Zz, XB,) + >allW -
where W is the auxiliary classifier and X2 is the trade-off hyperparameter.
Similarly, when we combine KL guided marginal alignment algorithm with controlling label infor- mation, then the objective function in every iteration is
min W.9
Σ ((Jw (Te), Yx) + Dx. kEB.
(rD + >2/lW WIl
Be
In addition, the training objective for the auxiliary classifier is
min W
Σ fW) + Σ keB,
1 Bel
(T),
(16)
Bd
AEB;
In practice, removing the second term would not affect the performance. Note that we need to disenable the automatic differentiation of T, T" and W when executing the backward pass for the auxiliary classifier. The detailed algorithm of controlling label information is given in the next section.
D.2 ALGORITIM OF CONTROLLING LABEL INFORMATION AND ADDITIONAL RESULTS OF ERM-CL
If only provide the pscudo labels for the target domain data to the auxiliary classifier, i.c. moving the second term in Eq (16), the Algorithm is the algorithm for combining any marginal alignment algorithm with controlling label information.
Even without incorporating with the marginal alignment algorithm, e.g., ERM, which case L, is removed, Algorithm still boosts the performance in practice.
Table 2 shows that ERM-CL can overall outperform the basic ERM and is close to the performance of ERM-GP.
28

---

Published as a conference paper at ICLR 2023
Algorithm 1 Controlling Label Information
Require: Source domain labelled dataset S, Target domain unlabelled dataset S Batch size b, Classification loss function &,, Marginal alignment loss function &,, Initial classifier parameter wn wo: Initial representation network parameter 0g, Learning rate y,, Lagrange multiplier X2
while wr, not converged do Update iteration: 4 t
2:
Sample Zg = [ fi= from source domain training set
4:
Sample X33 - J= from target domain training set S'x'
Compute distance from the auxiliary classifier dis + 1| w/g
6: Compute marginal alignment loss L, 1 (6,, Z4, x:))
Compute classification loss Le t 1/2 Ei=1 lo U, 2;, x()) Compute gradient:
8:
OB t V(Le + L, + dyd)s)
Update parameter: W++11 &- 1/ 17 9B. 0c+1 t 11 9B
10:
Obtain the pseudo labels V/8 + fw, (go, (x')))
Compute auxiliary classification loss Le Σ Lo (1 Oz, J v Compute auxiliary classifier gradient:
12:
JB & La
Update auxiliary classifier parameter: 11,1 < w, 17 913
14:
end while
Table 3: Ablation study on Effect of Gradient Penalty Hyperparameter.
A
0
0.1
0.3
0.5
0º 60
75.5+2.4
88.0+8.1
82.8=5.8
80.173.7
S +
92.5+0.9
93.6+1.2
93.8+1.1
93.1
D.3 ARCHITECTURES AND HYPERPARAMETERS
The network architecture in this work is the same as in Gulrajani & Lopez-Paz (2021) and Nguyen al. (2022), where a simple CNN used.
Other settings are also the same as Gulrajani & Lopez-Paz (2021) and Nguyen et al. (2022), for example, each algorithm trained for 100 epochs. To select the hyperparameters (Aı and A2) for ERM-GP. ERM-KL, KL-GP and KL-CL, we perform random search. Specifically, Y is searched between j0.1, 0.9] and A2 searched between [10 0.8). Other hyperparameters searching range could be found in the source code of Nguyen et al. (2022).
D.4 ADDITIONAL EXPERIMENTAL RESULTS
D.5 ABLATION STUDY ON THE EFFECT OF GRADIENT PENALTY HYPERPARAMETER
Our study includes an ablation analysis to investigate the impact of the hyperparameter x in the con- text of KL-GP. Specifically, conduct experiments where the source and target domains are set to 09/60" and SVHN/MNIST, respectively. Table summarizes the results. It worth noting that setting XS zero effectively reduces KL-GP to KI, and our results confirm the efficacy of including the gradient penalty term in KL-GP.
both RotatedMNIST and Digits datasets,
D.6 VISUALIZATION RESULTS
To visualize the representations of models trained using KL, KL-GP, and KL-CL, we employ t- SNE (Van der Maaten & Hinton. 2008). Figure 2 displays the visualization results when SVHN is used as the source domain and MNIST as the target domain. Our findings indicate that the incorpora- tion of additional regularizers yields slight improvement in representation alignment. However,
29

---

Published as a conference paper at ICLR 2023
(a) Visualization of KL
(b) Visualization of KL-GP
(c) Visualization of KL-CL
Figure 2: Visualization results of representations obtained by using t-SNE. The source domain (blue points) is SVHN and the target domain (red points) is MNIST.
Table VisDA17 experiments. Results of baselines are reported directly from Nguyen et (2022).
Method
Synthetic + Real
ERM
39.1
DANN
1..7
MMD
62.8#1.1
CORAL
39.5+4.5
WD
38.914.8
KL
70.6+0.5
KL-GP
71.9+0.7
KL-CL
71.3+0.4
essential note that these regularization terms are primarily designed enhance the performance of the classifier network, rather than the representation network.
D.7 RESULTS ON VISDA17
We also classification task with 280K images from 12 classes. Particularly, the synthetic images and the target domain contains real images. Table presents our experimental results. Notably, our regularization techniques, namely KL-GP and KL-CL are still capable of improving the performance of the KL guided marginal alignment algorithm to some extent.
conduct experiments on the VisDA17 dataset (Peng et al., 2017), which is a real-world domain contains
Teding Ercee
(scaled] lettny's divergence
0.8
0.6
Exnor
Accuncyy
01.8
0.2
Accuasy
211
011
101
80
100
Epoch
Proction
(a) Training Dynamic
(b) Testing Performance vs. # of Target Data
Figure 3: KL on S- The left figure is the comparison of the Jeffrey's divergence in the represen- tation space and the testing error. The right figure is the evolution testing accuracy with respect to the different fraction of unlabelled target data used for training.
30

---

Published as a conference paper at ICLR 2023
D.8 DYNAMICS OF JEFFREY'S S DIVERGENCE
The representation space version of Corollary 4.2 suggests that small Jeffrey's divergence can lead to low testing error. Figure 3a demonstrates that the dynamic of Jeffrey's divergence, as computed in the representation space, can effectively characterize the evolution of the testing error throughout the training phase. Additionally. Figure 3b reveals that the number of target data used has an impact on testing performance. Specifically, when less than half of the available unlabelled target data is used, performance increases with the number of data. However, when more than half of the unlabelled target data is used, there is only marginal improvement on performance.
31


Reviews:
[{"review_id": "vaItClzhGFd", "reviewer": "Reviewer_jaro", "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": "", "summary_of_the_paper": "This work provides UDA bounds based on the information-theoretic tools. Accordingly, new UDA methods are proposed with empirical evidence. ", "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.", "strength_and_weaknesses": "Strength:\n\n1. The theoretical analysis in Section 5 is interesting and novel to me.\n\n2. Applying SGLD to UDA, though itself is not initially developed in this paper, is novel to me.\n\n\nWeakness:\n\n1. 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. \n\n2. 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. \n\n3. Page 5: squared loss does not satisfy the triangle inequality. In fact, it satisfies the \\emph{approximate triangle inequalities} [2].\n\n4. 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].\n\n5. More detailed description is needed to understand the intuition behind $I(W;Z|X_j’)$ or $I(X_j’;Z|W)$.\n\n6. 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.\n\n7. 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.\n\n\n[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.\n\n[2] Crammer, K., Kearns, M., & Wortman, J. (2008). Learning from Multiple Sources. Journal of Machine Learning Research, 9(8).\n\n[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.\n\n\nQuestions:\n\n1. On page 5, is the random variable T’ above Eq. 4 sampled from the source or target? \n\n2. Remark 5.1, why the mutual information will vanish as $n, m \\rightarrow \\infty$ (as it is already defined over the expectation)?\n\n3. Theorem 5.1, the average over $m$ and $n$ seem unnecessary since RHS is already defined over the expectation.\n\n4. The mathematical definition of $I^{T_j’}(W;Y_i|T_i)$ is not clear to me.\n\n5. Theorem 5.3 is strange to me -- does it mean a small T will give a better generalization performance?\n\n\n\n\n", "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": "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": {}}, {"review_id": "N_DJR2_r5D-", "reviewer": "Reviewer_mqeg", "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": "", "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.\n\nThe paper considers the *empirical-to-population* (EP) generalization error in this setting, which is defined as \n$$\\textnormal{Err}(w) = R_{\\mu'}(w) - R_s(w),$$\n\nwhere $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$. \n\nTraditionally, in the domain adaptation literature, the studied error is the *population-to-population* (PP) generalization error\n$$\\widetilde{\\textnormal{Err}}(w) = R_{\\mu'}(w) - R_\\mu(w),$$\n\nsince 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\n$$\n    \\textnormal{Err}(w) = \\widetilde{\\textnormal{Err}}(w) + \\big[R_\\mu(w) - R_s(w) \\big].\n$$\n\nThe 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).\n\nThen, they use the insights obtained from the derived bounds to develop regularization strategies that result in better EP generalization error in their experiments.", "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). \n\nTo 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. \n\nFinally, the paper uses such insights to develop regularization strategies that result in better domain adaptation than previous schemes.\n\nThe 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.\n \n\n**Minor comments and nitpicks that did not impact the score of the review**\n\n* 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.\n* In the 4th line of the Preliminary, 'hypothesis space of ~~interesting~~ interest,'\n* In page 3, line 5, 'an algorithm $\\mathcal{A}$ that takes'\n* In Assumption 3: is $\\beta$-Lipschitz ~~continues~~ continuous.\n* 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}$.\n* You say that (3) is remarkable. What is remarkable about such a result? It seems reasonable and in line to the previous literature. \n* 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\". \n* In Theorem 4.5 and its proof, the Lipschitz constant should always be $\\beta$, sometimes you also write $L$.\n* There is a change in notation for probabilities in the second to last paragraph in page 8. The one starting with \"Notice that...\".\n* In the proof of Theorem 4.2 one can go from (8) to the equation after (9) directly using the triangle inequality.\n* Could you provide the exact equation or theorem for the classic VC-dimenstion generalization bound in the proof of Theorem B.1.\n* In the last line of page 18: 'might exist a ~~more optimal~~ faster convergence rate'.\n* 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)$.\n", "strength_and_weaknesses": "**Strengths**\n\n* 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.\n\n* The resulting bounds are often tighter than those in the literature and some of them provide new insights into the UDA problem.\n\n* The resulting regularization strategies obtain better results than the known schemes to improve domain adaptation.\n\n**Weaknesses**\n\n* 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. \n\n    * 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$.\n    * Section 4.2. (Theorem 4.4., Corollary 4.3, and the discussion around them) is based on *[Rodríguez-Gálvez et al. 2021]*.\n    * 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]*.\n    * 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]*. \n    * 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.\n\n* 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. \n\n* 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).$$ \nThen 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})],$$\nsuggesting 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)$.\n\n* 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$. \n\n(*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}$*.)\n\n* 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|,$$ \nhowever 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|,$$ \nwhich 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')],$$ \nand if $W$ and $X$ are related this is not true. \n\n    * 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]*.\n\n* 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.\n\n* 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}$.\n\n\n**References**\n\n*[Cover and Thomas, 2006]* Elements of information theory. \\\n*[Xu and Raginsky, 2017]* Information-theoretic analysis of generalization capability of learning algorithms.\\\n*[Pensia et al. 2018]* Generalization error bounds for noisy, iterative algorithms. \\\n*[Bu et al. 2019]* Tightening mutual information based bounds on generalization error. \\\n*[Negrea et al. 2019]* Information-theoretic generalization bounds for SGLD via data-dependent estimates. \\\n*[Germain et al. 2020]* PAC-Bayes and domain adaptation. \\\n*[Haghifam et al. 2020]* Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. \\\n*[Rodríguez-Gálvez et al. 2021b]* On random subset generalization error bounds\nand the stochastic gradient Langevin dynamics algorithm. \\\n*[Smith et al. 2021]* On the origin of implicit regularization in stochastic gradient descent. \\\n*[Rodríguez-Gálvez et al. 2021]* Tighter expected generalization error bounds via Wasserstein distance. \\\n*[Neu et al. 2021]* Information-theoretic generalization bounds for stochastic gradient descent. \\\n*[Wang and Mao, 2022]* On the generalization of models trained with SGD: information-theoretic bounds and implications.  ", "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": "DmKI-JU3eCV", "reviewer": "Reviewer_DmXB", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper use an information-theoretic framework to analyze the generalization ability of hypotheses and\nlearning algorithm of unsupervised domain adapation problem.", "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.", "strength_and_weaknesses": "Strength:\n1、The authors rigorously prove some generalization error bound. One of the bounds is associated only\nwith the learning algorithm, which is very different from other work.\n2、The author designs a new algorithm on the UDA problem based on their theory and achieves good\nresults compare to other methods in the otatedMNIST and Digits datasets.\n3、The author has relaxed the previous strong assumptions[1], so that the conclusions drawn are closer to\nthe real situation. And the author add gradient penalty based on this, which can be applied to any existing\nUDA algorithm\n[1] A. Tuan Nguyen, Toan Tran, Yarin Gal, Philip Torr, and Atilim Gunes Baydin. KL guided domain\nadaptation. In International Conference on Learning Representations, 2022. URL https:\n//openreview.net/forum?id=0JzqUlIVVDd.\n\nweakness：\n\n1、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. \n\n2、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.\n\n3、Compare to other UDA paper, this paper lack visual instructions such as t-SNE.\n\n4、The paper lacks ablation experiments with gradient penalties to demonstrate the effectiveness of this design.", "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": "AvJgVkDBI7F", "reviewer": "Reviewer_DzXY", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "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.", "summary_of_the_review": "This paper presents the novel information-theoretic generalization error bound in UDA, which significantly generalizes the existing analysis and algorithms.\nAlso, 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.", "strength_and_weaknesses": "# Strength\n-  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.\n- 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.\n- The obtained algorithm is solid based on Theorem 5.3 and seems easy to implement and improve existing methods, as shown in Table 1.\n\n# Questions and Weakness\n- 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.\n- 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?\n- The method of controlling label information requires additional memory and computation since it requires the subnetwork to generate $\\tilde{W}$.\n- 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 ?\n- 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?", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster