A General Upper Bound for Unsupervised Domain Adaptation

Dexuan Zhang, Tatsuya HaradaarXiv 2019 · OpenReview

Abstract

In this work, we present a novel upper bound of target error to address the problem for unsupervised domain adaptation. Recent studies reveal that a deep neural network can learn transferable features which generalize well to novel tasks. Furthermore, a theory proposed by Ben-David et al. (2010) provides a upper bound for target error when transferring the knowledge, which can be summarized as minimizing the source error and distance between marginal distributions simultaneously. However, common methods based on the theory usually ignore the joint error such that samples from different classes might be mixed together when matching marginal distribution. And in such case, no matter how we minimize the marginal discrepancy, the target error is not bounded due to an increasing joint error. To address this problem, we propose a general upper bound taking joint error into account, such that the undesirable case can be properly penalized. In addition, we utilize constrained hypothesis space to further formalize a tighter bound as well as a novel cross margin discrepancy to measure the dissimilarity between hypotheses which alleviates instability during adversarial learning. Extensive empirical evidence shows that our proposal outperforms related approaches in image classification error rates on standard domain adaptation benchmarks.

Introduction

Unsupervised Domain Adaptation (UDA) aims to leverage a labeled source domain to improve performance on an unlabeled target domain. A foundational theory by Ben-David et al. (2010) suggests that target error can be bounded by minimizing source error and the discrepancy between marginal distributions. However, this approach often overlooks the "joint error"—the risk that samples from different classes are mixed during distribution matching.

The Joint Error Challenge

Standard adversarial methods for UDA focus on aligning the "shape" of feature distributions. While this can reduce marginal discrepancy, it does not guarantee that class labels remain aligned. If "Source Class A" is mapped to "Target Class B," the distributions may appear matched, but the model's accuracy on the target domain will plummet. This phenomenon is characterized by an increase in joint error.

Illustration of the joint error problem where matching marginal distributions can lead to class misalignment.

As shown in Figure 1, even when marginal distributions are matched, a large discrepancy between the optimal labeling functions of the two domains can lead to significant target error. This "joint error" must be explicitly accounted for to ensure reliable adaptation.

Proposed Methodology

To address these limitations, the authors propose a more robust theoretical framework and a corresponding optimization algorithm.

1. A General Upper Bound

The authors derive a novel upper bound for target error that explicitly incorporates a term for the discrepancy between the optimal labeling functions of the source and target domains. This mathematical penalty prevents the "undesirable case" where classes are misaligned during adaptation.

2. Constrained Hypothesis Spaces

To ensure the bound is tight and optimizable, the search space for classifiers is restricted. The authors propose two strategies:

  • Source Accuracy Constraint: Restricts the classifier to maintain high performance on the source domain.
  • Pseudo-label Constraint: Incorporates target domain structure by using pseudo-labels to further refine the hypothesis space.
Visualization of the constrained hypothesis space strategy to minimize target error.

Figure 2 illustrates how these constraints guide the feature extractor to align distributions while respecting class boundaries, effectively minimizing the joint error term.

3. Cross Margin Discrepancy (CMD)

A key algorithmic contribution is the Cross Margin Discrepancy (CMD) metric. Unlike standard 0-1 loss or simple distance metrics, CMD utilizes a margin-based loss derived from the logarithm of softmax outputs. This "flatter" loss function near decision boundaries provides more stable gradients, preventing the feature extractor from making erratic updates during adversarial training.

Empirical Evaluation

The proposed method was evaluated on standard benchmarks including Digits (MNIST, SVHN, USPS), VisDA-2017, and Office-Home.

  • MNIST → SVHN: In this challenging shift, the method achieved 50.3% accuracy, a significant improvement over the previous state-of-the-art (MCD) at ~11%.
  • VisDA-2017: On the large-scale synthetic-to-real task, the approach reached 79.7% average accuracy, outperforming GPDA (73.3%) and MDD (61.1%).
  • Stability: Qualitative analysis confirmed that CMD leads to faster and more stable convergence compared to standard Maximum Classifier Discrepancy (MCD).

Conclusion

By explicitly accounting for joint error and introducing the CMD metric, this work provides a more stable and theoretically grounded approach to UDA. The results demonstrate that constraining the hypothesis space and smoothing the adversarial objective are critical for successful adaptation in complex, real-world scenarios.

Summary updated

Abstract

In this work, we present a novel upper bound of target error to address the problem for unsupervised domain adaptation. Recent studies reveal that a deep neural network can learn transferable features which generalize well to novel tasks. Furthermore, a theory proposed by Ben-David et al. (2010) provides a upper bound for target error when transferring the knowledge, which can be summarized as minimizing the source error and distance between marginal distributions simultaneously. However, common methods based on the theory usually ignore the joint error such that samples from different classes might be mixed together when matching marginal distribution. And in such case, no matter how we minimize the marginal discrepancy, the target error is not bounded due to an increasing joint error. To address this problem, we propose a general upper bound taking joint error into account, such that the undesirable case can be properly penalized. In addition, we utilize constrained hypothesis space to further formalize a tighter bound as well as a novel cross margin discrepancy to measure the dissimilarity between hypotheses which alleviates instability during adversarial learning. Extensive empirical evidence shows that our proposal outperforms related approaches in image classification error rates on standard domain adaptation benchmarks.
BibTeX
@misc{zhang2019general,
  author = {Dexuan Zhang and Tatsuya Harada},
  title = {{A General Upper Bound for Unsupervised Domain Adaptation}},
  year = {2019},
  eprint = {1910.01409},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1910.01409},
}
Figure