Abstract
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.
Introduction
In classical machine learning, the standard assumption is that training (source) and test (target) data are drawn from the same distribution. However, in many real-world scenarios, such as sentiment analysis across different product categories, this assumption is violated. This discrepancy between domains often leads to a significant drop in model performance. While previous theoretical work established bounds for binary classification using the $d_A$ distance, these results were limited to 0-1 loss and often produced loose bounds. This paper introduces a more general and tighter framework for domain adaptation based on a novel "discrepancy distance."
The Discrepancy Distance
The central contribution of this work is the Discrepancy Distance ($disc_L$). Unlike standard statistical measures like KL-divergence, the discrepancy distance is task-specific. It measures the difference between two distributions $P$ and $Q$ relative to a hypothesis set $H$ and a loss function $L$. Formally, it identifies the maximum difference in expected loss between any two hypotheses in $H$ when evaluated on $P$ versus $Q$.
By focusing on the model's capacity and the specific objective, this distance provides a more relevant metric for machine learning than purely statistical distances. The authors demonstrate that this discrepancy can be estimated from finite samples using Rademacher complexity, allowing for data-dependent measurements of domain shift.
Generalization Bounds and Algorithms
Using the discrepancy distance, the authors derive new generalization bounds for the target error. These bounds are notably tighter than previous results because they minimize the reliance on terms involving the unknown target labeling function.
To practically address domain shift, the paper proposes algorithms for discrepancy minimization through source data reweighting. The goal is to find a set of weights for the source samples such that the weighted source distribution minimizes the discrepancy with the target distribution.
For classification with 0-1 loss, this optimization can be framed as a Linear Program (LP). In the specific case of 1D data, the authors provide a highly efficient linear-time combinatorial algorithm. For regression tasks using square loss, the problem is cast as a Semidefinite Program (SDP), which remains solvable in polynomial time.
Experimental Validation
The theoretical framework was validated through synthetic experiments. In a 1D classification task with shifted Gaussian distributions, a standard model trained on the source domain achieved only ~50% accuracy on the target. Applying the discrepancy minimization algorithm improved target accuracy to over 85%. Similarly, in 16D ridge regression experiments, the reweighting strategy significantly reduced Mean Squared Error (MSE), bringing performance close to that of a model trained directly on target data.
Conclusion and Future Work
This work provides a principled foundation for domain adaptation across various loss functions. By treating reweighting as an optimization problem tied to generalization bounds, it moves beyond heuristic adaptation methods. Key insights include the importance of task-aware distribution distances and the feasibility of minimizing discrepancy through convex optimization. Future research will focus on scaling these algorithms to high-dimensional, large-scale real-world datasets in fields like NLP and computer vision, where computational efficiency and label mismatch remain significant challenges.
Summary updated