Information-Theoretic Analysis of Unsupervised Domain Adaptation
Authors: Ziqiao Wang
Yongyi Mao
Venue: NeurIPS 2022 Submitted (2022)
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). This study presents 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 and also inspire insights into algorithm designs. Specifically, we present two simple techniques for improving generalization in UDA and validate them experimentally.

Enformation-Theored Analysis of Unsupervised Domain Adaptation
Anonymous Author(s)
Affiliation
Address
email
Abstract
This paper uses information-theoreiic tools to analyze the generalization error unsupervised domain adaptation (UDA). This study presents 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 aggorithm-dependen and also inspire insights into algorithm designs. Specifically, we present two simple techniques for improving generalization UDA and validate them experimentally.
10
Introduction
11
12 This paper focuses on the unsupervised domain adaptation (UDA) task, where the learner is confronted with source domain and target domain and the algorithm is allowed to access to a labeled training sample from the source domain and an unlabeled training sample from the target domain. The goal to find predictor that performs well on the target domain.
14
main obstacle in such task is the discrepancy between the domains. Some recent works have [1-9] 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, most recently, Nguyen et al. [9] uses (reverse) KL divergence to measure the misalignment of the distributions of the two domains, and motivated by their generalization bound, they design an algorithm that penalizes the KI. divergence between the marginal distributions of two domains in the representation space. Despite that this "KI. guided domain adaptation" algorithm is demonstrated 23 to outperform many existing marginal alignment algorithms [10, 11, 6, 12], it is not clear whether KL-based alignment of marginal distributions is adequate for UDA, and more fundamentally what role the unlabelled target-domain training sample should play to achieve cross-domain generalization.
18
17
18
19
20
21
22
24
26 Notably, most UDA algorithms are heuristically designed and intuitively justified and most existing gegoorthmmindepeedeee
generalization bounds deeper theoretical understanding and more principled algorithm design.
Then there appears significant room for both
28
29 In this paper, we analyze the generalization ability of hypotheses and algorithms for UDA tasks using
30 an information-theoretiic framework developed in [13, 14). The foundation our bounding technique
31 is the Donsker- Varadhan representation of KI. divergence (see Lemma A. with the application of
32 sub- babb-aaussiantty (see Assumption 2). We present novel upper bounds for two notions generalization errors. The first notion ("PP generalization error") measures the gap between the population risk 34 in the target domain and that in the source domain for a hypothesis, and the second ("expected EP generalization error") measures the gap between the population risk in the target domain and the 36 empirical risk in the source domain for a learning algorithm. The specific contributions this work
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

37 are as follows. We show that the PP generalization enror for all hypotheses are uniformly bounded
38 by a quantity governed by the KL divergence between the two domain distributions, which, under bounded losses, recovers the the bound in [9]. We then show that such this KI. term upper-bounds 39
40 some other measures including Total- Variation distance [1], Wasserstein distance [6] and domain disagreement [7]. Thus, minimizing KL--divergence forces the minimization of other discrepancy measures as well. This, together with the ease of minimizing KL [9], explains the effectiveness of the KL-guided alignment approach. For expected EP generalization error, we develop several algorihm--dependen generalization bounds. These algorithm-dependent bounds further inspire the design of two new and yet simple strategies that can further boost the performance of the KL guided marginal alignment algorithms. Experiments are performed on standard benchmarks to verify the effectiveness of these strategies.
41
42
43
44
46
2
Related Work
48
49
Domain Adaptation
From a theoretical perspective, many domain adaptation generalization bounds
50
have been developed [1, 2, 15, 3, 6, 5, 7, 8], and some discrepancy measures are designed derive these bounds including the reduction of the total variation [1, 2, 15, 3]. Wasserstein distance [6], domain disagreement [7] and so on. In particular, bounds based on H&H in [2] are restricted to a binary classification setting and assume a deterministic labeling function. Furthermore, [2] also assumes the loss is the L1 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 (which could be unbounded). [16] proposed some generalization bounds based on
51
52
59
54
55
56
57
(JS) divergence, which are related our Corollary 4.2. Most existing works including 12, 16] that give upper bounds for Err, while we give upper bounds for its absolute value, |Frr|, which also serves as lower bound for generalization, highlighting some fundamental difficulty of the UDA learning task (see Corollary 4.
58
59
60
61
For more details about the domain adaptation theory, we refer readers to [17] for completed survey. From the algorithmic perspective of the domain adaptation, the most common method is to align the marginal distribution of representation between the source domain and the target domain, including using the adversarial training mechanism [10, 6, 8] and aligning the first two moments of the representation distribution [11]. There numerous other domain adaptation algorithms, and we refer readers to [18-21] ] for recent advances.
62
63
64
66
67
-effrmattonnTThoortiic Generalization Bounds Information-theored analysis are usually used to analyze the expected generalization error of supervised learning. where the training and testing data come from the same distribution [13, 22, 14, 23-27]. By exploiting the chain rule property of mutual information, these bounds are successfully applied to characterize the generalization ability of stochastic gradient based optimization algorithms [28, 24, 26, 29-31]. Recently, this framework has also been used in the multi task setting including meta- leaaning [32-35], semi-supervised learning [36, 37] and some other transfer learning problems [38, 32, 39-41]. In particular, [38. 39] consider
68
69
70
71
72
73
74 different transfer learning problem setup with ours. Specifically, their expected generalization error is
75 the gap between the target population risk and the empirical weighted risk (or the convex combination
76 of the source empirical risk and the target empirical risk), while our "EP" error is the gap between the target population risk and the source empirical risk. That is say, our work studies how make use of the unlabelled target data to improve the generalization performance on target domain except for minimizing the empirical risk of source domain, and their works assume the training objective function for the target domain data, which could be labelled, has already been known. In addition, bounds in [38, 39] fail characterize the dependence between W and Sxx.. More precisely, the algorithm-depeet dependent term in their bounds is [(W; Zz) or IW; S), while our digorithm-dependen term is X (W: Zz) that directly depends the unlabelled target data (see Theorem C.1 for more discussion in Appendix).
78
79
80
81
82
84
3 Preliminary
a5
86
Unless otherwise noted, a random variable will be denoted by a capitalized letter, and its realization denoted by the corresponding lower-case letter. Consider prediction task with instance space
87
88 2 X x y, where X' and y are the input space and the label (or output) space respectively. Let F
89 be the hypothesis space of interesting, in which each ʃ E F is function or predictor mapping X' to
90 y. We assume that each hypothesis I E F is parameterized by some weight parameter w in some
91 space W and may write f as fw as needed.
2

---

(EP) generalization error for the 92 Let i and j' be two distributions on 2, unknown to the learner. Normally, and μ' are not the
93 same and consider μز characterizing the source domain and μ' characterizing the target domain. design an algorithm A takes S and S'x' as the input and outputs 98 weight W E W. giving rise to predictor fw E F that "works well" on the target domain. Note in general characterized by a conditional distribution Pw]s,Sx/'
94 For the ease of notation, we may also write as Pz or Pxy and μ as Pz or Px'y', which also defines random variables = YX and Z = (X', Y"). Let
{Z,) ~ 1r be labeled be an unlabelled target-domain training
85
source-domain training sample and S'x' = {Xy] ~ T
96
97 sample. The objective of UDA
99
that the algorithm
100 To be precise on the performance metric of UDA, let é y x y + TRJ be loss function. Then for each weight configuration w E W, population risk in the target domain is defined as
101
Rg((w) - Ez (X'),, Y")
and good UDA algorithm hopes to return weight that minimizes this risk. Since je' is unknown, this risk can not be measured or minimized. On the other hand, one does have access to the empirical
103
risk in the source domain, as is defined by
& - n Ti
Rs(w)= Σ (X.,
105
Then the notion generalization error in this setting measures how well the hypothesis returned from the algorithm generalize from the source-domain training sample to the targer-domain unknown distribution μ'. Taking into account the stochastic nature of the algorithm A, natural notion of generalization error for UDA can be defined by
106
107
108
Err Ew.s [R (W) Rs (W)] = Ewss,s (R) - Rs()),
(1)
109
where the expectation in the first equation taken over the joint distribution of (W.S) P sxp2n and the expectation of the second equation is taken over the joint distribution (W, 5x.))
eustetiooonn
110
111
Pwis,sy,
x 28n pdmm
Note that there is another notion of generalization error, more traditional in the domain adaptation literature, namely, the gap between the population risk in the target domain and that in the source domain, as define by
113
114
Err(w) & Ry RR,(w).
(2)
where (w) & [f Y)). is apparent that Err(w) and Err are related by the following triangle inequality: RR (w) (s( I (w)((w) - (wx + (w) - (s)l))
115
116
where the second term on the right hand side is the standard generalization error in the source domain, which can be bounded by classical learning-theowd thcoretic tools, e.g., Rademacher complexity [42]. Thus bounding Err(w) helps bounding Err.
118
119
This paper studies both notions of generalization error for UDA. Specifically, starting from Section 5, we will mainly use information -thooreticcc tools bound Err directly, without going through Err(w). For the ease of reference, we refer to Err(w) as the rapulation-to-pooulatioo (PP) generalization error for w and Err the expected algorithm A.
121
122
123
124
Some definitions are prerequisite in this paper, now present some uncommon notions and defer the common notions to Appendix.
126
127
Definition 1 (Disintegrated Mutual Information). Let X, Y and Z be random variables and be realization of Z. The disintegrated mutual information of X and Y given Z is (x(; & DKL (Px,y 11 P )2=)).
128
129
Note that the conditional mutual information Y(X; =11
Definition& 2 (Lautum Information [43]). Define the lautum information between X and Y as
L(X;Y) 2 (x
132
3

---

133
4
Upper Bounds for PP Generalization Error
In this section, we present some upper bounds for Err(w)) The key techniques used in developing these bounds are the information-tin -theorrttt tools in the style of Lemma A. All these bounds adopt certain KL. divergence as a key quantity measuring the discrepancy between the source and target domain. Notably, some previously established bounds are recovered under a different assumption of the loss function. Additionally we demonstrate that under certain conditions, the KL-based bound an upper bound of many other discrepancy measures and hence minimizing the KL divergence forces the minimization of these other measures.
134
135
136
138
140
141
We first list some common assumptions on the loss function, which we consider in this paper.
142
Assumption (Boundedness). E(..-) is bounded in [).
143
Assumption (Subgaussianity). (X), Y) is R-subgaussian' under i for any w E W.
Remark 4.1. Note that Assumption I implies Assumption 2, i.e., if (ff is bounded in [0, M].
145
then it is also M /2/-subgaussian Thus, Assumption 2 is weaker than Assumption 1.
146
Assumption 3 (Lipschitzness). (X)( is B-Lipschitz continues in Z for any w E W, i.e.
(z1), v1) - (x2 3221 S 22).
148
Remark 4.2. Note that Assumption implies Assumption 3 when d is a discrete metric, i.e., if
(X), Y) is bounded in [0, M). then is also M M-Lisshhitz under the discrete metric.
149
150
Assumption 4 (Triangle). ((.,)) satisfies the following the triangle inequality: fly,, (())92)= S E(y1.
151
yys, y2) for any y1. V2, ys E y.
152
4.1
Generalization Bounds via the Subgaussian Condition
153
The following generalization bound is established by combining Lemma A. I and Assumption 2, technique developed in [14] for tnformation-thcoretiic analysis of generalization.
154
Theorem 4.1. If Assumption holds, then for any w E W, Err(w)) S /2r=Dkr
155
156
We note that this result on one hand can be turned into generalization upper bound providing guidance to algorithm design, and on the other hand provides a lower bound of the generalization error, which highlights some fundamental difficulty of the learning task. To illustrate this, we present an corollary of Theorem 4.1, while noting that similar development can also be applied to other bounds presented later this paper.
157
158
159
160
161 To that end, suppose that each fwr in the model family is expressed as the composition g o h, where h a function mapping X' to representation space T and g is a function mapping T to Jr For any given h X > T, denote by μt, the distribution on T x y obtained by pushing over via h, that is,
162
163
pn (t. v) = f 6(t h(()) (d)() y), where is the Dirac measure on T. Similarly, let μl, denote the distribution on T x y obtained by pushing over p' via h.
164
185
186
Corollary 4.1. Suppose that fw go h and that Assumption 2 holds. then for any w E W,
(u) 22RDDKL S (w) S Rw) + / 2 (14
In this result, the lower bound of Ry (10) indicates a fundamental difficulty in UDA learning in that, using the same predictor mapping fwo there is way for the population risk in the target domain to be lower than that of the source domain less a constant which depends only on the domain difference. On the other hand, the upper bound suggests that it is possible squeeze the gap between the two population risks by choosing an appropriate representation map /- evidently such a map should be
167
169
170
171
172
attempting to align 14, with μt or align their respective proxies.
173
is also remarkable that under Assumption and due to Remark 4.1, Theorem 4.1 implics
M
Err(w) S
V DKL
PPx) + DEL (Prip:
V2
174
Similarly applying this result in the representation space T, we see that Eq. (3) recovers the bound in Proposition I of [9]. Notice that unlike [9], Theorem 4.1 (or Eq. (3)) does not require the loss to be the cross entropy loss.
175
176
A random variable X is R-subgaussian if for any p. log E Exxp (p - EX)) S H2 /2.

---

Theorem 4.1 and [9] both use the KL divergence from source domain to target domain, DRL(F (lll,), and in fact, [Er(ww) can also be upper bounded by DRr (ulla)))) This can be done by invoking the subgaussianality of (X"),,) Y") (rather than (ff( Y)); for bounded loss, the subgaussianality of (ff((()), Y") is also satisfied. Then we obtain the following corollrry
177
178
179
180
Corollary 4.2. If Assumption I holds, [Er((W)
M
minnDDui((llll)) (Rkalddll))) s
181
M VDLL (rllee) + (eK(((lll))
182
2
Remark 4.3. In the second inequality of Corollary 4.2, (ucll)ll))) + DKL [pp) is usually called
189
184
the symmetrized KL divergence (or Jeffrey's 's divergence [44]), and the regularization term used in
[9] is indeed the symmetrized KL divergence between the distributions of the source and target representations. Notice that bounds in [16] are based on the JS divergence. Since there is a sharp upper bound of the JS divergence based on Jeffrey's 's divergence [45], minimizing Jeffrey's 's divergence (in the representation space) will simultaneously penalize the JS divergence.
185
186
187
188
189
In UDA, since Y' is completely unavailable to the algorithm A, it is impossible to minimize the misalignment of conditional distributions, i.e. DKL (P IPrr)), without any additional infor- mation. A common method is to assign pseudo labels to target data. However, it may also cause
190
191
192
some additional issues. For concreteness, suppose the trained model Q can well approximate the
193
real mapping between X and Y on source domain (i.e. Qrir = Py(r), which is usually the training
objective. Let Y be the pseudo label of T' generated by the trained model, i.e., Quir = Qyir- Let
194
195
Qr = Puip, then the following holds.
Pr",y' DKL (Prr (Irx)) = Epy,y log Qr Qr.pp.ry
+ DKL (Pr)p
(4)
For a specific t', if P(Y' 8/1' = t²) * and P( s/T'' =t) = O, then the second term in RHS of Eq. (4), DKT.
196
197
p()r)) - co. In this case, even the marginal distributions are perfectly aligned, the overall value of the upper bound is large. Thus, incorrect pscudo labels may even have negative impact on the target domain performance, and we hope two supports, Supp(Py:) and Supp(P} (Pp.p(P)) Py)., could largely overlap with each other for every target data.
199
201
Indeed, the misalignment of the conditional distributions appears to be the main difficulty of UDA [1, 8). 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 satisfied by the
202
203
0-1 loss and square error loss; this assumption has also been considered in previous works [3, 6].
205
Theorem 4.2. If Assumption 4 holds and let f(fw (X), (X)) be R- R-subgaussian, for any w, w/ E W.
206
Then for any w, Err(w)= S D2R2DKL(Pxx) [x) + X", where X = min Ry (w) + (w))
207
In this theorem, X measures the possibility of whether the domain adaptation algorithm will succeed under the oracle knowledge of μ and μ². In particular, if the hypothesis space is large enough, the minimizer w" for the "joint population risk" RB (w) + (wr may give rise to R2 (w*)
208
209
RB (w=) 0. then we're likely to generalize well the target domain. Then the KL divergence 210
211
(x [Px) between the two X' X-marginals alone bounds the PP generalization error uniformly
212
for all w W.
This theorem motivates the strategy of penalizing DKL (Pr P(.)) in the representation space to
213
achieve better generalization error. The next theorem suggests that such an approach also penalizes other notions of domain discrepancy, for example, domain disagreement defined in [7, Definition 1.]
215
216
and serving a key quantity in the PAC-Bayes type of domain adaptation generalization bounds [7]:
dis( Px, Px:) A [w,,", [[(ff (X'), fwr fx') Ew,w',x x [e(fw (X), fwr (X)]l- (5)
217
Theorem 4.3. If e(F (X)) is R-subgaussian for any w, w E H. then dis (xx, Pxx,Pxx) Px.) S
218
V 2R.
219
Note that unlike [7], here we do not require the loss function to be the 0-1 loss.
220
4.2
Generalization Bounds via the Lipschitz Condition
Wasserstein distance based generalization bound are often directly connected to, or even included
222 in, the information-theorees bounds [46, 27]. We now present such a bound for UDA under the Lipschitz continuity assumption of the loss function.
5

---

Theorem 4.4. If Assumption holds, then Err(w) S (w(,', nt)
224
225
Note that Theorem 4.4 can be related to the KI. divergence based bounds in the previous section when the Wasserstein distance is defined with respect to the discrete metric d. In this case, if the loss function is bounded, it is also Liptschitz continuous, and hence Theorem 4.4 applies. On the other
228
227
228
hand, Wasserstein distance is equivalent to the total variation distance [1, 2, 15, 3], while the latter is
229
connected to the KL. divergence via Pinsker's inequality [47, Theorem 6.5] and the Bretagnolle-Huu Huber inequality [48, Lemma 2.1]. Thus we arrive at the following result.
230
231
Corollary 4.3. If Assumption holds holds and let d be the discrete metric, then
Err(w) - MMTV(L' 10) s M min {
232
The bound in Corollary 4.3 can be immediately verified to be tighter than the bound in Eq. (3).
233
Parallel to Theorem 4.2, if the loss function satisfies the triangle property, we may establish another bound below, which recovers similar result in [6, Theorem 1.].
235
Theorem 4.5. If Assumption 4 holds and (X). fw (X)) is 3-Lipschitz in X for any w, w' E W, then for any w E W. Err(w) S LW Px) + X², where X min Ryc(w) + (y))).
236
237
Unlike the bound in [6], we do not require the classification tasks to be binary in Theorem 4.5, and the loss does not need to be the L1 distance.
238
239
This section may convey the following message. Since the KL divergence based bounds upper- bounds those based on other measures of domain differences, (e.g. total variation distance, domain discrepancy etc), if we penalize the KL divergence, we will also penalize those other measures. This is practically advantageous since it is usually easier and more stable to minimize the KL divergence[9).
241
242
Upper Bounds for Expected EP Generalization Error and Applications
243
244
There are two limitations in the bounds on the PP generalization error developed in the previous section and in the traditional analysis of domain adaptation. First, such bounds are independent of w and hence algorithm-indee independent. Second, although these bounds may inspire strategies to exploit the unlabelled target sample, e-g., aligning its marginal distribution with that of the source sample the representation space, they only provide very limited knowledge on the role that the unlabelled target sample plays in the algorithm. We now derive upper bounds for the EP generalization error, which better utilize the dependence of the algorithm output on the unlabelled target data. Applications of these bounds in designing the learning algorithms are also presented.
245
246
247
249
250
251
252
5.1
Bounds
253
Theorem 5.1. Assume ((fu(X'),Y) is R-subgaussian under ye' for any w E W. Then
Err| S 71772
1
ΣV
m
Σ
x
E Ex 2RV + (Vl:::)>++////2/// (2Rl)x
254
1=1
255
Remark 5.1. Note that the unlabelled target data plays a role in the first term of the bound. Indeed,
more source and target data will reduce the first term of the bound. Specifically, moving the expectation inside the square root function by Jensen's 's inequality and since Z, 11 X3. the equations
257
258
I(W; Xx)) = I(W; Zx)x + ((2; = I(W; Z,) + +XX;: Z.IW) hold by the chain rule. The term I(W; Z,) will vanish as n > oo and the term I(X;; Z.(W) will also vanish as n. m - 00.
259
280
is also worth mentioning that, from a practical perspective, the number of samples may have different impact on the different algorithms. For example, the second term (KL divergence) in our Theorem 5.1 can not be computed in the original space and we can only estimate it in the representation space. On the one hand, it seems that having more data will make the approximation
261
262
263
254
(f KL between marginal distributions) more accurate. While on the other hand, some domain adaptation algorithms involve the pseudo labelling process, and assigning incorrect pseudo labels to
286
the target data may even have negative impact on the target domain performance (as discussed in Section 4). In this case, having more target data will not improve the performance.

---

268
Corollary 5.1. Let Assumption I hold. Then
|Err|= <
M.
Exy min {
J M v min (DKu(ulle DKlllll)))
V2nm j=li=1
where L ((3-) is the disintegrated version of Lautum information.
270 Theorem 5.2. Assume is Lipschitz for both w E WW and = E 2, Le., (e(f( - -[f))((((( (((((")))))
Bdg (2, 2)) for all 2, 2 Z and (e(f.())),) ((fww()))))))))))))))))))(())) v) 3/ d2 w for all w, wt E W, then
B
11
a
Errl
Ex,,,, W(WW2.,P Pwix)) Pwix;) + ( (w(,,
THTT
272
This bound is tighter than the bound in Theorem 5.1, can be indicated by the following corollary. Corollary 5.2. Let Assumption hold. Then
273
Err
M
Ex
( + MTV(u,
nmm
1=1
170
M
DRL (PI((,2,x; + V (el(H)
M
Ex Ex
Tem
2
2
274
Notice that to recover Theorem 5.1 from Corollary 5.2, we can use Jensen's 's inequality move the expectation over Z: inside the convex square root function.
275
276
5.2
Gradient Penalty as an Universal Regularizer
The algorithm-depender bound in Theorem 5.1 tells us that one reduce the expected generaliza- tion error by limiting the disintegrated mutual information X (W; Z.). In the stochastic gradient based optimization algorithms, this term can be controlled by penalizing the gradient. To see this, we now consider "noisy" iterative algorithm for updating W, e.g., SGLD. At each time step let the labelled mini-batch from the source domain be ZB, let the unlabelled mini- batch from the target
278
279
280
281
282
domain be X and let g -- ZB, : X¹s,) be the gradient at time t. Thus, the updating rule of W
W. = W Thgg( W,,,, ZB, x²,)) ) + N₂ where т/e is the learning rate and N, ~ (O, o²Ia) is an isotropic Gaussian noise. The next theorem is an application of Theorem 1.1 in this setting.
285
285
Theorem 5.3. Let the total iteration number be T and let Gt = 9 ZB Xb,). then
R2 n
T Eg x Wi 1.S [[G/]|]] (V 2R2
EEr| <
Remark 5.2. Considering a noisy iterative algorithm here is simplify analysis. In fact it is also
287
possible to analyze the original iterative gradient optimization method without noise injected. For example, one can follow the same development [30, 31] to analyze vanilla SGD. In that case, there will be some additional terms in the bound, which are related to flainess of the found minima.
288
289
290
Theorem 5.3 hints that reduce the generalization error, one can restrict the gradient norm each
281
step. This strategy will also restrict the distance between the final output Wr and the initialization Wo. effectively shrinking the hypothesis space accessible by the algorithm.
282
293
Indeed, adding gradient penalty can be applied to any existing UDA algorithm and it is simple but effective in practice. Later on will show that even when the algorithm A does not access to any target data, in which case [[W; Z) reduces to [(W; Z.) and gWW,11; ZB, X²z,) becomes - B. minimizing the empirical loss of source domain sample while penalizing gradient
295
296
norm will still improve the performance. Notice that gradient penalty is also used in Wasserstein distance based adversarial training [49, 6], and their motivation is to stabilize the training to avoid gradient vanishing problem while here we it improve the generalization performance directly.
298
289
300
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

---

302
consider the mutual information as the expected KL divergence of posterior and a prior, based
on (W; Z,) in Theorem 5.1, it is possible to create target data dependent prior and derive tighter bound based on some quantity similar to "gradient incoherence" in [24]. As this will introduce
304
additional complexity in practice, leave this as a future study.
306
5.3
Controlling Label Information for KL Guided Marginal Alignment
307
Consider instances in the representation space, Z = (T, Y) and Z' = (T),)). Theorem 5.1 also encourage us to align the distributions of two domains in the representation space, argued earlier. Then the KI. guided marginal alignment algorithm proposed in [9] can be invoked here. One may notice that Theorem 5.1 uses Drt(ulle² while [9] uses DKL (xu (и'lla). As already discussed in Section 4, this inconsistency can be ignored when loss is bounded (see Corollary 5.1).
308
309
311
312
Most domain adaptation algorithms aim to align the marginal distributions of two domains in the representation space. However, without accessing Y', remains unknown if an UDA algorithm will work well since we cannot guarantee that discrepancy between conditional distribution Pyir and PripT won't become too large when we align the marginals. In [9]. the authors show that (P Py can be upper-bounded by DKL(4Py:) | [| ). if I(X;))
313
314
315
316
(();Y). The authors then argue that penalizing the KL divergence of the marginals distributions is safe.
317
We now argue that in practice the condition YX;Y) YT; can be difficult to satisfy if the cross entsrpy loss is used to define the source-domain empirical risk.
319
320
By data processing inequality on Y- -T, we know that [(X;)) 2 Thus, to let TTT; Y) reach maximum, one must minimize (Y[T). On the other hand, let @T/T.W W be the predictive distribution of labels in the source domain generated by the classifier. The expected
321
322
323
cross-entropy loss for each Z; in the representation space is then
Ew,z, [R(fw (T;), Yi) Ez, EE Zu | log Qrqr..wl.
324
which also decomposes as [50, 51]
Ew,z, ((:W((T)) YJ) = H(V[T:)) + By,w
[Qaan. - 1(W; Y.(.). (6)
325
Then minimizing the expected cross-entropy loss may not adequately reduce (Y, but rather cause I(W; [T)) to significantly increase, particularly when the model capacity is large. This may have two negative effects. First, the condition I ((;Y) = I(T;Y) is significantly violated, and DKL. (P l is no longer upper bounded by DRL. (Py l x). As consequence, aligning the two marginals alone may not be adequate. Second, large I(W; Y(JT;) indicates W
327
329
330
just simply memorizes the label Y, resulting a form of overfitting and hurting the generalization performance.
332
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 generalization. similar message can also be deduced from Theorem 5.1, when it is viewed in the repsentation space and noting / (W; 7,) = TTh (W; + ITH (W; (Y(.).
333
334
335
336
To control label information, [51] proposed an approach called LIMIT. However this method is rather complicated and arguably hard to train in domain adaptation (see Appendix). We now derive simple alternative strategy for this purpose.
337
338
Notice that (W; Y/IT)) < info Er. (P(W),,, =II, =t))), which is simple extension of variational representation of mutual information [47, Corollary 3.1.j. Here Q could be any distribution. By assuming P = NW(,,o"lalY, T. = tn) and taking Q =
339
340
341
NWW T T;, T3- 12),, we have
342
IT's (W; YIT.) < inf Er. [DKL(P(WIX, T, - -7 Q)) = x I|W - 21
auxiliary classifier für 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 fw to train fa and adding !|W - W112 as a regularizer in the training of W. The algorithm is given in 346 the Appendix. Remarkably the regularizer here resembles "Projection Norm" designed in [52] for oft-o--distribution generalization.
Thus, may
344
8

---

Table I: RotatedMMNSS and Digits Experiments. Results of baseline methods reported from [9].
RotatedMNIST (0" as source dommin)
Digits
Method
15
30"
45
60
75
Ave
M
U
U + M
S -+ M
Ave
ERM
97.540.2
84.120.8
53.920.7
34.2s0.4
22.3=0.5
58.4
73.124.2
54.826.2
65.921.4
64.6
DANN
97.340.4
90.611.1
68.724.2
30.840.6
19.0=0.6
61.3
90.720.4
91.240..
71.1
84.3
MMD
97.540.1
95.3+0.4
73.6+2.1
44.2+1.8
32.1=2.1
68.6
91,8+0.3
94,4x0.5
82.840.3
89.7
CORAL
97.1+0.3
82.3+0.3
56.0#2.4
30.8+0.2
27.1=1.7
58.7
88.0#1.9
83.3+0.1
69.3+0.6
80.2
WD
96.720.3
93.121.2
64.123.3
41.427.6
27.622.0
64.6
88.220.6
60.2+1.8
68.422.5
72.3
KL
97,8+0.1
97.1+0.2
93,4+0.8
75.5+2.4
68. 181.8
86.4
98,2+0.2
97,3+0.5
92.5+0.9
96.0
ERM GP
97.540.1
86.240.5
62.0#19
34,8+2,1
26.1=1.2
61.2
91.3+1.6
72.7+4.2
68.420.2
77.5
KI-GP
98.2+0.2
96.9+0.1
95.0+0.6
88.048.1
78.1=2.5
91.2
98. 88..+
97.8+0.1
93.8+1.1
96.8
KL-CL 98.4+00.
97.3+0.2
95.6+0.1
83.0+8.2
73.624.0
89.6
98.9=0.1
97.7+0.1
93.0#0.3
96.5
6
Experimental Results
348
349
We now perform experiments to verify the proposed techniques inspired by our theory in the previous section. The experimental setup follows that [9].
350
351
We select two popular small datasets, RotatedMNIST and Digits, to compare the different methods. In particular, RotatedMNIST built based on the MNIST dataset [53] and consists of six domains with each domain containing 11, 666 images. These six domains are rotated MNIST images with rotation angle 0% 15 30 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 [54] and SVHN [55], and the corresponding domain adaptation tasks are MNIST~USSPS (S-M).
Datasets
352
353
354
355
356
358
MM U), USPS MNISS (U-M),
Compared Methods Baseline methods are some popular marginal alignment UDA methods
360
including DANN [10), MMD [12], CORAL [11], WD [6] and KI. [9]. We also choose ERM for another baselin in which the algorithm can only access to the source domain sample during training.
362
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.
364
386
Implementation Details Most part of the implementation is based on the famous DomainBed suite [56]. Other settings exactly the same with [9] and the results of baseline methods are reported directly from [9]. Specifically, each algorithm is run three times and we show the average performance with the error bar. Every dataset has a 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 Domainßed suite. Other details and additional experiments can be found in Appendix.
368
370
372
373
From Table 1, first notice that gradient penalty is able help ERM to be more comparable with 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, we can see that the performance can be further boosted. This justifies the discussion in Section 5.2 and Section 5.3.
Results
374
375
378
377
378
7
Conclusion
379
Despite that the numerous learning techniques have been developed for domain adaptation, significant room exists for more in-depth theoretical understanding and more principled design of learning algo- rithms. This paper presents the information-
380
381
analysis for unsupervised domain adaptation, where we query two notions of the generalization errors in this context and present novel learning 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
382
383
384
representation space. Our other bounds are sesoritmm-dependen better exploiting the unlabelled
386
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.

---

References
388
389
[1]
Shai Ben-David. John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation, Advances in neural information processing systems, 19, 2006.
[2] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Machine Learning, 79 (1-2):151-175, 2010.
392
[3] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In The 22nd Conference on Learning Theory, 2009.
395
396
[4] Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon. On learning invariant representations for domain adaptation. In International Conference on Machine Learning, pages 7523-7532. PMLR, 2019.
398
399
[5]
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. In International Conference on Machine Learning, pages 7404-7413.
400
401
PMLR, 2019.
402
[6] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. In Thirty-second AAAI conference on artificial intelligence, 2018.
403
404
405
[7] Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant. Pac-bayes and domain adaptation. Neurocomputing, 379:379-397, 2020.
406
88]
David Acuna, Guojun Zhang, Mare T Law, and Sanja Fidler. f-domain adversarial learning: Theory and algorithms. In International Conference on Machine Learning, pages 66-75. PMLR, 2021.
408
409
410
[9] A. Tuan Nguyen, Toan Tran, Yarin Gal, Philip Torr, and Atilim Gunes Baydin. KL guided domain adaptation. In International Conference on Learning Representations, 2022. URL https:/
411
412
413
[10] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversate training of neural networks. The journal of machine learning research, ((1):2299-20300 2016.
414
415
416
Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation. In European conference on computer vision. pages 443-450. Springer, 2016.
417
418
[12] Haoliang Li, Sinno Jialin Pan, Shiqi Wang, and Alex C Kot. Domain generalization with adversarial feature learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2400-5509, 2018
419
420
421
[13] Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics. PMLR, 2016.
422
423
[14] Aolin Xu and Maxim Raginsky. iiformation-theoreti analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 2017.
424
425
[15] 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, pages 129-136. JMLR Workshop and Conference Proceedings, 2010.
426
428
[16] 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.
429
[17] levgen Redko, Emilie Morvant, Amaury Habrard, Mare Sebban, and Younes Bennani. A survey on domain adaptation theory. arXiv preprint arXiv:2004.11829, 2020.
432
433
[18] Gabriela Csurka. Domain adaptation for visual applications: comprehensive survey, arXiv preprint arXiv: 2017.
10

---

435
[19] Garrett Wilson and Diane J Cook. A survey of unsupervised deep domain adaptation. ACM
436
Transactions on Intelligent Systems and Technology (TIST), 11(5):1 2020.
[20] Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization: survey, arXiv e-prints, pages arXiv-2103, 2021.
438
[21] Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Wenjun Zeng, and Tao Qin. General- izing to unseen domains: A survey on domain generalization. arXiv preprint arXiv:2103.03097, 2021.
440
442
[22]
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.
444
[23] Yuheng Bu, Shaofeng Zou, and Venugopal V Veeravalli. Tightening mutual information based bounds on generalization error. In 2019 IEEE International Symposiun on Information Theory (ISTT), pages 587-591. IEEF, 2019.
446
[24] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Information-theeretie generalization bounds for sgld via data-dependent estimates. Advances in Neural Information Processing Systems, 2019.
448
449
450
[25] Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory. PMLR, 2020.
451
452
[26] 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.
453
454
455
[27] 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.
456
457
28 Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT). IEEE, 2018.
459
[29] Hao Wang, Rui Gao, and Flavio P Calmon. Generalization bounds for noisy iterative algorithms using properties of additive noise channels. arXiv preprint wxXiv2210.002970 2021.
461
[30] Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M Roy. Information- theoretic generalization bounds for stochastic gradient descent. In Conference on Learning Theory. PMLR, 2021.
463
485
[3]] Ziqiao Wang and Yongyi Mao. On the generalization of models trained with SGD: Information- theoretic bounds and implications. In International Conference on Learning Representations, 2022. URL https: http:///pppeeeeeeeeeee wttp:/iwww...eeeeeeeeeeeeeeeee mett/forum/dd-oo2zaBB655
487
[32] Sharu Theresa Jose and Osvaldo Simeone. Information-thhoreti generalization bounds for meta-learning and applications. Entropy, 23(1): 2021.
489
470
[33] Sharu Theresa Jose, Osvaldo Simeone, and Giuseppe Durisi. Transfer meta-learning:
471
information-theorette bounds and information meta-risk minimization. IEEE Transactions on Information Theory, 68(1):474-501, 2021.
472
473
[34] Arezou Rezazadeh, Sharu Theresa Jose, Giuseppe Durisi, and Osvaldo Simeone. Conditional mutual information- based generalization bound for meta learning. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 1176-1881. IEFF, 2021.
474
475
476
[35] Qi Chen, Changjian Shui, and Mario Marehand. Generalization bounds for meta-learning: An inforration-theorrtie analysis. Advances in Neural Information Processing Systems, 34, 2021.
477
478
[36] Haiyunn He, Hanshu Yan, and Vincent YF Tan. Informatioon generalization bounds for iterative remi-supervised learning. arXiv preprint arXiv:2110.0092: 2021.
11

---

480
[37] Gholamali Aminian, Mahed Abroshan, Mohammad Mahdi Khalili, Laura Toni, and Miguel Rodrigues. An information-thorreee approach semi supervised learning under covariate- shift. In International Conference on Artificial Intelligence and Statistics, pages 7433-7449. PMIR, 2022.
481
483
484
[38] Xuetong Wu, Jonathan H Manton, Uwe Aickelin, and Jingge Zhu. Information - analysis for transfer learning. In 2020 IEEE International Symposium Information Theory (ISIT), pages 2819-2824. IEEE, 2020.
486
487
[39] Sharu Theresa Jose and Osvaldo Simeone. Informatiin-theerrtiic bounds on transfer general- ization gap based on jensen-shannon divergence. In 2021 29th European Signal Processing Conference (EUSIPCO), pages 1461-1465. IEEE, 2021.
488
489
490
[40] Mohammad Saeed Masiha, Amin Gohari, Mohammad Hossein Yassaee, and Mohammad Reza Aref. Learning under distribution mismatch and model misspecification. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 2912-2917. IEEE, 2021.
491
[41] Yuheng Bu, Gholamali Aminian, Laura Toni, Gregory W Wornell, and Miguel Rodrigues. Characterizing and understanding the generalization error of transfer learning with gibbs algorithm. In International Conference Artificial Intelligence and Statistics, pages 8673- 8699. PMLR, 2022.
494
496
497
[42] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 36N04):4 2002.
498
499
[43] Daniel P Palomar and Sergio Verdú. Lautum information. IEEE transactions on information theory, 54(3):964-977 97664 2008.
500
[44] 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):
502
453 13-4461,1 1946.
504
[45] Gavin E. Crooks. Inequalities between the jenson-shannon and jeffreys divergences. In Tech. Note 004, 2008
505
506
[46] Hao Wang, Mario Diaz, José Cândido S Santos Filho, and Flavio P Calmon. An information-
507
theoretic view of generalization via wasserstein distance. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 577-581. IEEE, 2019.
508
[47] Yury Polyanskiy and Yihong Wu. Lecture notes information theory. Lecture Notes for 6.441 (MIT), ECE 563 (UIUC), STAT 364 (Yale), 2019., 2019.
510
511
[48] Jean Bretagnolle and Catherine Huber. Estimation des densités: risque minimax. Zeitschrift für Wahrschhinnichhketssteeor und verwandte Gebiete, 47(2):119-137) 1979.
513
[49]
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. Advances in neural information processing systems, 30, 2017.
514
515
516
[50] Alessandro Achille and Stefano Soatto. Emergence of invariance and disentanglement in deep representations. The Journal of Machine Learning Research, 1917:1947-1980, 2018.
517
[51] Hrayr Harutyunyan, Kyle Reing, Greg Ver Steeg, and Aram Galstyan. Improving generalization by controlling aabel-noise information in neural network weights. In International Conference on Machine Learning, pages 4071-4081. PMLR, 2020.
519
[52] Yaodong Yu, Zitong Yang, Alexander Wei, Yi Ma, and Jacob Steinhardt. Predicting out-of- distribution error with the projection norm. arXiv preprini arXiv:2202.05833, 2022.
522
523
[53] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.l www.w.e..coooo.. com/exdb/nnistt 2, 2010.
524
525
[54] Jonathan Hull. database for handwritten text recognition research. IEEE Transactions on pattern analysis and machine intelligence, 16(5):550-554, 1994.
12

---

527
[55] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. NeurIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
528
530
[56] Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representations, 2021. URL id=10dXeXDoWtI.
531
[57] XuanLong Nguyen, Martin J Wainwright, and Michael Jordan. Estimating divergence func- tionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56( 11:8847-586,, 2010.
534
[58] Jiantao Jiao, Yanjun Han, and Tsachy Weissman. Dependence measures bounding the explo- ration bias for general measurements. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 1475-1479. IEEE, 2017.
537
[59] Rohit Agrawal and Thibaut Horel. Optimal bounds between f-divergenees and integral prob- ability metrics. In International Conference on Machine Learning, pages 115-124. PMLR, 2020.
540
[00] Villani Cédric. Optimal Transport: Old and New (Grundlehren der mathematischen Wis- senschaften, 338). Springer, 2008
543
544
[6
Clément L Canonne. A short note on an inequality between kl and tv. arXiv preprint arXiv:2202.07118, 2022.
545
548
622]
Vladimir Vapnik. Statistical learning theory. Wiley, 1998. ISBN 978-0-471-03003-4
547
[63]
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecom- munications and Signal Processing). Wiley-Interscience,, USA, 2006. ISBN 047124195 1241954.
548
549
[64]
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, sigh-performance deep learning library. Advances in Neural Information Processing Systems, 32:8026-808 8037, 2019.
550
551
552
553
[65] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint 1:Xiv:1312.611,, 2013.
554
Checklist
555
556
1. For all authors...
557
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
559
(b) Did you describe the limitations of your work? [Yes] See Section
560
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is theoretical work and we do not see any potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
563
584
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] e.g., see Section 4.
566
587
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices.
568
3. If you ran experiments..
589
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See Section and supplemental material.
570
571
572
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6 and Appendices.
13

---

574
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Table 1.
575
576
(d) Did you include the total amount compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendices.
578
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
579
(a) If your work uses existing assets, did you cite the creators? [Yes]
580
(b) Did you mention the license of the assets? [Yes] See Appendices.
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
582
583
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
585
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
587
5.
If you used crowdsourcing or conducted research with human subjects...
588
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
590
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
593
14


Reviews:
[{"review_id": "fZR5yjFapd", "reviewer": "Reviewer_VJaj", "summary": "The paper provides two types of information-theoretic bounds for unsupervised domain adaptation. The first is the PP generalization error, which bounds the gap between the source population risk and the target population risk. The second is the expected EP generalization error that bounds the expected gap between the target population risk and the source empirical risk. The PP generalization error is connected to the KL divergence-based marginal distribution matching method. And the EP generalization error bound is algorithm-dependent and intrigues two simple approaches that improve the KL method on rotated MNIST and digits dataset. ", "questions": "### Major Concerns\n\n1. Equation (1) in the main paper seems problematic. $E_{W,S}[R_{\\mu^\\prime}(W) - R_S(W)]$ equals to $E_{W,S,S^\\prime_{X^\\prime}}[R_{\\mu^\\prime}(W) - R_S(W)]$ when $W,S$ and $S^\\prime_{X^\\prime}$ are independent. However, $W=\\mathcal{A}(S, S^\\prime_{X^\\prime})$ for UDA. \n\n2. The first equation in Appendix Line 678 is unclear to me. \n\n\n### Minor concerns\n1. The subguassian assumption of loss function should be related to the specific distribution, for $(X,Y)\\sim\\mu$ and $(X^\\prime, Y^\\prime)\\sim\\mu^\\prime$. Assumption 2 is w.r.t. $\\mu$, while Theorem 5.1 is w.r.t $\\mu^\\prime$.\n2. Line 112, typo PP -> EP", "limitations": "Yes, the authors have claimed that this work does not touch upon the fundamental difficulty in UDA or the lower bounds of generalization errors.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nThe whole paper is well-written and easy to follow. And the proposed algorithms seem to boost the performance of KL-divergence-based marginal distribution matching methods on the two datasets. \n\n### Weakness\n\n1. The originality and significance of the work are not obvious\n\nThe PP generalization bound related to KL divergence is actually a similar version to the JS divergence bound of [1]. \nBoth the PP and EP bound are related to the KL divergence of the two domain distributions $\\mu, \\mu^\\prime$. However, this term is fixed and irrelevant to the algorithm given the domain distributions. Even though the paper mentioned some insights for learning the representation via minimizing the KL divergence, no rigorous theoretical analysis is provided.\nThe fundamental difficulty of UDA is not studied in this paper, e.g., the theoretical validity of the pseudo label. \n\n2. Not enough related work discussion\n\nThe paper is highly related to [2] and [3], which also studied UDA with information-theoretic tools, but no discussion is provided. \n\n3. Experimental evaluation is not adequate\n\nThe proposed algorithms (gradient penalty/controlling label information) in fact add a regularization for learning the source domain to avoid overfitting and improve cross-domain generalization.  Similar approaches exist in previous works like [1], but no comparison is conducted. \n\n4. Technique Concerns\n\nSee the questions in the following section.\n\n[1] Shui, C., Chen, Q., Wen, J., Zhou, F., Gagné, C. and Wang, B., 2020. Beyond H-divergence: Domain adaptation theory with Jensen-Shannon divergence.\n\n[2] Wu, Xuetong, et al. \"Information-theoretic analysis for transfer learning.\" 2020 IEEE International Symposium on Information Theory (ISIT). IEEE, 2020.\n\n[3] Jose, Sharu Theresa, and Osvaldo Simeone. \"Information-theoretic bounds on transfer generalization gap based on Jensen-Shannon divergence.\" 2021 29th European Signal Processing Conference (EUSIPCO). IEEE, 2021.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cBnind-kFN1", "reviewer": "Reviewer_PFbK", "summary": "This paper focuses on the generalization bound of Unsupervised Domain Adaptation (UDA). The authors discuss two kinds of generalization errors and present the upper bounds of them respectively. The theoretical analysis are based on information theory and give inspiring insights into algorithm designs. The experiments validate the effectiveness of the algorithm on benchmark datasets.", "questions": "Q1. Compared Theorem 5.2 with Theorem 4.4, the difference between them is the first term of the bound in Theorem 5.2. And we know that $Err$ can be bounded by $\\widetilde{Err}$ plus a standard generalization error term on source domain. So, what is the difference between the first term of the bound in Theorem 5.2 and the standard generalization error term on source domain? Which one is tighter?\n\nOther questions can be found in Cons.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Pros:\n1. Quality: This paper has adequate contribution to the generalization bound of UDA problem. They focuse on two kinds of generalization bounds. For the first error bound, their works are similar to the traditional analysis, but they generalize them that they do not require specific loss function and specific classification settings. For the second error bound, their bounds involve $W$, which motivates the algorithm designs. They derive the bounds under different assumptions and divergence measures.\n2. Originality: This is the first work to analyse the generalization bounds of UDA from an information-theoretic perspective, as the authors claim. In fact, I am not familiar with the information theoretical framwork (Donsker-Varadhan representation of KL divergence) used in this paper. **So I am not very sure that the derivations in this paper are non-trival and novel.**\n3. Clarity: The writing is clear and easy to follow. The paper is well-organized.\n4. Significance: The generalization bounds of UDA are worth exploring. This paper is of great significance to this research field.\n\n## Cons:\n1. Some extra explanations and remarks should be added. Some contexts and symbols about information theory are somewhat hard to read.  For example, above Line 241, $I^{X_j'}(W;Z_i)$ is the disintegrated mutual information of $W$ and $Z_i$. According to the Definition 1, it involves the terms $P_{W,Z_i|X=X_j'}$ and $P_{W|X=X_j'}$. What does it mean for the probability of $W$ conditioned on an unlabeled sample $X$? It benifits for the readability of the paper if the authors add some explainations or remarks here.\n2. Above Line 204, what is the distribution of $W,W'$ in $\\mathbb{E}_{W,W',X}$ ?\n3. Although I understand the meaning of $\\ell(w,z)$, it seems has a conflic with the previous notion $\\ell(f_w(X),Y)$.\n4. In Theorem 5.1, 5.2, can we remove the term $\\frac{1}{mn}\\sum^{m}_{j=1}\\sum^{n}_{i=1}$, since the samples $ \\{X_j'\\},\\{Z_i\\} $ are i.i.d. for all i,j?", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WbwQuOgbDYx", "reviewer": "Reviewer_ch1K", "summary": "This paper provides two upper bounds for two notions of generalization errors; this first is the gap between the population risk in the target domain and the population risk in the source domain; the second is the gap between the population risk in the target domain and the empirical risk in the source domain. In addition, the paper presents two techniques for improving generalization in UDA and validate them experimentally.", "questions": "- The upper bounds seem very loose. What is the first upper bound's superiority to the previous bounds mentioned in [2]?", "limitations": "The limitations of the presented analysis could be discussed in more detail.\n\n", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\n\nThe paper's idea is not extremely novel, since there have been a lot of upper bounds for the first gap, such as [2].\n\n### Quality\n\nThe technical part of the paper seems correct as far as I can see.\n\n### Clarity \n\nThe paper is well-written. \n\n### Significance\n\nThe question studied in the paper is significant. The generalization gap bounds inspire insights into algorithm designs.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ig16qySpQTw", "reviewer": "Reviewer_UmkN", "summary": "This paper presents an information-theoretic analysis for unsupervised domain adaptation, where the authors considered two notions of the generalization errors in this context and present novel learning bounds. Some of these bounds recover the previous KL-based bounds under different conditions, and other bounds are algorithm-dependent that exploits the unlabelled target data, which inspired the designing of learning algorithms. The authors also demonstrate the effectiveness of these schemes on standard benchmark datasets.", "questions": "No.", "limitations": "No.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Some concerns:\n\n1. To some extend, the results in section 4 were not surprised. The upper bounds for the population risks expressed by KL divergence were well established in the transfer learning literature, say the works by Ben-David. The issue is that such bounds are usually hard to compute and applied to algorithm designs. In addition, it is also very difficult to verify high tight such bounds are. Since this paper neither presented new proving techniques nor showed any tightness results on their presented upper bounds, I may question the usefulness of such bounds for addressing the core difficulty of transfer learning problems.\n\n2. It seems that the number of samples in both source and target training data may play important roles in domain adaptation, which is referred to as the sample complexity issue in transfer learning. However, I do not see such characterizations in the bound presented in this paper. How does more target domain samples can effect the learning algorithms as well as the performances? This may need more detailed studies and discussions.\n\n3. The authors mentioned \"This paper presents the first information-theoretic analysis for unsupervised domain adaptation\". This is a bit over strong statement, and I would not say this is the first paper to present such analyses, since there are many other theoretical papers in transfer learning area that had done such kind of analyses. The paper may present some new bounds, but shall not be the first in this area.\n\n4. The most valuable part of this paper to me is the algorithm designs in section 5. However, it seems to me that the core idea of the proposed algorithm from the theoretical analyses in to add a L2 regularization term in the gradient decent updating, which has also been applied in many previous works. I wonder if the contribution of this paper is to provide another theoretical justification for the regularization term, or indeed there are novel steps in the algorithm that were not been considered before?\n\n5. The equation between line 105 and 106, the second term on the right hand side should be R_{\\mu} instead of R_{\\mu'}. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject