On Learning Invariant Representations for Domain Adaptation†‡††,‡Han Zhao , Remi Tachet des Combes , Kun Zhang & Geoffrey J. Gordon†‡Carnegie Mellon University, Microsoft Research Montreal
han.zhao@cs.cmu.edu, kunz1@andrew.cmu.edu, {remi.tachet, geoff.gordon}@microsoft.com

Previous Theoretical Result: Given hypothesis class H and AH :={h−1(1) | h ∈ H}, the H-divergence is: dH(D, D0) :=supA∈AH | PrD (A) − PrD0(A)|. Generalization bound for binary classification (Blitzer et al. NeurIPS’ 08), ∀h ∈ H:Our generalization upper bound on the target error: Let hDS , fS iand hDT , fT i be the source and target domains. For any function classH ⊆ [0, 1]X , and ∀h ∈ H, the following inequality holds:

Target images without labels

Source images with labels

Domain Adversarial Neural Network (DANN):εS (h) + dH∆H(DS , DT )|{z00:
where H̃ = {sgn(|h(x) − h (x)| − t) | h, h ∈ H, 0 ≤ t ≤ 1}.

∗+λ}To be minimized by learning invariant representations• εS (h)/εT (h): population source/target binary classification error.
• dH∆H(DS , DT ): divergence between source and target domains.
• λ∗ := minh0∈H εS (h0) + εT (h0), the optimal joint error.
A counter-example:
g(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=0target domain

1)

y=1

y=0x
1

0.5
0
y=0
y=1

0.5

1

1.5x

2

1

0.5

0

0.5
y=0

source domain

1

1.5

2

y=1

source domain

Question:
Is finding invariant representations while at the same timeachieving a small source error sufficient to guarantee a small
target error? If not, under what conditions is it?
Our Answer: No, and it provably hurts if the label distributions aredifferent! Only sufficient when conditional distributions are close.

0,fS (x) = 1,DS = U (−1, 0),x ≤ −1/2
x > −1/2

0, x ≥ 3/2
fT (x) = 1,x < 3/2

DT = U (1, 2),Experiments

Optimal hypothesis: h∗(x) = 1 iff x ∈ (−1/2, 3/2) with λ∗ = 0.
Feature transformation:

Our Contributions:• A simple counter-example that invalidates domain adaptation
algorithms based on matching marginal distributions.
• Sufficient condition: a generalization upper bound that suggests
matching conditional distributions.
• Necessary condition: an information-theoretic lower bound thatsuggests matching marginal label distributions.
• Empirical results that corroborate our theoretical analysis.

g(x) = Ix≤0(x) · (x + 1) + Ix>0(x) · (x − 1)

Digit classification on MNIST, USPS and SVHN (DSY 6= DTY ):After adaptation: Perfect domain alignment: dH∆H(DS0 , DT0 ) = 0. But,

0,0fS (x) = 
1,
0,0fT (x) = 1,DS0 = U (0, 1),0DT = U (0, 1),Now ∀h : R 7→ {0, 1},00x ≤ 1/2x > 1/2x ≥ 1/2x < 1/200∗

εS (h ◦ g) + εT (h ◦ g) = 1, hence λ = 1.

Implication: In this example, minimizing the source error whilealigning domains will only increase the target error.

ICML-2019

Our information-theoretic lower bound on the joint error: SupghYYZZpose X −→ Z −→ Ŷ holds, and dJS(DS , DT ) ≥ dJS(DS , DT ), then:
21
YYZZ
εS (h ◦ g) + εT (h ◦ g) ≥ dJS(DS , DT ) − dJS(DS , DT ) .
2• dJS(·, ·): Jensen-Shannon distance between distributions.
• DSY /DTY : source/target marginal label distributions.
Extension: Different transformations for the S/T domains don’t help:
Let gS , gT be the source and target transformation functions from X toZ. Suppose dJS(DSY , DTY ) ≥ dJS(DSZ , DTZ ), then:21YYZZεS (h ◦ gS ) + εT (h ◦ gT ) ≥ dJS(DS , DT ) − dJS(DS , DT ) .
2Before adaptation:
• Free of the unavailable term λ∗ := minh0∈H εS (h0) + εT (h0).
• Incorporate the conditional shiftmin{EDS [|fS − fT |], EDT [|fS − fT |]} into the analysis.
• Also holds for (bounded) regression problems.

USPS - SVHN

εT (h) ≤εT (h) ≤ εS (h) + dH̃(DS , DT ) + min{EDS [|fS − fT |], EDT [|fS − fT |]},

SVHN - USPSAdaptation

Theoretical Analysis

USPS - MNISTUnsupervised Domain Adaptation: Source 6= Target

A Simple Example

SVHN - MNIST

Overview

han.zhao@cs.cmu.edu

Conclusion: When the label distributions are different, aligning bothdomains while minimizing the source error leads to an increasing target error during training.

June 11, 2019