Source-linked AI summary
On Learning Invariant Representation for Domain Adaptation
Han Zhao, Remi Tachet des Combes, Kun Zhang, Geoffrey J. Gordon
TL;DR
The paper examines whether invariant representations and small source error guarantee successful unsupervised domain adaptation. It constructs a counterexample, derives upper and lower bounds incorporating conditional shift and label-distribution differences, and reports empirical corroboration of the theoretical findings.
Problem
It is unclear whether aligned representations and small source error suffice for target generalization in unsupervised domain adaptation.
Method
The paper constructs a counterexample and proves target- and joint-error upper and lower bounds for invariant-representation approaches.
Results
The results show that invariant representations with small source error are not sufficient for target generalization and can produce large joint error.
Takeaways & Limitations
Successful adaptation requires accounting for conditional shift and task-related information when designing invariant-representation methods.
Takeaways & Limitations
The paper leaves open how feature transformations can reduce conditional shift and when label distributions can be aligned without labeled target data.
Abstract
from arXiv · showhide
Due to the ability of deep neural nets to learn rich 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 the learnt representation, together with the hypothesis learnt from the source domain, can generalize to the target domain. In this paper, we first construct a simple counterexample showing that, contrary to common belief, the above conditions are not sufficient to guarantee successful domain adaptation. In particular, the counterexample exhibits \emph{conditional shift}: the class-conditional distributions of input features change between source and target domains. To give a sufficient condition for domain 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 by proving an information-theoretic lower bound on the joint error of \emph{any} domain adaptation method that attempts to learn invariant representations. Our result characterizes 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. 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 paper questions whether domain-invariant representations and low source error suffice for target generalization. It motivates this question through practical data-collection constraints and reported adaptation failures.
- Motivation: Unsupervised domain adaptation transfers knowledge from labeled source data to an unlabeled target domain.It addresses settings where large-scale supervised data are expensive or time-consuming to collect.
- Motivation: Recent adaptation methods learn intermediate features whose source and target distributions are the same while minimizing source error.
- Research question: Aligned representations and small source error may fail to guarantee target generalization, including for closely related source-target pairs.The paper cites digit classification from MNIST to SVHN as an example of reported failure.
- Research question: The paper asks whether invariant representations with small source error guarantee small target error and, if not, which conditions do.
- Contributions: A counterexample shows that perfectly aligned representations and small source error are insufficient, motivating bounds that account for conditional shift.The supplied figure caption depicts perfect pre-transformation classification but large post-transformation joint error despite aligned distributions.
2 Preliminary
The paper formalizes domain adaptation with source and target distributions, labeling functions, feature transformations, hypotheses, risks, and distribution discrepancies. Its setup treats adaptation as learning a representation and source-trained hypothesis whose target error is controlled.
- Notation: A domain consists of an input distribution and labeling function, with source and target domains denoted separately.The representation space is induced from the input space by a feature transformation g.
- Notation: Hypothesis error is the expected disagreement with the labeling function under a domain, reducing to misclassification probability for binary functions.
- Problem setup: Unsupervised adaptation uses labeled source samples and unlabeled target samples to seek small target error from source training error.The formal goal is to determine conditions and algorithms under which small empirical source risk implies small target risk.
- Distribution discrepancy: The H-divergence measures the largest difference in event probabilities between two distributions over sets induced by a hypothesis class.Its value depends on the richness of the hypothesis class and can range from zero for constant hypotheses to total variation for all measurable binary functions.
- Adaptation bound: The standard adaptation bound includes empirical source risk, source-target distribution discrepancy, and optimal joint risk.The joint-risk term limits adaptation when no hypothesis performs well on both domains.
- Invariant representations: Invariant-representation methods jointly seek close induced source-target distributions and small empirical source error.
3 Related Work
Related work studies domain adaptation through multiple distribution distances and includes adversarial methods that learn source-target-indistinguishable features. The paper situates its analysis primarily within the H-divergence framework.
- Distribution measures: Domain adaptation methods use distances including H-divergence, maximum mean discrepancy, and Wasserstein distance.
- Adversarial adaptation: Domain-adversarial neural networks learn domain-invariant features through adversarial training that makes source and target representations indistinguishable.
4 Theoretical Analysis
The analysis shows that invariant representations and low source error do not by themselves ensure target success: conditional shift can make the target error large. It then gives an upper bound incorporating labeling-function shift and a lower bound showing that differing label marginals constrain invariant-representation methods.
- Counterexample: A one-dimensional counterexample has a hypothesis with zero error on both domains, yet an invariant transformation makes every representation-space hypothesis incur joint error 1.The transformation perfectly aligns the induced source and target marginals, but forces any hypothesis to err on exactly one domain at each represented input.
- Counterexample: Under the invariant transformation, reducing source error increases target error because the transformed source and target labeling functions are far apart.The standard bound becomes vacuous because its optimal joint-error term changes from 0 before transformation to 1 after transformation.
- Generalization upper bound: The proposed upper bound replaces the pessimistic joint-error term with the minimum expected distance between source and target labeling functions.The bound is εT(h) ≤ εS(h) + d̃H(DS, DT) + min{EDS[|fS − fT|], EDT[|fS − fT|]}.
- Generalization upper bound: The empirical bound combines source error, empirical marginal discrepancy, labeling-function shift, hypothesis-complexity terms, and finite-sample error.Its components separate domain-adaptation quantities from complexity measures and sampling effects.
- Information-theoretic lower bound: When source and target marginal label distributions differ, invariant representations face an intrinsic lower bound on joint error.If the induced representation distributions are perfectly aligned, the target error can increase when source error and representation invariance are minimized; the result also extends to separate source and target transformations.
- Information-theoretic lower bound: The lower-bound result identifies marginal-label matching as task-related information that must be considered when designing invariant-representation adaptation methods.The paper notes that the bound can become trivial in some cases, while still emphasizing the role of marginal label distributions.
5 Experiments
Experiments on MNIST, USPS, and SVHN show that DANN adaptation accuracy can peak early and then decline while source accuracy continues increasing. The decline is associated with differing label distributions and supports the theoretical claim that over-training can hurt target generalization.
- Experimental setup: The experiments evaluate digit classification across MNIST, USPS, and SVHN, whose label distributions are shown for comparison.The datasets contain 10 classes and differ in train/test sizes.
- Adaptation trajectories: DANN adaptation accuracy rapidly increases in an initial phase lasting fewer than 10 iterations, then gradually decreases after reaching a peak.The reported trajectories contain two distinct accuracy phases.
- Adaptation trajectories: Source training accuracy continues increasing smoothly even as target-domain adaptation accuracy declines.The negative least-squares slopes of the adaptation curves highlight this divergence.
- Interpretation: The results imply that over-training the feature transformation and discriminator can hurt target generalization when label distributions differ.Additional experiments with artificially unbalanced datasets and more powerful networks show similar behavior.
6 Conclusion and Future Work
The paper concludes that invariant representations and low source error do not by themselves guarantee target generalization. It provides upper and lower error bounds and identifies conditional-distribution alignment as an important direction for future domain adaptation methods.
- Conclusions: Invariant representations combined with small source error are not sufficient to guarantee target generalization.The conclusion frames this as the central theoretical and empirical finding.
- Conclusions: The paper proves upper and lower bounds for target and joint errors that translate into sufficient and necessary conditions for adaptation success.These bounds are presented as tools for understanding when adaptation can succeed.
- Future work: Future work includes designing algorithms that align conditional distributions and characterizing feature transformations that reduce conditional shift.The authors also identify label-distribution alignment without explicit target labels as an open direction.
A Missing Proofs
This appendix supplies proofs for the paper’s domain-adaptation bounds, including empirical generalization control and an information-theoretic lower bound. The results connect target error to source error, distribution discrepancy, labeling-function shift, and label-distribution mismatch.
- Upper bounds: Theorem 4.1 bounds target error by source error, representation discrepancy, and the smaller expected disagreement between source and target labeling functions.The bound is εT(h) ≤ εS(h) + d ˜H(DS, DT) + min{EDS[|fS − fT|], EDT[|fS − fT|]}.
- Upper bounds: Theorem 4.2 gives an empirical target-error bound using empirical source error, empirical discrepancy, Rademacher complexities, and labeling-function disagreement.The complexity terms control estimation from finite source and target samples.
- Proof strategy: The proof of the empirical bound combines concentration inequalities for source error and discrepancy with a union bound.Lemmas 4.3 and 4.5 provide the two probabilistic controls used in the final step.
B Technical Tools
The technical appendix reviews concentration through Rademacher complexity, contraction for function compositions, Jensen–Shannon divergence bounds, and the data processing inequality. These tools support the paper’s generalization and information-theoretic analyses.
- Generalization tools: The appendix uses empirical Rademacher complexity to control deviations between empirical and expected errors.The cited concentration lemma applies uniformly over a function class with probability at least 1 − δ.
- Generalization tools: Ledoux–Talagrand’s contraction lemma bounds the Rademacher complexity of composite functions when the outer function is Lipschitz.The appendix states the result for a Lipschitz function φ with parameter L.
- Information-theoretic tools: Lin’s lemma upper-bounds Jensen–Shannon divergence between distributions using their L1, or total variation, distance.This provides a divergence comparison used in the appendix’s information-theoretic arguments.
- Information-theoretic tools: The data processing inequality states that mutual information cannot increase along a Markov chain X → Z → Y.The appendix uses this principle to relate information in representations and predictions.
C Additional Experiments
Additional experiments artificially create label-distribution imbalance between MNIST and USPS, and DANN results show the predicted effect is enhanced as the discrepancy grows.
- The experiments remove samples from source-domain classes to create two unbalanced MNIST-to-USPS adaptation tasks.One task removes 70% of MNIST digits 0–4; the other removes 70% of digit 0 and all classes above 2.
- The observed effect is enhanced by the larger label-distribution discrepancy, consistent with the theoretical and experimental findings.The plotted results average five random seeds, with variability substantially smaller than the observed trend.
- Figure 4 compares target test accuracy without adaptation against DANN adaptation results and fits a dashed line to emphasize their negative slope.