Domain Adaptation: Learning Bounds and Algorithms

Yishay Mansour; Mehryar Mohri; Afshin Rostamizadeh

Source-linked AI summary

Domain Adaptation: Learning Bounds and Algorithms

Yishay Mansour, Mehryar Mohri, Afshin Rostamizadeh

arXiv:0902.3430v3Feb 19, 2009cs.LGcs.AI

TL;DR

Domain adaptation asks how to learn on a target distribution when labeled training data come from a somewhat different source distribution. The paper introduces discrepancy distance and Rademacher-based bounds, then develops adaptation guarantees and discrepancy-minimization algorithms. It reports preliminary experiments showing benefits, while noting limitations of general distance bounds and opportunities for more efficient algorithms.

Problem
Domain adaptation seeks hypotheses with low target loss when labeled source data and target test data come from different distributions.
Method
The paper introduces discrepancy distance for general loss functions, derives Rademacher-complexity and algorithmic adaptation bounds, and develops discrepancy-minimization algorithms.
Results
The paper derives new generalization and regularization-based adaptation bounds and reports preliminary experiments showing benefits from discrepancy-minimization algorithms.
Takeaways & Limitations
Discrepancy distance provides a task-flexible basis for analyzing and adapting learning algorithms across source and target distributions.
Takeaways & Limitations
A bound based on l1 distribution distance can be uninformative because that distance may be large even in favorable adaptation situations.

Abstract

from arXiv · show

This paper addresses the general problem of domain adaptation which arises in a variety of applications where the distribution of the labeled sample available somewhat differs from that of the test data. Building on previous work by Ben-David et al. (2007), we introduce a novel distance between distributions, discrepancy distance, that is tailored to adaptation problems with arbitrary loss functions. We give Rademacher complexity bounds for estimating the discrepancy distance from finite samples for different loss functions. Using this distance, we derive novel generalization bounds for domain adaptation for a wide family of loss functions. We also present a series of novel adaptation bounds for large classes of regularization-based algorithms, including support vector machines and kernel ridge regression based on the empirical discrepancy. This motivates our analysis of the problem of minimizing the empirical discrepancy for various loss functions for which we also give novel algorithms. We report the results of preliminary experiments that demonstrate the benefits of our discrepancy minimization algorithms for domain adaptation.

1 Introduction

Domain adaptation addresses learning when labeled source data and test data come from somewhat different distributions. The paper develops discrepancy-based theory, bounds, algorithms, and preliminary experiments for this setting.

Domain adaptation leverages labeled source data and unlabeled target data to learn a hypothesis performing well on the target domain.
The paper introduces discrepancy distance, which extends distribution comparison beyond 0-1 classification to regression and other loss functions.
Rademacher-complexity bounds establish data-dependent guarantees for estimating discrepancy distance from finite samples.
New domain-adaptation bounds cover regularization-based algorithms, including support vector machines and kernel ridge regression, through empirical discrepancy.
Discrepancy minimization is formulated for 0-1 classification and square-loss regression, with LP, one-dimensional combinatorial, and SDP algorithms.
The paper reports preliminary experiments demonstrating benefits from its discrepancy-minimization algorithms.

2 Preliminaries

The paper formulates domain adaptation with labeled source data, unlabeled target data, and a loss measured under the target distribution. It introduces Rademacher complexity as a data-dependent tool for controlling hypothesis-class complexity.

Learning Set-Up: Training data are drawn from source distribution Q, while test points come from a potentially different target distribution P.
Learning Set-Up: The source and target labeling functions may differ, and adaptation requires this dissimilarity to be small.
Learning Set-Up: The learner receives an unlabeled target sample drawn independently from P and evaluates functions using a general loss function L.
Learning Set-Up: Domain adaptation selects a hypothesis h from H with small expected target loss LP(h, f).
Rademacher Complexity: Rademacher complexity is introduced as a data-dependent measure of function-class complexity for the paper's generalization bounds.
Rademacher Complexity: Empirical Rademacher complexity can be measured from finite samples and may yield tighter bounds than VC-dimension-based measures.
Rademacher Complexity: The paper states a Rademacher bound applying with probability at least 1 − δ uniformly to hypotheses in H.

3 Distances between Distributions

The paper develops discrepancy distance as a task-sensitive alternative to generic distribution distances, extending adaptation analysis beyond 0-1 classification. It establishes finite-sample estimation results and connects the distance to adaptation bounds for several losses.

Motivation: The l1 distance bounds source-target loss differences but can be uninformative when distributions differ substantially despite favorable adaptation conditions.This motivates using a distance tailored to the learning task rather than overall distributional similarity.
dA-distance: For 0-1 classification, dA compares source and target probabilities over regions induced by disagreements between hypotheses.The relevant regions are supports of |h−h′| for pairs of hypotheses because the target labeling function is unknown.
Discrepancy distance: Discrepancy distance extends this task-sensitive comparison to general loss functions and tasks such as regression.It coincides with dA for 0-1 classification and also supports losses such as Lq(y, y′) = |y − y′|^q.
Properties: The discrepancy distance is symmetric and satisfies the triangle inequality, but it may be zero for distinct distributions and therefore need not be a true metric.This non-separation can occur even for bounded linear hypothesis classes with standard continuous losses.
Finite-sample estimation: Rademacher-complexity bounds show that discrepancy distance can be estimated from finite samples for bounded losses, including regression and classification.The results include data-dependent bounds, sharper than corresponding VC-dimension statements, and convergence results when the loss-composed class has finite pseudo-dimension.
Finite-sample estimation: The analysis yields analogous results for classification and supports estimating discrepancy between empirical source and target distributions from finite samples.The proofs use loss-specific Rademacher bounds, including contraction arguments for Lq regression and related results for 0-1 loss.

4 Domain Adaptation: Generalization Bounds

The section develops domain-adaptation bounds that relate target error to source behavior, labeling-function proximity, and discrepancy between source and target distributions. It also extends guarantees to regularization-based algorithms under assumptions including convexity, boundedness, or small source–target labeling disagreement.

Generalization bounds: The section addresses how target loss differs from empirical source loss and how source-trained and target-trained hypotheses compare.The authors state that their theoretical guarantees address both questions.
Generalization bounds: Theorem 8 provides an adaptation bound for symmetric losses satisfying the triangle inequality.The bound is expressed using target error, discrepancy, and a best-in-class hypothesis term.
Generalization bounds: Compared with an earlier adaptation bound, Theorem 8 can use fewer target-function error terms and yields a smaller bound in the single-hypothesis, single-target-function case.In that case, the new bound is LP(h, f) + disc(P, Q), whereas the earlier bound includes 2LQ(h, f) + LP(h, f) + disc(P, Q).
Generalization bounds: Under small discrepancy and small best-in-class source loss, target regret is essentially bounded by source loss relative to the source best hypothesis.The specialized bound is LP(h, fP) ≤ LP(h∗, fP) + LQ(h, h∗) + disc(P, Q).
Regularization-based algorithms: For regularization-based algorithms, the results provide pointwise loss-difference guarantees and apply to SVMs with positive-definite symmetric kernels and kernel ridge regression.The guarantees use convex regularization objectives and assumptions such as σ-admissibility and agreement of labeling functions on the empirical source support.
Regularization-based algorithms: The square-loss extensions allow source and target labeling functions to differ when their empirical disagreement is small.Theorems 12 and 13 separately consider the cases where fP belongs to H and where it does not.

5 Discrepancy Minimization Algorithms

The paper minimizes empirical discrepancy by reweighting the source distribution while preserving its support, deriving optimization formulations and efficient algorithms for classification and regression.

Discrepancy minimization: Reweighting the source distribution can reduce empirical discrepancy while preserving its support, changing the cost assigned to errors on labeled points.The optimized distribution can emphasize or de-emphasize training points and is distinct from earlier importance-weighting objectives.
Classification, 0-1 loss: For 0-1 loss, discrepancy minimization becomes a min-max program and then a linear program with finitely many constraints determined by distinct intersections with the sample.Sauer’s lemma bounds the required constraints using the VC-dimension of H∆H.
Limits of minimization: A large unlabeled target region imposes an unavoidable lower bound on empirical discrepancy, so small discrepancy cannot be achieved in that case.The bound follows because such a region has no source support and contributes its target mass to the discrepancy for every reweighting.
Classification, 0-1 loss: In one dimension, a linear-time algorithm reaches the lower bound, making the minimum discrepancy equal to the smallest target mass of an unlabeled region.For half-spaces on the real line, the algorithm assigns each labeled point the weights of consecutive unlabeled points to its right, after sorting the combined supports.
Computing the discrepancy in 1D: The one-dimensional optimal weights satisfy bQ′(si) = ni/n and can be computed in O((m + n) log(m + n)) time.The weights are based on the number of consecutive unlabeled points following each labeled point.
Regression, L2 loss: For square loss with bounded linear hypotheses, discrepancy minimization is formulated through a maximum-eigenvalue problem and solved using a semidefinite-programming approach.The matrix is symmetric and affine in the distribution weights; the resulting algorithm has a stated polynomial-time bound.

6 Experiments

Preliminary experiments evaluate discrepancy-minimizing weights for classification and ridge regression under shifted source and target distributions. The results report reduced discrepancy and improved target-domain accuracy or prediction selection.

Experimental overview: The experiments report that discrepancy-minimizing algorithms reduce empirical discrepancy and improve accuracy with respect to the target domain.The experiments use weighted source distributions to train hypotheses closer to the target under the discrepancy metric.
Classification: In one dimension, classification compares unweighted and weighted training as accuracy varies with the number of training points.Figure 3 uses shifted Gaussian source and target distributions, with ten times as many unlabeled as labeled points and error bars of ±1 standard deviation.
Classification: With source and target Gaussians centered at −1 and +1, respectively, unweighted training errs on about half of target test points, whereas discrepancy-minimizing weighting improves target performance.The hypothesis class is half-spaces and the target function is the interval [−1, 1].
Ridge regression: For ridge regression, discrepancy-minimizing weights reduce discrepancy and assist selection of a more appropriate target-domain hypothesis.The experiment applies the derived SDP to shifted Gaussian distributions and extends the comparison to 16 dimensions.

7 Conclusion

The paper presents a broad theoretical and algorithmic analysis of domain adaptation, with applicability across adaptation tasks. More efficient or approximate algorithms are identified as a route toward larger-scale use.

Conclusion: The analysis and algorithms are described as widely applicable and able to benefit a variety of domain-adaptation tasks.The conclusion frames broader applicability as a consequence of the paper’s theoretical and algorithmic coverage.
Conclusion: More efficient algorithm versions and efficient approximations could extend these techniques to large-scale adaptation problems.This is presented as a future direction rather than an established experimental result.

A Proof of Theorem 2

The proof bounds deviations of empirical quantities using bounded differences and empirical Rademacher complexity. McDiarmid’s inequality is applied to both the relevant function and the complexity term before combining the bounds.

Proof strategy: Changing one sample point changes Φ(S) by at most 1/m, enabling a McDiarmid bound for Φ(S).The resulting statement holds uniformly over hypotheses with probability at least 1 − δ.
Proof strategy: The expectation of Φ(S) is bounded using empirical Rademacher complexity.This supplies the complexity-dependent component needed for the theorem.
Proof strategy: Changing one sample point changes Rm(H) by at most 2/m, so McDiarmid’s inequality also controls the complexity term.This step is stated with probability at least 1 − δ/2.
Proof conclusion: Combining the McDiarmid bound with the bound on E_S[Φ(S)] yields the theorem.The proof concludes by combining the complexity estimate and concentration inequalities.

B Rademacher Classification Bound

The theorem gives a Rademacher classification bound for binary-valued hypotheses under 0-1 loss and a distribution Q.

Theorem 14 considers functions from X to {0, 1} under the 0-1 loss.
With probability at least 1−δ, the stated inequality holds for all samples S of size m drawn according to Q.
The bound is presented as a Rademacher classification bound for the hypothesis family H.

C Discrepancy Minimization with Kernels and L2 loss

The kernel-based discrepancy-minimization problem for square loss can be transformed into a convex semidefinite program using the kernel Gram matrix.

The high-dimensional extension takes H to be the reproducing kernel Hilbert space associated with a positive definite symmetric kernel K.
For square loss, determining the discrepancy-minimizing distribution can be cast as an SDP depending only on the Gram matrix of K.
The optimization variables z_i represent reweighted values bQ′(s_i) on source-sample elements.
The matrix A is diagonal with entries bP(s_i)−z_i, while the remaining target-sample variables are set to zero.
Adding tI makes B=A+tI positive definite for sufficiently large t, enabling the factorization used in the spectral transformation.
The transformed matrix K^1/2BK^1/2 has the same relevant non-zero eigenvalues as the feature-space matrix, establishing the kernel formulation.
The diagonal matrix A0 and coordinate matrices I_i make M′(z) affine in z, so the resulting problem is convex and expressible as an SDP.

D Standard Form of SDP Problem

This section formulates the discrepancy-minimization problem as an SDP and explains its standard solver representation.

The inequality form of the semidefinite program is explicitly formulated from equation (41).
The constraints −z_i ≤ 0 for all i can be combined into one linear matrix inequality using a block-diagonal matrix.
The dual problem is presented in standard form for direct submission to solvers such as SeDuMi.
Each variable z_i can be recovered as the Lagrange multiplier for its corresponding equality constraint.

Weighte Unweigh

The supplied passage contains a fragment referring to target and source weighting.

The fragment mentions target and source quantities in connection with weighting.
The passage does not state a complete weighting procedure.
No quantitative weighting result is reported in the passage.