Efficient and Provable Algorithms for Covariate Shift

Deeksha Adil, Jaroslaw Blasiok

TL;DR

This paper provides the first formal end-to-end sample complexity and computational guarantees for estimating test expectations under covariate shift with arbitrary bounded target functions. By establishing that learning distributions up to total variation (TV) distance or estimating density ratios via (kernel) logistic regression is theoretically sufficient, the authors disprove the common belief that separate density estimation is fundamentally ineffective for covariate shift adaptation.

What Problem Does This Paper Address?

In supervised learning, a standard assumption is that training and test samples come from the same distribution. Under covariate shift, the conditional label distribution remains identical ($p_{\text{tr}}(y|x) = p_{\text{te}}(y|x)$), but the marginal feature distributions diverge ($p_{\text{tr}}(x) \neq p_{\text{te}}(x)$).

Practitioners often reweight samples using the density ratio (or importance weight) $w(x) = p_{\text{te}}(x)/p_{\text{tr}}(x)$. However, theoretical guarantees for these methods have remained sparse:

  1. Prior guarantees typically rely on restrictive assumptions on the target function $f$ (such as assuming $f$ belongs to a known Reproducing Kernel Hilbert Space, as in Kernel Mean Matching / KMM).
  2. Existing literature frequently asserts that separately estimating $p_{\text{tr}}$ and $p_{\text{te}}$ is not only computationally inefficient in high dimensions, but fundamentally doomed because tiny errors in the denominator $p_{\text{tr}}(x)$ blow up the density ratio.
  3. Common heuristics like logistic regression for density ratio estimation lack rigorous end-to-end sample complexity analysis.

The authors formulate the core challenge as covariate-shifted mean estimation: given labeled training points $(x_i, f(x_i))$ with $x_i \sim p_{\text{tr}}$ and unlabeled test points $\tilde{x}_i \sim p_{\text{te}}$, compute an estimate $Z$ such that $|Z - \mathbb{E}_{x \sim p_{\text{te}}}[f(x)]| \le \epsilon$ for any unknown bounded function $f: \mathbb{R}^d \to [-1, 1]$.

Methods

The paper develops theoretical analysis and algorithms across several distribution regimes:

  • Direct Gaussian Learning (Algorithms 1 & 2): For general or isotropic multivariate Gaussians, empirical means and covariance matrices are estimated directly. The algorithm forms plug-in Gaussian densities $\hat{p}_{\text{te}}$ and $\hat{p}_{\text{tr}}$, computes sample reweighting estimates using $\frac{\hat{p}_{\text{te}}(y_i)}{\hat{p}_{\text{tr}}(y_i)} f(y_i)$, and applies the median-of-means trick.
  • Truncated Importance Weighting via TV Learnability (Algorithm 3): To handle general learnable distribution classes, the algorithm estimates densities $\hat{p}_{\text{tr}}$ and $\hat{p}_{\text{te}}$, but truncates the estimated ratio $\hat{r}(x) = \hat{p}_{\text{te}}(x)/\hat{p}_{\text{tr}}(x)$ at a threshold $B$ (setting it to $0$ if $\hat{r}(x) > B$).
  • Logistic Regression for Exponential Families: Reduces density ratio estimation to binary classification between training and test sets. Minimizing the empirical cross-entropy loss recovers parameter estimates without ever evaluating the underlying normalizer or density.
  • Kernel Logistic Regression: Extends the classification reduction to non-parametric settings where the log-density ratio $\ln(p_{\text{tr}}(x)/p_{\text{te}}(x))$ lives in an arbitrary RKHS $\mathcal{H}$.

Datasets

Not discussed in the paper. The work is purely theoretical and does not conduct experiments on synthetic or empirical benchmark datasets.

Key Insights and Ideas

  • Challenging the "Separate Estimation" Folk Wisdom: Conventional wisdom holds that estimating $p_{\text{te}}$ and $p_{\text{tr}}$ separately cannot yield a good density ratio estimator. The authors demonstrate that whenever the true ratio's tail is bounded ($\Pr_{x \sim p_{\text{te}}}(p_{\text{te}}(x)/p_{\text{tr}}(x) > B/4) \le \epsilon$), achieving TV errors $d_{\text{TV}}(p_{\text{te}}, \hat{p}_{\text{te}}) \le \epsilon$ and $d_{\text{TV}}(p_{\text{tr}}, \hat{p}_{\text{tr}}) \le \epsilon/B$, paired with simple threshold truncation, is mathematically sufficient for mean estimation.
  • Standard KMM vs. Naive Plug-in: The authors observe that standard KMM analysis requires $n_{\text{tr}} \gtrsim (MB/\epsilon)^2$ and $n_{\text{te}} \gtrsim (M/\epsilon)^2$. They show a naive plug-in method (learning $\hat{f}$ via $L_1$ kernel regression directly on training data and evaluating on test samples) achieves the exact same asymptotic complexity, showing that existing KMM theory fails to explain why KMM performs better in practice.
  • Surrogate Regret Bounds Imply TV Bounds: For classification-based density estimation, the excess cross-entropy loss (regret) directly upper-bounds the sum of KL divergences $D_{\text{KL}}(p_{\text{te}} \parallel \hat{p}_{\text{te}}) + D_{\text{KL}}(p_{\text{tr}} \parallel \hat{p}_{\text{tr}})$. Via Pinsker's inequality, low regret automatically translates to the TV-distance bounds required for truncated importance estimation.

Key Results

  • Multivariate Gaussians:
  • For general Gaussians with close means ($\|\mu_{\text{tr}} - \mu_{\text{te}}\|_2 \le O(1)$) and covariances, Algorithm 1 requires $\widetilde{O}(d^2/\epsilon^2)$ samples to estimate $\mathbb{E}_{p_{\text{te}}}[f]$ within $\epsilon$.
  • For isotropic Gaussians ($I$), Algorithm 2 achieves an optimal $\widetilde{O}(d/\epsilon^2)$ sample complexity.
  • General TV-Learnable Distributions:
  • If $\Pr_{x \sim p_{\text{te}}}(p_{\text{te}}(x)/p_{\text{tr}}(x) > B/4) \le \epsilon$, then with TV estimates accurate to $\epsilon$ and $\epsilon/B$, Algorithm 3 estimates the mean within $O(\epsilon)$ using $O(B^2/\epsilon^2)$ labeled training samples.
  • Lower Bound: The authors show an information-theoretic lower bound of $\Omega(B/\epsilon)$ samples even when $p_{\text{tr}}$ and $p_{\text{te}}$ are known exactly.
  • Exponential Families via Logistic Regression:
  • When densities belong to the same $D$-dimensional exponential family, an $\epsilon$-accurate mean estimate can be computed using at most $O(B_1 B_2^2 B_3^4 \epsilon^{-8})$ samples (where $B_1 = \text{Tr}(\Sigma_{\text{tr}} + \Sigma_{\text{te}})$, $B_2$ bounds parameter separation, and $B_3 \ge R_2(p_{\text{tr}} \parallel p_{\text{te}})$).
  • RKHS via Kernel Logistic Regression:
  • When $\ln(p_{\text{tr}}/p_{\text{te}}) \in \mathcal{H}$ with kernel bound $D$ and norm bound $B_1$, the required sample complexity is $O(D B_1^2 B_2^4 / \epsilon^8)$.

Limitations and Future Work

  • Suboptimal $\epsilon$ Dependence in General Reductions: In both exponential family and RKHS settings, routing through TV distance bounds and Rademacher generalization incurs high polynomial sample dependencies on accuracy ($O(\epsilon^{-8})$ vs. the parametric $O(\epsilon^{-2})$ achieved in the specialized Gaussian analysis).
  • Distribution Overlap Requirement: The results inherently rely on bounded tails or bounded Rényi-2 divergence ($R_2(p_{\text{tr}} \parallel p_{\text{te}}) \le B_3$). In settings with near-disjoint supports or heavy non-overlapping tails, these sample bounds degrade rapidly.
  • Empirical Validation: The proposed algorithms and truncation bounds were not evaluated empirically against existing heuristics (such as unconstrained Kernel Logistic Regression or standard KMM implementations) on real-world covariate shift benchmarks.

Summary updated

Abstract

Covariate shift, a widely used assumption in tackling _distributional shift_ (when training and test distributions differ), focuses on scenarios where the distribution of the labels conditioned on the feature vector is the same, but the distribution of features in the training and test data are different. Despite the significance and extensive work on covariate shift, theoretical guarantees for algorithms in this domain remain sparse. In this paper, we distill the essence of the covariate shift problem and focus on estimating the average $E_{\widetilde{x}\sim p_{\mathrm{test}}}f(\widetilde{x})$, of any unknown and bounded function $f$, given labeled training samples $(x_i, f(x_i))$, and unlabeled test samples $\widetilde{x}_i$; this is a core subroutine for several widely studied learning problems. We give several efficient algorithms, with provable sample complexity and computational guarantees.
BibTeX
@inproceedings{adil2026efficient,
  author = {Deeksha Adil and Jaroslaw Blasiok},
  title = {{Efficient and Provable Algorithms for Covariate Shift}},
  booktitle = {ALT},
  year = {2026},
  url = {https://openreview.net/forum?id=j7czrz0hy0},
}

Loading related content...

Figure