On Learning Invariant Representations for Domain Adaptation
Han Zhao 1 Remi Tachet des Combes 2 Kun Zhang 1 Geoffrey J. Gordon 1 2

Abstract
Due to the ability of deep neural nets to learnrich representations, recent advances in unsupervised domain adaptation have focused on learning
domain-invariant features that achieve a small error on the source domain. The hope is that thelearnt representation, together with the hypothesis
learnt from the source domain, can generalize tothe target domain. In this paper, we first constructa simple counterexample showing that, contrary
to common belief, the above conditions are notsufficient to guarantee successful domain adaptation. In particular, the counterexample exhibits
conditional shift: the class-conditional distributions of input features change between source andtarget domains. To give a sufficient condition fordomain adaptation, we propose a natural and interpretable generalization upper bound that explicitly takes into account the aforementioned shift.
Moreover, we shed new light on the problem byproving an information-theoretic lower bound on
the joint error of any domain adaptation methodthat attempts to learn invariant representations.
Our result characterizes a fundamental tradeoff
between learning invariant representations andachieving small joint error on both domains whenthe marginal label distributions differ from source
to target. Finally, we conduct experiments on
real-world datasets that corroborate our theoretical findings. We believe these insights are helpful
in guiding the future design of domain adaptation
and representation learning algorithms.

1. Introduction
The recent successes of supervised deep learning methods
have been partially attributed to rich datasets and increasing
1

Machine Learning Department, Carnegie Mellon University,
Pittsburgh, PA, USA 2 Microsoft Research, Montreal, Canada. Correspondence to: Han Zhao <han.zhao@cs.cmu.edu>.
Proceedings of the 36 th International Conference on Machine
Learning, Long Beach, California, PMLR 97, 2019. Copyright2019 by the author(s).

computational power. However, in many critical applications, e.g., self-driving cars or personal healthcare, it is often
prohibitively expensive and time-consuming to collect largescale supervised training data. Unsupervised domain adaptation (DA) focuses on such limitations by trying to transfer
knowledge from a labeled source domain to an unlabeled target domain, and a large body of work tries to achieve this byexploring domain-invariant structures and representations
to bridge the gap. Theoretical results (Ben-David et al.,2010; Mansour et al., 2009a; Mansour & Schain, 2012) andalgorithms (Glorot et al., 2011; Becker et al., 2013; Ajakan
et al., 2014; Adel et al., 2017; Pei et al., 2018) under thissetting are abundant.
Due to the ability of deep neural nets to learn rich feature
representations, recent advances in domain adaptation havefocused on using these networks to learn invariant representations, i.e., intermediate features whose distribution is
the same in source and target domains, while at the sametime achieving small error on the source domain. The hopeis that the learnt intermediate representation, together withthe hypothesis learnt using labeled data from the source
domain, can generalize to the target domain. Nevertheless,from a theoretical standpoint, it is not at all clear whetheraligned representations and small source error are sufficientto guarantee good generalization on the target domain. In
fact, despite being successfully applied in various applications (Zhang et al., 2017; Hoffman et al., 2017), it has also
been reported that such methods fail to generalize in certain
closely related source/target pairs, e.g., digit classificationfrom MNIST to SVHN (Ganin et al., 2016).
Given the wide application of domain adaptation methods
based on learning invariant representations, we attempt inthis paper to answer the following important and intriguingquestion:
Is finding invariant representations while at thesame time achieving a small source error sufficient to guarantee a small target error? If not,under what conditions is it?
Contrary to common belief, we give a negative answer tothe above question by constructing a simple example showing that these two conditions are not sufficient to guarantee
target generalization, even in the case of perfectly aligned
representations between the source and target domains. In

On Learning Invariant Representations for Domain Adaptationg(x) = Ix0 (x) · (x + 1)

target domain+ Ix>0 (x) · (x<latexit sha1_base64="Hk7gK9ZvHZgvlaE6B/70QQwbEHM=">AAADE3icbZHNbtNAEMc35quYj6Zw5LIiapWqIrILUnsBVXCBWxFNUymOovV6kqyyH2Z3TRwsPwZvwFsgLogrD8CZK7wDm9SoicNIK/01v//s7szEKWfGBsHPhnft+o2bt7Zu+3fu3ru/3dx5cG5Upil0qeJKX8TEAGcSupZZDhepBiJiDr14+mrBex9AG6bkmZ2nMBBkLNmIUWJdatjs+eN2vo/3nuNIEDuJ4+JNOSzyiMN7HJQORTRRFrdzfIDDfRxF/t7BuhW/qBmfOKM/bLaCTrAMvCnCSrRQFafDncbnKFE0EyAt5cSYfhikdlAQbRnlUPpRZiAldErG0HdSEgFmUCwnUOJdl0nwSGl3pMXL7GpFQYQxcxE75+Lvps4Wyf+xfmZHx4OCyTSzIOnlQ6OMY6vwYpw4YRqo5XMnCNXM/RXTCdGEWjd0fxevvrO4PSUf1XovgkxBKyVcL0RS4I5KmFElBJFJETGZlMXVwGt0Bmw8sf8Mo2JWN+T5Fczr0KSyopTw4t0mthpgxXFWlm6vYX2Lm+L8sBM+7Ry+fdY6eVlteAs9Qo9RG4XoCJ2g1+gUdRFFX9Ev9Bv98T55X7xv3vdLq9eoah6itfB+/AVVif6u</latexit>

y=1

y=0

target domain

1)

y=1

y=0

x
1

0.5
0
y=0
y=1

0.5

1

1.5

2

x
1

0.5

0

0.5
y=0

source domain

1

1.5

2

y=1

source domain

Figure 1. A counterexample where invariant representations lead to large joint error on source and target domains. Before transformationof g(·), h⇤ (x) = 1 iff x 2 ( 1/2, 3/2) achieves perfect classification on both domains. After transformation, source and target
distributions are perfectly aligned, but no hypothesis can achieve a small joint error.

fact, our example shows that the objective of learning invariant representations while minimizing the source error canactually be hurtful, in the sense that the better the objective,
the larger the target error. At a colloquial level, this happens because learning invariant representations can breakthe originally favorable underlying problem structure, i.e.,
close labeling functions and conditional distributions. To
understand when such methods work, we propose a generalization upper bound as a sufficient condition that explicitly
takes into account the conditional shift between source andtarget domains. The proposed upper bound admits a naturalinterpretation and decomposition in domain adaptation; weshow that it is tighter than existing results in certain cases.
Simultaneously, to understand what the necessary conditions for representation based approaches to work are, we
prove an information-theoretic lower bound on the joint
error of both domains for any algorithm based on learning
invariant representations. Our result complements the above
upper bound and also extends the constructed example tomore general settings. The lower bound sheds new lighton this problem by characterizing a fundamental tradeoff
between learning invariant representations and achieving
small joint error on both domains when the marginal label
distributions differ from source to target. Our lower bounddirectly implies that minimizing source error while achieving invariant representation will only increase the target
error. We conduct experiments on real-world datasets that
corroborate this theoretical implication. Together with thegeneralization upper bound, our results suggest that adaptation should be designed to align the label distribution as
well when learning an invariant representation (c.f. Sec. 4.3).
We believe these insights will be helpful to guide the future
design of domain adaptation and representation learningalgorithms.

2. Preliminary
We first introduce the notations used throughout this paper and review a theoretical model for domain adaptation(DA) (Kifer et al., 2004; Ben-David et al., 2007; Blitzer
et al., 2008; Ben-David et al., 2010).

Notations We use X and Y to denote the input and output
space, respectively. Similarly, Z stands for the representation space induced from X by a feature transformationg : X 7! Z. Accordingly, we use X, Y, Z to denote therandom variables which take values in X , Y, Z, respectively.
In this work, domain corresponds to a distribution D on the
input space X and a labeling function f : X ! [0, 1]. In thedomain adaptation setting, we use hDS , fS i and hDT , fT i
to denote the source and target domains, respectively. A
hypothesis is a function h : X ! {0, 1}. The error of ahypothesis h w.r.t. the labeling function f under distribution DS is defined as: "S (h, f ) := Ex⇠DS [|h(x) f (x)|].
When f and h are binary classification functions, this definition reduces to the probability that h disagrees with f under
DS : Ex⇠DS [|h(x) f (x)|] = Ex⇠DS [I(f (x) 6= h(x))] =Prx⇠DS (f (x) 6= h(x)). In this work, we focus on the deterministic setting where the output Y = f (X) is given by adeterministic labeling function f defined on the corresponding domain. For two functions g and h with compatible
domains and ranges, we use h g to denote the function
composition h(g(·)). Other notations will be introduced in
the context when necessary.
2.1. Problem Setup
We consider the unsupervised domain adaptation problem
where the learning algorithm has access to a set of n labeledpoints {(xi , yi )}ni=1 2 (X ⇥ Y)n sampled i.i.d. from themsource domain and a set of unlabeled points {xj }m
j=1 2 X
sampled i.i.d. from the target domain. At a colloquial level,
the goal of an unsupervised domain adaptation algorithm
is to generalize well on the target domain by learning fromlabeled samples from the source domain as well as unlabeled samples from the target domain. Formally, let therisk of hypothesis h be the error of h w.r.t. the true labeling
function under domain DS , i.e., "S (h) := "S (h, fS ). As
commonly used in computational learning theory, we denote by "bS (h) the empirical risk of h on the source domain.
Similarly, we use "T (h) and "bT (h) to mean the true risk
and the empirical risk on the target domain. The problemof domain adaptation considered in this work can be statedas: under what conditions and by what algorithms can weOn Learning Invariant Representations for Domain Adaptation

guarantee that a small training error "bS (h) implies a small
test error "T (h)? Clearly, this goal is not always possible if
the source and target domains are far away from each other.
2.2. A Theoretical Model for Domain Adaptation
To measure the similarity between two domains, it is crucial
to define a discrepancy measure between them. To thisend, Ben-David et al. (2010) proposed the H-divergence tomeasure the distance between two distributions:Definition 2.1 (H-divergence). Let H be a hypothesis classon input space X , and AH be the collection of subsets
of X that are the support of some hypothesis in H, i.e.,
AH := {h 1 (1) | h 2 H}. The distance between two
distributions D and D0 based on H is: dH (D, D0 ) :=supA2AH | PrD (A) PrD0 (A)|. 1
H-divergence is particularly favorable in the analysis of
domain adaptation with binary classification problems,and it had also been generalized to the discrepancy distance (Cortes et al., 2008; Mansour et al., 2009a;b; Cortes &Mohri, 2014) for general loss functions, including the one
for regression problems. Both H-divergence and the discrepancy distance can be estimated using finite unlabeled samples from both domains when H has a finite VC-dimension.

One flexibility of the H-divergence is that its power on
measuring the distance between two distributions can becontrolled by the richness of the hypothesis class H. To
see this, first consider the situation where H is very restrictive so that it only contains the constant functions h ⌘ 0
and h ⌘ 1. In this case, it can be readily verified by thedefinition that dH (D, D0 ) = 0, 8 D, D0 . On the other extreme, if H contains all the measurable binary functions,then dH (D, D0 ) = 0 iff D(·) = D0 (·) almost surely. In
this case the H-divergence reduces to the total variation, or
equivalently the L1 distance, between the two distributions.
Given a hypothesis class H, we define its symmetric difference w.r.t. itself as: H H = {h(x) h0 (x) | h, h0 2 H},
where is the xor operation. Let h⇤ be the optimal hypothesis that achieves the minimum joint risk on both the source
and target domains: h⇤ := arg minh2H "S (h) + "T (h),and let ⇤ denote the joint risk of the optimal hypothesis h⇤ :⇤ :="S (h⇤ ) + "T (h⇤ ). Ben-David et al. (2007) proved thefollowing generalization bound on the target risk in terms of
the empirical source risk and the discrepancy between thesource and target domains:
Theorem 2.1 (Ben-David et al. (2007)). Let H be a hypothbS (resp. D
bT ) be theesis space of VC-dimension d and D
empirical distribution induced by a sample of size n drawn
1

To be precise, Ben-David et al. (2007)’s original definition of
H-divergence has a factor of 2, we choose the current definition as
the constant factor is inessential.

from DS (resp. DT ). Then w.p. at least 1, 8h 2 H,

1bS , DbT )"T (h)  "bS (h) + dH H (D2!
rd log n + log(1/ )
⇤
+ +O
.
n

(1)

The bound depends on ⇤ , the optimal joint risk that canbe achieved by the hypotheses in H. The intuition is thefollowing: if ⇤ is large, we cannot hope for a successfuldomain adaptation. Later in Sec. 4.3, we shall get back tothis term to show an information-theoretic lower bound on it
for any approach based on learning invariant representations.
Theorem 2.1 is the foundation of many recent works on
unsupervised domain adaptation via learning invariant representations (Ajakan et al., 2014; Ganin et al., 2016; Zhao
et al., 2018b; Pei et al., 2018; Zhao et al., 2018a). It has
also inspired various applications of domain adaptation withadversarial learning, e.g., video analysis (Hoffman et al.,2016; Shrivastava et al., 2016; Hoffman et al., 2017; Tzeng
et al., 2017), natural language understanding (Zhang et al.,2017; Fu et al., 2017), speech recognition (Zhao et al., 2019;
Hosseini-Asl et al., 2018), to name a few.
At a high level, the key idea is to learn a rich andparametrized feature transformation g : X 7! Z such thatthe induced source and target distributions (on Z) are close,
as measured by the H-divergence. We call g an invariant
representation w.r.t. H if dH (DSg , DTg ) = 0, where DSg /DTgis the induced source/target distribution. At the same time,these algorithms also try to find new hypothesis (on the
representation space Z) to achieve a small empirical error
on the source domain. As a whole algorithm, these twoprocedures corresponds to simultaneously finding invariant
representations and hypothesis to minimize the first two
terms in the generalization upper bound of Theorem 2.1.

3. Related WorkA number of adaptation approaches based on learning invariant representations have been proposed in recent years.
Although in this paper we mainly focus on using the Hdivergence to characterize the discrepancy between two
distributions, other distance measures can be used as well,e.g., the maximum mean discrepancy (MMD) (Long et al.,2014; 2015; 2016), the Wasserstein distance (Courty et al.,2017b;a; Shen et al., 2018; Lee & Raginsky, 2018), etc.
Under the theoretical framework of the H-divergence, Ganin
et al. (2016) propose a domain adversarial neural network(DANN) to learn the domain invariant features. Adversarial
training techniques that aim to build feature representations
that are indistinguishable between source and target domains have been proposed in the last few years (Ajakan

On Learning Invariant Representations for Domain Adaptation

et al., 2014; Ganin et al., 2016). Specifically, one of thecentral ideas is to use neural networks, which are powerful
function approximators, to approximate the H-divergence
between two domains (Kifer et al., 2004; Ben-David et al.,2007; 2010). The overall algorithm can be viewed as a zerosum two-player game: one network tries to learn feature
representations that can fool the other network, whose goal
is to distinguish the representations generated on the source
domain from those generated on the target domain. In a
concurrent work, Johansson et al. (2019) also identified theinsufficiency of learning domain-invariant representation
for successful adaptation. They further analyzed the information loss of non-invertible transformations, and proposeda generalization upper bound that directly takes it into account. In our work, by showing an information-theoretic
lower bound on the joint error of these methods, we showthat although invariant representations can be achieved, it
does not necessarily translate to good generalization on thetarget domain, in particular when the label distributions of
the two domains differ significantly.
Causal approaches based on conditional and label shifts fordomain adaptation also exist (Zhang et al., 2013; Gong et al.,2016; Lipton et al., 2018; Azizzadenesheli et al., 2018). One
typical assumption made to simplify the analysis in this lineof work is that the source and target domains share the samegenerative distribution and only differ at the marginal label
distributions. It is worth noting that Zhang et al. (2013) and
Gong et al. (2016) showed that both label and conditional
shift can be successfully corrected when the changes in thegenerative distribution follow some parametric families. In
this work we focus on representation learning and do notmake such explicit assumptions.

4. Theoretical Analysis
Is finding invariant representations alone a sufficient condition for the success of domain adaptation? Clearly it isnot. Consider the following simple counterexample: let
gc : X 7! Z be a constant function, where 8x 2 X ,gc (x) = c 2 Z. Then for any discrepancy distance d(·, ·)over two distributions, including the H-divergence, MMD,
and the Wasserstein distance, and for any distributions
DS , DT over the input space X , we have d(DSgc , DTgc ) = 0,
where we use DSgc (resp. DTgc ) to mean the induced source(resp. target) distribution by the transformation gc over the
representation space Z. Furthermore, it is fairly easy toconstruct source and target domains hDS , fS i, hDT , fT i,such that for any hypothesis h : Z 7! Y, "T (h gc ) 1/2,
while there exists a classification function f : X ! Y that
achieves small error, e.g., the labeling function.
One may argue, with good reason, that in the counterexample above, the empirical source error "bS (h gc ) is also
large with high probability. Intuitively, this is because thesimple constant transformation function gc fails to retain
the discriminative information about the classification task
at hand, despite the fact that it can construct invariant representations.
Is finding invariant representations and achieving a small
source error sufficient to guarantee small target error? In
this section we first give a negative answer to this question
by constructing a counterexample where there exists a nontrivial transformation function g : X 7! Z and hypothesis
h : Z 7! Y such that both "S (h g) and dH H (DSg , DTg )are small, while at the same time the target error "T (h g) islarge. Motivated by this negative result, we proceed to provea generalization upper bound that explicitly characterizes
a sufficient condition for the success of domain adaptation. We then complement the upper bound by showing
an information-theoretic lower bound on the joint error ofany domain adaptation approach based on learning invariant
representations.
4.1. Invariant Representation and Small Source Risk
are Not Sufficient
In this section, we shall construct a simple 1-dimensional
example where there exists a function h⇤ : R 7! {0, 1}that achieves zero error on both source and target domains.
Simultaneously, we show that there exists a transformation
function g : R 7! R under which the induced source andtarget distributions are perfectly aligned, but every hypothesis h : R 7! {0, 1} incurs a large joint error on the induced
source and target domains. The latter further implies that
if we find a hypothesis that achieves small error on thesource domain, then it has to incur a large error on the target
domain. We illustrate this example in Fig. 1.
Let X = Z = R and Y = {0, 1}. For a  b, we use U (a, b)
to denote the uniform distribution over [a, b]. Consider thefollowing source and target domains:(
0, x  1/2
DS = U ( 1, 0),fS (x) =1, x > 1/2(
0, x 3/2
DT = U (1, 2),
fT (x) =1, x < 3/2
In the above example, it is easy to verify that the interval
hypothesis h⇤ (x) = 1 iff x 2 ( 1/2, 3/2) achieves perfectclassification on both domains.
Now consider the following transformation:g(x) = Ix0 (x) · (x + 1) + Ix>0 (x) · (x1).

Since g(·) is a piecewise linear function, it follows that
DSZ = DTZ = U (0, 1), and for any distance metric d(·, ·)over distributions, we have d(DSZ , DTZ ) = 0. But now for
any hypothesis h : R 7! {0, 1}, and 8x 2 [0, 1], h(x) will

On Learning Invariant Representations for Domain Adaptation

make an error in exactly one of the domains, hence
8h : R 7! {0, 1},"S (h g) + "T (h g) = 1.

In other words, under the above invariant transformation g,
the smaller the source error, the larger the target error.
One may argue that this example seems to contradict thegeneralization upper bound from Theorem 2.1, where thefirst two terms correspond exactly to a small source error
and an invariant representation. The key to explain thisapparent contradiction lies in the third term of the upperbound, ⇤ , i.e., the optimal joint error achievable on both
domains. In our example, when there is no transformation
applied to the input space, we show that h⇤ achieves 0 error
on both domains, hence ⇤ = minh2H "S (h) + "T (h) =0. However, when the transformation g is applied to theoriginal input space, we prove that every hypothesis has joint
error 1 on the representation space, hence ⇤g = 1. Since
we usually do not have access to the optimal hypothesis
on both domains, although the generalization bound stillholds on the representation space, it becomes vacuous in
our example.
An alternative way to interpret the failure of the constructed
example is that the labeling functions (or conditional distributions in the stochastic setting) of source and target
domains are far away from each other in the representation
space. Specifically, in the induced representation space, theoptimal labeling function on the source and target domains
are:
(
(
0,
x

1/2
0, x > 1/2
fS0 (x) =, fT0 (x) =,1, x > 1/2
1, x  1/2
and we have ||fS0
1.

fT0 ||1 = Ex⇠U (0,1) [|fS0 (x)fT0 (x)|] =4.2. A Generalization Upper Bound
For most of the practical hypothesis spaces H, e.g., half
spaces, it is usually intractable to compute the optimal joint
error ⇤ from Theorem 2.1. Furthermore, the fact that ⇤contains errors from both domains makes the bound very
conservative and loose in many cases. In this section, inspired by the constructed example from Sec. 4.1, we aim
to provide a general, intuitive, and interpretable generalization upper bound for domain adaptation that is free of thepessimistic ⇤ term. Ideally, the bound should also explicitly characterize how the shift between labeling functionsof both domains affects domain adaptation. Due to spaceconstraints, we refer the interested reader to the Appendix
for the proofs of our technical lemmas, and mainly focus in
the following on interpretations and results.
Because of its flexibility in choosing the witness function
class H and its natural interpretation as adversarial binaryclassification, we still adopt the H-divergence to measure
the discrepancy between two distributions. For any hypothesis space H, it can be readily verified that dH (·, ·) satisfies
the triangular inequality:dH (D, D0 )  dH (D, D00 ) + dH (D00 , D0 ),where D, D0 , D00 are any distributions over the same space.
We now introduce a technical lemma that will be helpful inproving results related to the H-divergence:
Lemma 4.1. Let H ✓ [0, 1]X and D, D0 be two distributions over X . Then 8h, h0 2 H, |"D (h, h0 ) "D0 (h, h0 )| dH̃ (D, D0 ), where H̃ := {sgn(|h(x) h0 (x)| t) | h, h0 2
H, 0  t  1}.

As a matter of fact, the above lemma also holds for any
function class H (not necessarily a hypothesis space) where
there exists a constant M > 0, such that ||h||1  M for all
h 2 H. Another useful lemma is the following triangularinequality:
Lemma 4.2. Let H ✓ [0, 1]X and D be any distribution
over X . For any h, h0 , h00 2 H, we have "D (h, h0 ) "D (h, h00 ) + "D (h00 , h0 ).
Let fS : X ! [0, 1] and fT : X ! [0, 1] be the optimallabeling functions on the source and target domains, respectively. In the stochastic setting, fS (x) = PrS (y = 1 | x)
corresponds to the optimal Bayes classifier. With thesenotations, the following theorem holds:
Theorem 4.1. Let hDS , fS i and hDT , fT i be the source
and target domains, respectively. For any function classH ✓ [0, 1]X , and 8h 2 H, the following inequality holds:"T (h)  "S (h) + dH̃ (DS , DT )+ min{EDS [|fS

fT |], EDT [|fS

fT |]}.

Remark The three terms in the upper bound have naturalinterpretations: the first term is the source error, the second
one corresponds to the discrepancy between the marginal
distributions, and the third measures the distance between
the labeling functions from the source and target domains.
Altogether, they form a sufficient condition for the successof domain adaptation: besides a small source error, not only
do the marginal distributions need to be close, but so do thelabeling functions.
Comparison with Theorem 2.1. It is instructive to compare the bound in Theorem 4.1 with the one in Theorem 2.1. The main difference lies in the ⇤ in Theorem 2.1 and the min{EDS [|fS
fT |], EDT [|fS
fT |]}
in Theorem 4.1. ⇤ depends on the choice of the hypothesis class H, while our term does not. In fact, ourquantity reflects the underlying structure of the problem,i.e., the conditional shift. Finally, consider the example
given in the left panel of Fig. 1. It is easy to verify that

On Learning Invariant Representations for Domain Adaptation

we have min{EDS [|fS
fT |], EDT [|fS
fT |]} = 1/2
in this case, while for a natural class of hypotheses, i.e.,
H := {h(x) = 0 , a  x  b | a < b}, we have⇤= 1. In that case, our bound is tighter than the one in
Theorem 2.1.
In the covariate shift setting, where we assume the conditional distributions of Y | X between the source and target
domains are the same, the third term in the upper boundvanishes. In that case the above theorem says that to guarantee successful domain adaptation, it suffices to match themarginal distributions while achieving small error on thesource domain. In general settings where the optimal labeling functions of the source and target domains differ, theabove bound says that it is not sufficient to simply match themarginal distributions and achieve small error on the source
domain. At the same time, we should also guarantee that the
optimal labeling functions (or the conditional distributionsof both domains) are not too far away from each other. Asa side note, it is easy to see that EDS [|fS fT |] = "S (fT )and EDT [|fS fT |] = "T (fS ). In other words, they are
essentially the cross-domain errors. When the cross-domain
error is small, it implies that the optimal source (resp. target) labeling function generalizes well on the target (resp.
source) domain.
Both the error term "S (h) and the divergence dH̃ (DS , DT )in Theorem 4.1 are with respect to the true underlying distributions DS and DT , which are not available to us during
training. In the following, we shall use the Rademacher complexity to provide for both terms a data-dependent boundfrom empirical samples from DS and DT .
Definition 4.1 (Empirical Rademacher Complexity). Let
H be a family of functions mapping from X to [a, b] andS = {xi }ni=1 a fixed sample of size n with elements in
X . Then, the empirical Rademacher complexity of H withrespect to the sample X is defined asn
1X
RadS (H) := E supi h(xi ) ,h2H n i=1

where = { i }ni=1 and i are i.i.d. uniform random variables taking values in {+1, 1}.
With the empirical Rademacher complexity, we can showthat w.h.p., the empirical source error "bS (h) cannot be too
far away from the population error "S (h) for all h 2 H:
Lemma 4.3. Let H ✓ [0, 1]X , then for all > 0, w.p. atleast 1, the following inequality
p holds for all h 2 H:
"S (h)  "bS (h) + 2RadS (H) + 3 log(2/ )/2n.

b be its empiriSimilarly, for any distribution D over X , let D
cal distribution from sample S ⇠ Dn of size n. Then for any
two distributions D and D0 , we can also use the empirical
Rademacher complexity to provide a data-dependent boundb Db 0 ):
for the perturbation between dH (D, D0 ) and dH (D,b be defined above, then forLemma 4.4. Let H̃, D and D
all > 0, w.p. at least 1, the following inequality
holds for all h 2 H̃: ED [Ih ]  EDb [Ih ] + 2RadS (H̃) +p
3 log(2/ )/2n.
Since H̃ is a hypothesis class, by definition we have:b = sup | Pr(A)dH̃ (D, D)
A2AH̃

D

= sup |ED [Ih ]h2H̃

Pr(A)|bD

EDb [Ih ]|.

Hence combining the above identity with Lemma 4.4, we
immediately have w.p. at least 1:
pb  2RadS (H̃) + 3 log(2/ )/2n.
dH̃ (D, D)(2)

Now use a union bound and the fact that dH̃ (·, ·) satisfies
the triangle inequality, we have:b D
b 0 be defined above,
Lemma 4.5. Let H̃, D, D0 and D,then for 8 > 0, w.p. at least 1, for 8h 2 H̃:pb Db 0 ) + 4RadS (H̃) + 6 log(4/ )/2n.
dH̃ (D, D0 )  dH̃ (D,Combine Lemma 4.3, Lemma 4.5 and Theorem 4.1 with aunion bound argument, we get the following main theorem
that characterizes an upper bound for domain adaptation:

Theorem 4.2. Let hDS , fS i and hDT , fT i be the source andbS , DbT be the empirical source andtarget domains, and let D
target distributions constructed from sample S = {SS , ST },each of size n. Then for any H ✓ [0, 1]X and 8h 2 H:
bS , DbT ) + 2RadS (H) + 4RadS (H̃)"T (h)  "bS (h) + dH̃ (D+ min{EDS [|fS fT |], EDT [|fS⇣p⌘+O
log(1/ )/n ,fT |]}

where H̃ := {sgn(|h(x) h0 (x)| t)|h, h0 2 H, t 2 [0, 1]}.
Essentially, the generalization upper bound can be decomposed into three parts: the first part comes from the domain
adaptation setting, including the empirical source error, theempirical H-divergence, and the shift between labeling functions. The second part corresponds to complexity measuresof our hypothesis space H and H̃, and the last part describes
the error caused by finite samples.
4.3. An Information-Theoretic Lower BoundIn Sec. 4.1, we constructed an example to demonstrate thatlearning invariant representations could lead to a feature
space where the joint error on both domains is large. In thissection, we extend the example by showing that a similar
result holds in more general settings. Specifically, we shallprove that for any approach based on learning invariant representations, there is an intrinsic lower bound on the jointOn Learning Invariant Representations for Domain Adaptation

error of source and target domains, due to the discrepancy
between their marginal label distributions. Our result hence
highlights the need to take into account task related information when designing domain adaptation algorithms basedon learning invariant representations.
Before we proceed to the lower bound, we first define several
information-theoretic concepts that will be used in the analysis. For two distributions D and D0 , the Jensen-Shannon(JS) divergence DJS (D || D0 ) is defined as:

1
1
DKL (D || DM ) + DKL (D0 || DM ),22
where DKL (· || ·) is the Kullback–Leibler (KL) divergenceand DM := (D + D0 )/2. The JS divergence can be viewed
as a symmetrized and smoothed version of the KL divergence, and it is closely related to the L1 distance between
two distributions through Lin’s lemma (Lin, 1991).
DJS (D || D0 ) :=Unlike the KL divergence, the JS divergence is bounded:0  DJS (D || D0 )  1. Additionally, from the JS divergence, we can define a distance metric between two
distributions as well, known as the JS distance (Endres &Schindelin, 2003):
p
dJS (D, D0 ) := DJS (D || D0 ).

With respect to the JS distance and for any (stochastic)
mapping h : Z 7! Y, we can prove the following lemma
via the celebrated data processing inequality:
Lemma 4.6. Let DSZ and DTZ be two distributions over Z
and let DSY and DTY be the induced distributions over Y byfunction h : Z 7! Y, thendJS (DSY , DTY )  dJS (DSZ , DTZ ).

(3)

For methods that aim to learn invariant representations fordomain adaptation, an intermediate representation space Z
is found through feature transformation g, based on which
a common hypothesis h : Z 7! Y is shared between both
domains (Ganin et al., 2016; Tzeng et al., 2017; Zhao et al.,2018b). Through this process, the following Markov chain
holds:gh
X ! Z ! Ŷ ,(4)

where Ŷ = h(g(X)) is the predicted random variableof interest. Hence for any distribution D over X , thisMarkov chain also induces a distribution DZ over Z and
DŶ over Y. By Lemma 4.6, we know that dJS (DSŶ , DTŶ ) dJS (DSZ , DTZ ). With these notations, noting that the JS distance is a metric, the following inequality holds:

Intuitively, dJS (DSY , DSŶ ) and dJS (DTY , DTŶ ) measure thedistance between the predicted label distribution and theground truth label distribution on the source and target domain, respectively. Formally, the following result establishes a relationship between dJS (DY , DŶ ) and the accuracyof the prediction function h:
Lemma 4.7. Let Y = f (X) 2 {0, 1} where f (·) is thelabeling function and Ŷ = h(g(X)) 2 {0, 1} be the predicp
tion function, then dJS (DY , DŶ )  "(h g).

We are now ready to present the key lemma of the section:ghLemma 4.8. Suppose the Markov chain X ! Z ! Ŷholds, thenppdJS (DSY , DTY )  dJS (DSZ , DTZ ) + "S (h g) + "T (h g).

Remark This lemma shows that if the marginal label distributions are significantly different between the source andtarget domains, then in order to achieve a small joint error,
the induced distributions over Z from source and target domains have to be significantly different as well. Put anotherway, if we are able to find an invariant representation suchthat dJS (DSZ , DTZ ) = 0, then the joint error of the composition function h g has to be large:
Theorem 4.3. Suppose the condition in Lemma 4.8 holds
and dJS (DSY , DTY ) dJS (DSZ , DTZ ), then:

1
2
dJS (DSY , DTY ) dJS (DSZ , DTZ ) .
2
Remark The lower bound gives us a necessary conditionon the success of any domain adaptation approach basedon learning invariant representations: if the marginal label distributions are significantly different between source
and target domains, then minimizing dJS (DSZ , DTZ ) and thesource error "S (h g) will only increase the target error.
In fact, Theorem 4.3 can be extended to hold in the setting where different transformation functions are applied insource and target domains:"S (h g)+"T (h g)Corollary 4.1. Let gS , gT be the source and target transformation functions from X to Z. Suppose the condition in
Lemma 4.8 holds and dJS (DSY , DTY ) dJS (DSZ , DTZ ), then:

1
2
dJS (DSY , DTY ) dJS (DSZ , DTZ ) .
2
Recent work has also explored using different transformation functions to achieve invariant representations (Bousmalis et al., 2016; Tzeng et al., 2017), but Corollary 4.1
dJS (DSY , DTY )  dJS (DSY , DSŶ )+dJS (DSŶ , DTŶ )+dJS (DTŶ , DTY ). shows that this is not going to help if the marginal label
distributions differ between two domains.
Combining the above inequality with Lemma 4.6, we immediately have:
We conclude this section by noting that our bound on thedJS (DSY , DTY )  dJS (DSZ , DTZ )+ dJS (DSY , DSŶ ) + dJS (DTY , DTŶ ).

(5)"S (h gS )+"T (h gT )joint error of both domains is not necessarily the tightest
one. This can be seen from the example in Sec. 4.1, wheredJS (DSZ , DTZ ) = dJS (DSY , DTY ) = 0, and we have "S (h g)+

On Learning Invariant Representations for Domain Adaptation(a) USPS ! MNIST(b) USPS ! SVHN(c) SVHN ! MNIST(d) SVHN ! USPS

Figure 2. Digit classification on MNIST, USPS and SVHN. The horizontal solid line corresponds to the target domain test accuracy
without adaptation. The green solid line is the target domain test accuracy under domain adaptation with DANN. We also plot the leastsquare fit (dashed line) of the DANN adaptation results to emphasize the negative slope.

"T (h g) = 1, but in this case our result gives a trivial lower
bound of 0. Nevertheless, our result still sheds new lighton the importance of matching marginal label distributionsin learning invariant representation for domain adaptation,
which we believe to be a promising direction for the designof better adaptation algorithms.

5. Experiments
Our theoretical results on the lower bound of the joint error
imply that over-training the feature transformation function
and the discriminator may hurt generalization on the target
domain. In this section, we conduct experiments on realworld datasets to verify our theoretical findings. The task isdigit classification on three datasets of 10 classes: MNIST,USPS and SVHN. MNIST contains 60,000/10,000 train/test
instances; USPS contains 7,291/2,007 train/test instances,and SVHN contains 73,257/26,032 train/test instances. We
show the label distribution of these three datasets in Fig. 3.

discriminator in DANN takes the output of convolutional
layers as its feature input, followed by a 500 ⇥ 100 fully
connected layer, and a one-unit binary classification output.
We plot four adaptation trajectories in Fig. 2. Among thefour adaptation tasks, we can observe two phases in theadaptation accuracy. In the first phase, the test set accuracy rapidly grows, in less than 10 iterations. In the second
phase, it gradually decreases after reaching its peak, despite
the fact that the source training accuracy keeps increasingsmoothly. Those phase transitions can be verified fromthe negative slopes of the least squares fit of the adaptation curves (dashed lines in Fig. 2). We observe similar
phenomenons on additional experiments using artificiallyunbalanced datasets trained on more powerful networks
in Appendix C. The above experimental results imply thatover-training the feature transformation and discriminator
does not help generalization on the target domain, but caninstead hurt it when the label distributions differ (as shownin Fig. 3). These experimental results are consistent with
our theoretical findings.

6. Conclusion and Future Work

Figure 3. The label distributions of MNIST, USPS and SVHN.

Before training, we preprocess all the samples into grayscale single-channel images of size 16 ⇥ 16, so they can beused by the same network. In our experiments, to ensure afair comparison, we use the same network structure for all
the experiments: 2 convolutional layers, one fully connected
hidden layer, followed by a softmax output layer with 10
units. The convolution kernels in both layers are of size 5⇥5,
with 10 and 20 channels, respectively. The hidden layer
has 1280 units connected to 100 units before classification.
For domain adaptation, we use the original DANN (Ganin
et al., 2016) with gradient reversal implementation. The

In this paper we theoretically and empirically study the important problem of learning invariant representations fordomain adaptation. We show that learning an invariant representation and achieving a small source error is not enoughto guarantee target generalization. We then prove both upper and lower bounds for the target and joint errors, which
directly translate to sufficient and necessary conditions forthe success of adaptation. We believe our results take an important step towards understanding deep domain adaptation,
and also stimulate future work on the design of stronger
deep domain adaptation algorithms that align conditional
distributions. Another interesting direction for future work
is to characterize what properties the feature transformation
function should have in order to decrease the conditional
shift. It is also worth investigating under which conditions
the label distributions can be aligned without explicit labeleddata from the target domain.

On Learning Invariant Representations for Domain Adaptation

Acknowledgements
HZ thank Yifan Wu for inspiring discussion on possible
failure cases of deep domain adaptation, and Jeremy Cohenfor reviewing drafts of this work. HZ and GG would like toacknowledge the support from DARPA XAI project, contract #FA87501720152. KZ would like to acknowledge thesupport by National Institutes of Health (NIH) under Contract No. NIH-1R01EB022858-01, FAINR01EB022858,
NIH-1R01LM012087, NIH-5U54HG008540-02, and FAINU54HG008540, by the United States Air Force under Contract No. FA8650-17-C-7715, and by National Science Foundation (NSF) EAGER Grant No. IIS-1829681. The NIH,
the U.S. Air Force, and the NSF are not responsible for theviews reported in this article.

References
Adel, T., Zhao, H., and Wong, A. Unsupervised domain
adaptation with a relaxed covariate shift assumption. In
AAAI, pp. 1691–1697, 2017.
Ajakan, H., Germain, P., Larochelle, H., Laviolette, F.,
and Marchand, M. Domain-adversarial neural networks.
arXiv preprint arXiv:1412.4446, 2014.
Azizzadenesheli, K., Liu, A., Yang, F., and Anandkumar, A.
Regularized learning for domain adaptation under label
shifts. 2018.
Bartlett, P. L. and Mendelson, S. Rademacher and gaussiancomplexities: Risk bounds and structural results. Journalof Machine Learning Research, 3(Nov):463–482, 2002.
Becker, C. J., Christoudias, C. M., and Fua, P. Non-linear
domain adaptation with boosting. In Advances in Neural
Information Processing Systems, pp. 485–493, 2013.
Ben-David, S., Blitzer, J., Crammer, K., Pereira, F., et al.
Analysis of representations for domain adaptation. Advances in neural information processing systems, 19:137,
2007.
Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A.,
Pereira, F., and Vaughan, J. W. A theory of learning fromdifferent domains. Machine learning, 79(1-2):151–175,
2010.
Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., and Wortman, J. Learning bounds for domain adaptation. In
Advances in neural information processing systems, pp.
129–136, 2008.
Bousmalis, K., Trigeorgis, G., Silberman, N., Krishnan, D.,
and Erhan, D. Domain separation networks. In Advancesin Neural Information Processing Systems, pp. 343–351,
2016.

Cortes, C. and Mohri, M. Domain adaptation and sample bias correction theory and algorithm for regression.
Theoretical Computer Science, 519:103–126, 2014.
Cortes, C., Mohri, M., Riley, M., and Rostamizadeh, A.
Sample selection bias correction theory. In International
Conference on Algorithmic Learning Theory, pp. 38–53.
Springer, 2008.
Courty, N., Flamary, R., Habrard, A., and Rakotomamonjy,
A. Joint distribution optimal transportation for domain
adaptation. In Advances in Neural Information Processing Systems, pp. 3730–3739, 2017a.
Courty, N., Flamary, R., Tuia, D., and Rakotomamonjy, A.
Optimal transport for domain adaptation. IEEE transactions on pattern analysis and machine intelligence, 39(9):1853–1865, 2017b.
Endres, D. M. and Schindelin, J. E. A new metric for probability distributions. IEEE Transactions on Information
theory, 2003.
Fu, L., Nguyen, T. H., Min, B., and Grishman, R. Domain
adaptation for relation extraction with domain adversarial
neural network. In Proceedings of the Eighth International Joint Conference on Natural Language Processing(Volume 2: Short Papers), volume 2, pp. 425–429, 2017.
Ganin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle,
H., Laviolette, F., Marchand, M., and Lempitsky, V.
Domain-adversarial training of neural networks. Journalof Machine Learning Research, 17(59):1–35, 2016.
Glorot, X., Bordes, A., and Bengio, Y. Domain adaptation
for large-scale sentiment classification: A deep learning
approach. In Proceedings of the 28th international conference on machine learning (ICML-11), pp. 513–520,
2011.
Gong, M., Zhang, K., Liu, T., Tao, D., Glymour, C., andSchölkopf, B. Domain adaptation with conditional transferable components. In International conference on machine learning, pp. 2839–2848, 2016.
Hoffman, J., Wang, D., Yu, F., and Darrell, T. Fcns in
the wild: Pixel-level adversarial and constraint-based
adaptation. arXiv preprint arXiv:1612.02649, 2016.
Hoffman, J., Tzeng, E., Park, T., Zhu, J.-Y., Isola, P.,
Saenko, K., Efros, A. A., and Darrell, T. Cycada: Cycleconsistent adversarial domain adaptation. arXiv preprint
arXiv:1711.03213, 2017.
Hosseini-Asl, E., Zhou, Y., Xiong, C., and Socher, R. Augmented cyclic adversarial learning for domain adaptation.
arXiv preprint arXiv:1807.00374, 2018.

On Learning Invariant Representations for Domain Adaptation

Johansson, F. D., Ranganath, R., and Sontag, D. Support andinvertibility in domain-invariant representations. arXiv
preprint arXiv:1903.03448, 2019.

Tzeng, E., Hoffman, J., Saenko, K., and Darrell, T. Adversarial discriminative domain adaptation. arXiv preprint
arXiv:1702.05464, 2017.

Kifer, D., Ben-David, S., and Gehrke, J. Detecting change indata streams. In Proceedings of the Thirtieth international
conference on Very large data bases-Volume 30, pp. 180–
191. VLDB Endowment, 2004.

Zhang, K., Schölkopf, B., Muandet, K., and Wang, Z. Domain adaptation under target and conditional shift. In
International Conference on Machine Learning, pp. 819–
827, 2013.

Lee, J. and Raginsky, M. Minimax statistical learning withwasserstein distances. In Advances in Neural Information
Processing Systems, pp. 2692–2701, 2018.

Zhang, Y., Barzilay, R., and Jaakkola, T. Aspect-augmented
adversarial networks for domain adaptation. arXiv
preprint arXiv:1701.00188, 2017.

Lin, J. Divergence measures based on the Shannon entropy.
IEEE Transactions on Information Theory, 37(1):145–
151, 1991.

Zhao, H., Zhang, S., Wu, G., Gordon, G. J., et al. Multiple
source domain adaptation with adversarial learning. In
International Conference on Learning Representations,2018a.

Lipton, Z. C., Wang, Y.-X., and Smola, A. Detecting andcorrecting for label shift with black box predictors. arXiv
preprint arXiv:1802.03916, 2018.
Long, M., Wang, J., Ding, G., Sun, J., and Yu, P. S. Transfer
joint matching for unsupervised domain adaptation. In
Proceedings of the IEEE conference on computer visionand pattern recognition, pp. 1410–1417, 2014.
Long, M., Cao, Y., Wang, J., and Jordan, M. Learningtransferable features with deep adaptation networks. In
International Conference on Machine Learning, pp. 97–
105, 2015.
Long, M., Zhu, H., Wang, J., and Jordan, M. I. Unsupervised
domain adaptation with residual transfer networks. In
Advances in Neural Information Processing Systems, pp.
136–144, 2016.
Mansour, Y. and Schain, M. Robust domain adaptation. In
ISAIM, 2012.
Mansour, Y., Mohri, M., and Rostamizadeh, A. Domain
adaptation: Learning bounds and algorithms. arXiv
preprint arXiv:0902.3430, 2009a.
Mansour, Y., Mohri, M., and Rostamizadeh, A. Multiple
source adaptation and the rényi divergence. In Proceedings of the Twenty-Fifth Conference on Uncertainty in
Artificial Intelligence, pp. 367–374. AUAI Press, 2009b.
Pei, Z., Cao, Z., Long, M., and Wang, J. Multi-adversarial
domain adaptation. 2018.
Shen, J., Qu, Y., Zhang, W., and Yu, Y. Wasserstein distanceguided representation learning for domain adaptation. In
Thirty-Second AAAI Conference on Artificial Intelligence,2018.
Shrivastava, A., Pfister, T., Tuzel, O., Susskind, J., Wang,
W., and Webb, R. Learning from simulated and unsupervised images through adversarial training. arXiv preprint
arXiv:1612.07828, 2016.

Zhao, H., Zhang, S., Wu, G., Moura, J. M., Costeira, J. P.,
and Gordon, G. J. Adversarial multiple source domain
adaptation. In Advances in Neural Information Processing Systems, pp. 8568–8579, 2018b.
Zhao, H., Hu, J., Zhu, Z., Coates, A., and Gordon, G. J.
Deep generative and discriminative domain adaptation.
In Proceedings of the 18th International Conference on
Autonomous Agents and MultiAgent Systems, 2019.