PaperlayerView exact revision on arXiv

Source-linked AI summary

Theoretical Analysis of Domain Adaptation with Optimal Transport

Ievgen Redko, Amaury Habrard, Marc Sebban

arXiv:1610.04420v4stat.MLcs.LG

TL;DR

Domain adaptation requires guarantees when source and target distributions differ, but existing divergences may not capture data geometry. The paper uses Wasserstein distance to derive bounds across unsupervised, labeled-source-and-target, and multi-source settings, concluding that the resulting analysis can be tighter than alternatives while requiring transport regularization for effective source learning.

  • Problem

    Domain adaptation needs generalization guarantees when source and target distributions differ, with existing bounds depending on distribution divergence and a joint-error capability term.

  • Method

    The paper derives domain-adaptation bounds using Wasserstein distance for unsupervised, combined labeled-data, and multiple-source learning settings.

  • Results

    The resulting Wasserstein-based bounds can be tighter than bounds using total variation, Rényi-related divergences, or discrepancy distance.

  • Takeaways & Limitations

    The bounds support measuring source-target distance with Wasserstein distance while retaining a capability term for a hypothesis performing well on both domains.

  • Takeaways & Limitations

    Minimizing Wasserstein distance alone may fail when transport does not preserve labels, so regularization is needed to support source-error minimization.

Abstract

from arXiv · show

Domain adaptation (DA) is an important and emerging field of machine learning that tackles the problem occurring when the distributions of training (source domain) and test (target domain) data are similar but different. Current theoretical results show that the efficiency of DA algorithms depends on their capacity of minimizing the divergence between source and target probability distributions. In this paper, we provide a theoretical study on the advantages that concepts borrowed from optimal transportation theory can bring to DA. In particular, we show that the Wasserstein metric can be used as a divergence measure between distributions to obtain generalization guarantees for three different learning settings: (i) classic DA with unsupervised target data (ii) DA combining source and target labeled data, (iii) multiple source DA. Based on the obtained results, we provide some insights showing when this analysis can be tighter than other existing frameworks.

1 Introduction

Domain adaptation addresses learning when source and target distributions differ, making conventional same-distribution generalization assumptions unreliable. The paper motivates Wasserstein-based analysis as a geometry-aware alternative for deriving adaptation guarantees.

  • Classic generalization bounds assume training and test data follow the same distribution, an assumption often violated in real-world applications.
  • Domain adaptation learns from a source distribution while accounting for a potentially different target distribution.
  • Existing DA guarantees bound target risk using source risk, inter-domain divergence, and a joint-error capability term.
  • Minimizing divergence between source and target distributions is identified as a key factor in the potential success of DA algorithms.
  • Existing divergences do not directly incorporate data-distribution geometry, motivating optimal-transport approaches based on Wasserstein distance.
  • The paper develops Wasserstein generalization bounds for single- and multi-source DA scenarios.

2 Definitions and notations

The paper introduces optimal transport as a framework for comparing and aligning source and target distributions in domain adaptation. It defines Wasserstein distance through transport couplings and describes its use in sample alignment and DA formalization.

  • 2.1 Optimal transport: Optimal transport seeks a minimum-cost probabilistic coupling between two probability measures with prescribed marginals.
  • 2.1 Optimal transport: The Wasserstein distance is defined from the optimal transport solution between source and target probability measures.
  • 2.1 Optimal transport: The transport cost uses a function c to measure moving unit mass from x to y, while Π(µS, µT) contains couplings with the required marginals.
  • 2.1 Optimal transport: The analysis focuses on p = 1, while higher-order Wasserstein results can be obtained using Hölder inequality and Wp ≤ Wq for p ≤ q.
  • 2.1 Optimal transport: In discrete settings, optimal transport is expressed through a coupling matrix and a cost matrix for empirical source and target measures.
  • 2.2 Domain adaptation and optimal transport: DA defines domains through distributions and labeling functions, then uses optimal transport to align source samples with target samples.
  • 2.2 Domain adaptation and optimal transport: Wasserstein-based DA preserves data topology, can be estimated efficiently, and was reported to improve results on benchmark computer-vision datasets.

3 Generalization bounds with Wasserstein distance

The paper derives Wasserstein-based generalization bounds for domain adaptation, relating source and target errors and extending the analysis to empirical measures and labeled target data. It also identifies transport regularization as important because minimizing Wasserstein distance alone need not control source or joint error.

  • 3.1 A bound relating the source and target error: The proof assumes a convex, symmetric, bounded loss with a triangular property and uses an RKHS embedding whose loss function has bounded norm.The loss-induced function belongs to an RKHS, enabling the reproducing-property argument; its norm is assumed bounded by 1, with extension to a general bound M by scaling.
  • 3.1 A bound relating the source and target error: Wasserstein distance provides a bound relating target error to source error for hypotheses in an RKHS.The bound is ϵT(h, h′) ≤ ϵS(h, h′) + W1(µS, µT).
  • 3.1 A bound relating the source and target error: The empirical generalization bound decomposes into source error, Wasserstein discrepancies between population and empirical measures, and a joint-error term λ.The derivation uses convergence guarantees for empirical measures under W1 and the triangle inequality for the Wasserstein metric.
  • 3.1 A bound relating the source and target error: Minimizing Wasserstein distance alone does not ensure small source or joint error unless labeling is preserved by transport.Transport can map differently labeled source instances to the same target point or map positive source examples to negative target instances.
  • 3.1 A bound relating the source and target error: Class-labeled transport regularization controls the trade-off between Wasserstein alignment and source-error minimization by discouraging different classes from sharing target points.The proposed regularization promotes group sparsity in the coupling matrix and is presented as an algorithmic solution for controlling terms in the bound.
  • 3.2 A learning bound for the combined error: With labeled target data, the best hypothesis using both source and target labels performs at least as well as the best hypothesis trained on target data alone.This applies when the source contribution is included, 0 ≤ α < 1, compared with α = 1 for target-only learning.

4 Multi-source domain adaptation

For multiple source domains, the paper derives Wasserstein-based generalization bounds and interprets adaptation through a weighted source error and a barycenter transported toward the target. The analysis motivates using source-distribution barycenters followed by transport to the target.

  • 4 Multi-source domain adaptation: Multi-source domain adaptation combines N labelled source domains, with each source weighted by αj in the empirical multisource error.The weights satisfy Σj=1^N αj = 1.
  • 4 Multi-source domain adaptation: Theorem 4 provides a high-probability generalization bound for the empirical minimizer of the weighted multisource error under fixed source weights.The bound is stated for any fixed α and δ, with probability at least 1 − δ over the samples.
  • 4 Multi-source domain adaptation: The multi-source potential term can be bounded by transporting each weighted source distribution toward an intermediate empirical measure and then transporting that measure to the target.The decomposition includes weighted source-to-intermediate Wasserstein terms and an intermediate-to-target Wasserstein term.
  • 4 Multi-source domain adaptation: The first term is the Wasserstein barycenter objective, whose minimizer defines an empirical barycenter of the source probability measures.The barycenter minimizes a weighted sum of Wasserstein distances to the source measures.
  • 4 Multi-source domain adaptation: The resulting adaptation strategy finds a barycenter of the source distributions and transports it to the target distribution.For Gaussian source distributions, the related multimarginal optimal-transport problem and Wasserstein barycenter have a closed-form solution.

5 Comparison to other existing bounds

The paper compares Wasserstein-based domain-adaptation bounds with divergence-based alternatives. It argues that Wasserstein bounds can be tighter than total-variation-based bounds and computationally advantageous, while also incorporating the geometry of the data space.

  • 5 Comparison to other existing bounds: Existing domain-adaptation bounds differ primarily in the divergence used to measure source-target distribution mismatch.The comparison includes H-divergence, discrepancy distance, and integral probability metric-based bounds.
  • 5 Comparison to other existing bounds: Wasserstein distance yields tighter bounds than the total variation distance used in earlier domain-adaptation theory.The paper also relates Wasserstein distance to Kullback–Leibler and Rényi divergences, while noting that direct discrepancy comparisons can be uninformative.
  • 5 Comparison to other existing bounds: Entropically regularized Wasserstein distance can be computed with the linear-time Sinkhorn–Knopp algorithm regardless of the cost function.The paper presents this as a computational advantage over the other compared distances.
  • 5 Comparison to other existing bounds: Unlike the previously introduced divergences, Wasserstein distance accounts for the geometry of the underlying space.The paper therefore characterizes it as a precise tool for measuring divergence between domains.

6 Conclusion

The paper develops Wasserstein-based generalization bounds for single- and multi-source domain adaptation and draws algorithmic implications from the resulting capability term.

  • The bounds measure source–target distance with the Wasserstein metric in both single- and multi-source learning scenarios.
  • The bounds include a capability term representing the existence of a good hypothesis for both source and target domains.
  • The capability term motivates regularizing the optimal transportation plan so interpolation supports efficient source-domain learning.
  • The analysis reports tighter bounds than total variation and Rényi-divergence frameworks and greater computational attractiveness than one alternative framework.
  • Future work examines whether the cost function used in the bounds applies to real-world domain-adaptation problems.

Supplementary material: Theoretical Analysis of

The supplementary material introduces the proof organization, beginning with Theorem 1 and then developing concentration results for combined errors in single- and multi-source settings.

  • The material first presents the original version of Theorem 1.
  • It then introduces concentration results for combined errors in single-source and multi-source settings.

1 Original formulation of Theorem 1

This section states a concentration theorem for probability measures satisfying a Talagrand-type transport inequality and identifies the meaning of the Tp(λ) condition.

  • Theorem 5 assumes p ∈ [1, 2] and a probability measure on R^d satisfying a Tp(λ) inequality.
  • For d′ > d and λ′ < λ, the theorem provides a constant N0 depending on d′, λ′, and a square exponential moment of the measure.
  • The Tp(λ) condition is described through a Talagrand inequality for probability measures on X.

2 Concentration inequality used in the Proof of Theorem 3

The proof bounds deviations of combined empirical and true errors using bounded differences, symmetrization, and Rademacher averages.

  • McDiarmid’s inequality bounds the deviation by controlling how much the expression changes when one sample vector changes.
  • The empirical–true combined-error difference is first rewritten into a form suitable for concentration analysis.
  • Changing either x_i or y_i changes the expression by at most 2α, determining the concentration denominator.
  • The expected empirical–true error difference is bounded by sums of Rademacher averages using an independent sample and symmetrization.
  • A theorem from Bartlett and Mendelson is used to bound the Rademacher averages and obtain the desired result.

3 Concentration inequality used in the Proof of Theorem 4

The section states a concentration lemma for samples drawn from multiple source distributions and outlines a proof closely related to an earlier lemma. It also addresses the denominator in the exponent and Rademacher complexity bounds.

  • Concentration inequality used in the Proof of Theorem 4: Lemma 3 considers a sample of size n formed by drawing β_j n labeled points from each source distribution μ_Sj.The statement applies under the assumptions of Lemma 1 and covers every hypothesis h with probability at least 1 − δ for fixed α.
  • Concentration inequality used in the Proof of Theorem 4: The proof follows the approach of Lemma 2 but differs in how the denominator of the exponent is defined.
  • Concentration inequality used in the Proof of Theorem 4: The argument also derives a bound involving Rademacher complexities.
Loading 1610.04420v4…