A New PAC-Bayesian Perspective on Domain Adaptation

1. Introduction

• Domain adaptation transfers a model from a fixed but unknown source distribution to a related, slightly different target distribution.The introduction notes applications including computer vision, bioinformatics, and natural language processing.Source: §1 · p. 1
• Earlier domain-adaptation bounds jointly used source risk, marginal-distribution divergence, and a non-estimable term related to adaptation difficulty.The cited earlier PAC-Bayesian approach also used a non-estimable term that requires labels from both domains to estimate.Source: §1 · p. 1
• The new bound combines target voter disagreement, source voter accuracy weighted by domain divergence, and a term for target regions outside the source’s informative support.The paper derives PAC-Bayesian guarantees, specializes the approach to linear classifiers, and introduces DALC.Source: §1 · p. 2
• The paper reports that DALC improves performance over the previous PAC-Bayesian domain-adaptation algorithm.The algorithm follows from the paper’s bound and its PAC-Bayesian generalization guarantees.Source: §1 · p. 2

2. Unsupervised Domain Adaptation Setting

• The setting uses binary labels and a labeled source sample alongside an unlabeled target sample.The source and target are distributions over the input-output space, with associated input marginals.Source: §2 · p. 2
• The learner chooses a posterior distribution over voters using the source-target samples to form a weighted majority vote with target-domain generalization guarantees.The prior represents beliefs about voter accuracy before observing the samples.Source: §2 · p. 2
• Because the usual PAC-Bayesian route bounds majority-vote risk by twice the Gibbs risk, it can yield poor guarantees; expected voter disagreement offers a tighter-bound strategy.The paper specializes its PAC-Bayesian bound to linear classifiers as another strategy for tighter majority-vote bounds.Source: §2 · p. 2

3. Some Previous Domain Adaptation Bounds

• Reviewed bounds combine source risk, marginal-distribution distance, and a non-estimable term that quantifies task difficulty.Ben-David et al. (2006; 2010) formulate the shared-hypothesis error as a sum of source and target risks.Source: §3 · p. 3
• The H∆H-distance measures similarity between source and target marginals, supporting a strategy of finding hypotheses that behave similarly on both domains and fit source labels.The best joint hypothesis’s error is not estimable without target labels and is assumed low when adaptation is achievable.Source: §3 · p. 3
• Mansour et al. (2009) extend the H∆H-distance idea to real-valued loss functions, but their bound’s accuracy also depends on a non-estimable term assumed low.That term depends on the best target hypothesis’s risk and its agreement with the best source hypothesis on source data.Source: §3 · p. 3
• Germain et al. (2013) use domain disagreement in a PAC-Bayesian bound, but PBDA omits λ(ρ) from optimization and assumes it is negligible for all posteriors.That assumption cannot be verified because the best target posterior is unknown.Source: §3 · p. 3

• Target voter disagreement is computable from unlabeled target inputs, whereas expected joint error is computed on labeled source data.Source: §4 · p. 3

The domain adaptation bound

• When S = T, the bound is reached and reduces to the source-domain disagreement-plus-joint-error identity for Gibbs risk.Source: §4 · p. 4

Meaningful quantities

• The target-risk bound combines target disagreement, divergence-weighted source joint error, and worst-case risk on target regions outside the source support.The uninformative-region term is assumed small in this work.Source: §4 · pp. 3–4

Domains’ divergence

• βq(T ∥S) weights source joint error and varies with q; q=2 relates it to χ2-distance, and it is linked to Rényi divergence.Source: §4 · p. 4
• The term ηT \S represents worst feasible target error where the source has no support, an area the authors assume is small.Estimating joint error in that region would require extra assumptions.Source: §4 · p. 4

5.1. On the previous PAC-Bayesian bound

• Unlike the posterior-dependent additive λ(ρ) term in the earlier bound, βq(T ∥S) multiplicatively weights source error and is constant across posteriors, allowing a tunable trade-off.Source: §5.1 · p. 4

5.2. On some domain adaptation assumptions

• Under covariate shift, βq(TX∥SX) and ηT \S may be estimated by unsupervised density estimation; shared support makes ηT \S = 0.Source: §5.2 · p. 5
• With shared support, β∞ corresponds to the inverse point-wise weight ratio; for cluster-assumption settings, target disagreement behaves favorably for linear classifiers.Source: §5.2 · p. 5

5.3. On representation learning

• The algorithm assumes target support is mostly contained in source support; representation learning could reduce uncovered target regions while preserving the disagreement–source-error compromise.Source: §5.3 · p. 5

• Theorem 4 extends a PAC-Bayesian theorem to arbitrary bounded losses, enabling guarantees for the disagreement and source joint error used in the adaptation bound.Source: §6 · p. 5
• Corollary 5 provides PAC-Bayesian guarantees for the two quantities, with parameters b and c controlling the trade-off between empirical estimates and KL(ρ∥π).Source: §6 · p. 5
• The proof bounds disagreement and joint error via paired voters and their respective loss functions, then combines the guarantees under Theorem 3.Source: §6 · p. 6
• For algorithmic simplicity, Theorem 6 uses q→∞ and bounds target risk from empirical target disagreement and source joint error estimates.Source: §6 · p. 6
• The resulting optimization is smoother, permits unequal source and target sample sizes, and can neglect ηT \S because it is constant in ρ.The authors consider ηT \S small when source and target supports are similar.Source: §6 · p. 6

Linear-classifier losses

• The expected disagreement and joint error are expressed through linear-classifier loss functions, with Φdis(x) defined as 2×Φ(x)×Φ(−x).Figure 1 depicts the specialized loss functions.Source: §7 · pp. 6–7, Figure 1 · p. 7

Linear classifiers

• The specialization parameterizes a posterior over linear voters so its majority-vote risk matches the linear classifier's risk, while promoting large margins.The posterior is a spherical Gaussian centered on w, with identity covariance; the prior is centered on zero.Source: §7 · p. 6

Domain adaptation bound

• The target risk is bounded by target disagreement, source joint error weighted by β∞(T∥S), and a residual term η_T\S.The generalization-bound corollary gives a high-probability version with coefficients c′ and b′.Source: §7 · p. 7
• Some source errors may be allowed when they improve target separation, since the bound trades source Φerr joint error against target Φdis disagreement.Under the cluster assumption, target disagreement is low when the decision boundary crosses a low-density region between homogeneous labeled clusters.Source: §7 · p. 7

Learning algorithm

• DALC minimizes the specialized bound's objective by gradient descent, and the kernel trick extends it to RKHS classifiers.The objective is highly non-convex; the described experiments initialize gradient descent with a uniform weight vector.Source: §7 · p. 7

Amazon Reviews

• DALC was best six times and second four times across the 12 Amazon tasks, except for the two electronics–DVD tasks; a Wilcoxon test gave an 89.5% probability it beats PBDA.The reported comparison is based on error rates on separate target test sets.Source: Table 1 · p. 8, §8 · p. 8

Toy example

• On an intertwining-moons toy problem with an unlabeled target rotated by 50°, DALC adapts successfully while misclassifying some source examples, trading source-sample errors for lower disagreement on the target sample.Source: §8 · pp. 7–8

Amazon Reviews

• The Amazon benchmark comprises twelve directed product-domain tasks using binary review labels, about 40,000 filtered features, tf-idf weighting, and 2,000 labeled source plus 2,000 unlabeled target examples.DALC is compared with source-trained SVM, DASVM, CODA, and PBDA; target-test error rates are reported.Source: §8 · p. 8

• The new algorithm outperforms the previous PAC-Bayesian approach.Source: §9 · p. 8
• The target-risk bound trades off target voter disagreement, source joint errors, and worst-case error in regions where the source is non-informative.Domain divergence βq(T ∥S) weights the importance of source information rather than appearing as an additive term.Source: §9 · p. 8
• The analysis combined with a PAC-Bayesian generalization bound yields a domain-adaptation algorithm for linear classifiers.Source: §9 · p. 8
• Future work includes estimating βq(T ∥S) under covariate shift or with target labels, and using representation learning or active learning to address ηT \S.Source: §9 · p. 8

A. Proof of Theorem 4

• Theorem 4’s proof applies Jensen’s inequality and a change-of-measure inequality, then Markov’s inequality and further cited inequalities before reorganizing terms into a high-probability bound.Source: A. Proof of Theorem 4 · p. 11

B. Using DALC with a kernel function

• The kernel trick represents DALC using a dual weight vector in an augmented space and rewrites its objective with the kernel matrix.Source: B. Using DALC with a kernel function · p. 11
• The experiments minimize the objective with the Broyden-Fletcher-Goldfarb-Shanno method (BFGS) implemented in scipy.Source: B. Using DALC with a kernel function · p. 11

• DALCRCV reverse validation searches a 20 × 20 logarithmic grid with C from 0.01 to 10^6 and B from 1.0 to 10^8; other algorithms’ results come from Germain et al. (2013).Source: C. Experimental Protocol · p. 11