Distribution shift separates training performance from deployment performance. The central problem is to compare risks under two laws, usually called source and target.
Source and target risks
The same predictor can have different risks under different feature-response laws.
Definition. Let \(P\) be the source law and \(Q\) the target law. The source and target risks are \[ R_P(f)=P\ell_f,\qquad R_Q(f)=Q\ell_f. \] Domain adaptation asks for small \(R_Q(f)\) using mostly or only data from \(P\), plus structural information linking \(P\) and \(Q\).
Remark. Without assumptions connecting \(P\) and \(Q\), source data alone cannot guarantee target performance.
Covariate shift
Under covariate shift, the conditional law of labels is stable and only the feature distribution changes.
Definition. Covariate shift assumes \(P(Y\mid X)=Q(Y\mid X)\) but \(P_X\ne Q_X\). If \(Q_X\ll P_X\), let \(w(x)=\mathrm{d}Q_X/\mathrm{d}P_X\).
Proposition. Under covariate shift, \[ R_Q(f)=\mathbb E_P\left[w(X)\ell(f(X),Y)\right]. \]
Proof. Disintegrate both laws into conditional label laws and feature marginals. The conditional parts agree, while \(Q_X(\mathrm{d}x)=w(x)P_X(\mathrm{d}x)\). Substituting into the target risk gives the weighted source expectation.
Divergence-based comparison
Target risk can be bounded by source risk plus a discrepancy between distributions.
Proposition. For bounded losses \(0\le\ell_f\le M\), \[ |R_Q(f)-R_P(f)|\le M\|Q-P\|_{\mathrm{TV}}. \]
Proof. The signed measure \(Q-P\) applied to \(\ell_f\) has absolute value at most \(\|\ell_f\|_\infty\|Q-P\|_{\mathrm{TV}}\), with the convention that total variation is the supremum over bounded functions by norm \(1\).
Representation and invariant prediction
A representation can make domains closer, but invariance must preserve predictive information.
Remark. If a map \(\Phi(X)\) removes all domain information but also removes label information, adaptation fails. Useful invariant representations balance small domain discrepancy with small conditional or approximation error in the representation.
A taxonomy of shifts
Definition.
- Covariate shift: \(P(Y\mid X)=Q(Y\mid X)\), while \(P_X\ne Q_X\).
- Label shift: \(P(X\mid Y)=Q(X\mid Y)\), while \(P_Y\ne Q_Y\).
- Concept shift: \(P(Y\mid X)\ne Q(Y\mid X)\).
- Selection bias: observed data are conditioned on a selection indicator whose law depends on \(X\), \(Y\), or both.
These assumptions are not interchangeable. Covariate weighting is generally invalid under concept shift, and label-prior correction is invalid when class-conditional feature laws change.
Importance-weight variance and overlap
Proposition. Under covariate shift, for a fixed \(f\), \[ \widehat R_w(f)=\frac1n\sum_{i=1}^nw(X_i)\ell_f(X_i,Y_i) \] is unbiased for \(R_Q(f)\), and \[ \operatorname{Var}_P\{\widehat R_w(f)\} =\frac1n\operatorname{Var}_P\{w(X)\ell_f(X,Y)\}. \] If \(0\le\ell\le M\), then \[ \operatorname{Var}_P\{\widehat R_w(f)\} \le\frac{M^2}{n}\{1+\chi^2(Q_X\|P_X)\}. \]
Proof. Unbiasedness is the change-of-measure identity. Independence gives the variance formula. Finally, \(\mathbb E_Pw^2=1+\chi^2(Q_X\|P_X)\), and \(\operatorname{Var}(w\ell)\le\mathbb E(w\ell)^2\le M^2\mathbb Ew^2\).
Remark. Absolute continuity is not enough for stable adaptation. The second moment of the density ratio controls effective sample size; poor overlap can make unbiased weighting statistically useless.
Self-normalized and clipped weights
Definition. Self-normalized risk and clipped weighting are \[ \widehat R_{\mathrm{SN}}(f)= \frac{\sum_iw_i\ell_i}{\sum_iw_i}, \qquad \widehat R_\tau(f)=\frac1n\sum_i(w_i\wedge\tau)\ell_i. \]
Self-normalization introduces \(O(n^{-1})\) ratio bias but is invariant to an unknown multiplicative normalization of \(w\). Clipping bounds variance at the price of bias \[ 0\le R_Q(f)-\mathbb E\widehat R_\tau(f) \le M\,\mathbb E_P(w-\tau)_+. \] The threshold should therefore be chosen by an explicit bias-variance criterion rather than by the fiction that clipped weights remain unbiased.
Label-shift identification
Theorem. Let \(Y\in\{1,\ldots,K\}\), and let \(g(X)\in\{1,\ldots,K\}\) be a fixed classifier. Under label shift define the source confusion matrix \[ C_{jk}=P\{g(X)=j\mid Y=k\}. \] If \(C\) is invertible, then target label proportions \(q_k=Q(Y=k)\) are identified from target predicted-label frequencies \(\mu_j=Q\{g(X)=j\}\) by \[ q=C^{-1}\mu. \]
Proof. Label shift makes the conditional distribution of \(g(X)\) given \(Y=k\) the same in both domains. Hence \[ \mu_j=\sum_kQ\{g(X)=j\mid Y=k\}q_k =\sum_kC_{jk}q_k. \] Invertibility gives the solution. Near-singularity makes estimation unstable even though population identification holds.
The \(\mathcal H\Delta\mathcal H\) adaptation bound
Definition. For a binary hypothesis class \(\mathcal H\), define \[ d_{\mathcal H\Delta\mathcal H}(P_X,Q_X) =2\sup_{h,h'\in\mathcal H} |P_X(h\ne h')-Q_X(h\ne h')|. \]
Theorem. For every \(h\in\mathcal H\), \[ R_Q(h)\le R_P(h)+ \frac12d_{\mathcal H\Delta\mathcal H}(P_X,Q_X)+\lambda_{\mathcal H}, \] where \[ \lambda_{\mathcal H}=\inf_{h^*\in\mathcal H} \{R_P(h^*)+R_Q(h^*)\}. \]
Proof. For any \(h^*\in\mathcal H\), \[ R_Q(h)\le R_Q(h^*)+Q_X(h\ne h^*). \] By the discrepancy definition, \(Q_X(h\ne h^*)\le P_X(h\ne h^*)+\tfrac12d_{\mathcal H\Delta\mathcal H}\). Moreover \(P_X(h\ne h^*)\le R_P(h)+R_P(h^*)\), since disagreement implies at least one classifier errs. Combine and minimize over \(h^*\).
The term \(\lambda_{\mathcal H}\) is unavoidable: matching feature marginals cannot help when no classifier performs well in both domains.
Distributionally robust risk
Definition. Given a nominal empirical law \(\widehat P_n\) and discrepancy \(D\), distributionally robust learning solves \[ \inf_f\sup_{Q:D(Q,\widehat P_n)\le\rho}Q\ell_f. \]
Proposition. For a KL ball and bounded loss, convex duality gives \[ \sup_{Q:\operatorname{KL}(Q\|\widehat P_n)\le\rho}Q\ell = \inf_{\eta>0} \left\{\eta\rho+ \eta\log\widehat P_ne^{\ell/\eta}\right\}. \]
Proof. Introduce multiplier \(\eta\ge0\) for the KL constraint. The inner supremum of \(Q\ell-\eta\operatorname{KL}(Q\|\widehat P_n)\) is \(\eta\log\widehat P_ne^{\ell/\eta}\) by the Gibbs variational principle. Strong duality holds under the usual interior condition.
Impossibility without transport assumptions
Theorem. Suppose only labeled source data and unlabeled target features are observed. Without a restriction linking \(P(Y\mid X)\) and \(Q(Y\mid X)\), no learner can uniformly guarantee target classification error below \(1/2\).
Proof. Construct two target laws with the same feature marginal and the same source law, but with opposite deterministic target labels. All observed data have identical distributions under the two worlds. Any classifier's target errors in the two worlds sum to one, so its worst-case error is at least \(1/2\).
This indistinguishability argument is the right baseline for every adaptation theorem: each positive result must state the exact assumption that excludes the two-world construction.