Efficient and Provable Algorithms for Covariate Shift

Deeksha Adil, Jaroslaw Blasiok

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 $\mathbb{E}_{\tilde{\mathbf{x}}\sim p_{\mathrm{test}}}\mathbf{f}(\tilde{\mathbf{x}})$, of any unknown and bounded function $\mathbf{f}$, given labeled training samples $(\mathbf{x}_i, \mathbf{f}(\mathbf{x}_i))$, and unlabeled test samples $\tilde{\mathbf{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. Moreover, we provide the first rigorous analysis of algorithms in this space when $\mathbf{f}$ is unrestricted, laying the groundwork for developing a solid theoretical foundation for covariate shift problems.

Introduction

In standard machine learning paradigms, we typically assume that training and test data are drawn from the same underlying distribution. However, real-world deployments frequently encounter "distributional shift," where this assumption fails. One of the most common forms of this phenomenon is covariate shift. Under covariate shift, the conditional distribution of labels given features $p(y|x)$ remains invariant, but the marginal distribution of the features themselves changes between training ($p_{tr}$) and testing ($p_{te}$).

This paper addresses a fundamental building block of the covariate shift problem: covariate-shifted mean estimation. The goal is to estimate the expected value of an unknown, bounded function $f$ on the test distribution, using only labeled samples from the training distribution and unlabeled samples from the test distribution. While specific methods like Kernel Mean Matching (KMM) have been proposed, they often rely on restrictive assumptions about the function class of $f$. This work seeks to establish provable guarantees for any bounded function $f$ and determine the fundamental sample complexity limits of the problem.

Algorithmic Frameworks

The researchers propose several algorithms tailored to different levels of knowledge regarding the underlying distributions:

1. Parametric Estimation (Gaussians)

For scenarios where distributions are multivariate Gaussians, the authors demonstrate that a "plug-in" approach is highly effective. By estimating the means and covariances of both distributions and using the ratio of these estimated densities as importance weights, the mean can be estimated with high precision. For $d$-dimensional Gaussians, this requires $O(d^2/\epsilon^2)$ samples, which improves to $O(d/\epsilon^2)$ if the Gaussians are isotropic.

2. The TV-Learning Plug-in

Perhaps the most significant theoretical contribution is the analysis of the Total Variation (TV) distance plug-in. Conventional wisdom in the field suggests that separately estimating $p_{tr}$ and $p_{te}$ to compute their ratio is inherently unstable, as small errors in the denominator (the training density) can lead to massive errors in the final estimate.

This paper challenges that myth. The authors prove that if a class of distributions is learnable in TV distance (e.g., mixtures of Gaussians or log-concave distributions), then the covariate shift problem is also solvable. By applying a threshold to the density ratio to handle "heavy tails," they show that separate estimation is a valid, provable strategy with polynomial sample complexity.

3. Logistic Regression and RKHS

The paper provides the first end-to-end theoretical analysis for using logistic regression to estimate importance weights ($p_{te}/p_{tr}$). This method is common in practice but lacked rigorous bounds. The authors extend this to Reproducing Kernel Hilbert Spaces (RKHS), allowing for non-parametric density ratios that can model complex shifts.

Key Insights and Theoretical Results

  • Bridging Distribution Learning and Covariate Shift: The work establishes a formal link between these two fields. If you can learn the distributions, you can solve the shift. This opens the door for using a wide array of existing distribution-learning algorithms to solve covariate shift problems.
  • Sample Complexity Bounds: The paper provides concrete bounds for various scenarios:
  • Bounded Ratios: If the density ratio $p_{te}/p_{tr}$ is bounded by $B$, the problem is solvable with $O(B^2/\epsilon^2)$ samples.
  • RKHS Settings: For complex, non-parametric families, the problem is solvable with polynomial sample complexity, specifically $O(\epsilon^{-8})$ in the most general RKHS setting.

Limitations and Future Directions

While this work provides a rigorous foundation, several challenges remain:

  • The Complexity Gap: The $O(\epsilon^{-8})$ bound for RKHS is theoretically polynomial but practically high. Future work is needed to tighten these bounds, as the $O(\epsilon^{-2})$ complexity seen in Gaussian cases suggests that more efficient general bounds may exist.
  • The Bounded Ratio Constraint: The current proofs rely on the density ratio not being excessively large. If the test distribution covers regions where the training distribution has zero or near-zero probability, the problem becomes fundamentally ill-posed without additional structural assumptions.
  • Scaling to ERM: This paper focuses on mean estimation. The next logical step is extending these provable guarantees to Empirical Risk Minimization (ERM), where the goal is to minimize a loss function under shift rather than just estimating a single expectation.

Conclusion

By providing the first efficient and provably correct algorithms for covariate-shifted mean estimation without restricting the function class of $f$, this paper moves the field beyond heuristic-based approaches. It demonstrates that density ratio estimation via separate distribution learning is not only viable but theoretically sound, laying the groundwork for more robust machine learning in non-stationary environments.

Summary updated

Abstract

Covariate shift, a widely used assumption in tackling {\it 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 $\mathbb{E}_{\tilde{\mathbf{x}}\sim p_{\mathrm{test}}}\mathbf{f}(\tilde{\mathbf{x}})$, of any unknown and bounded function $\mathbf{f}$, given labeled training samples $(\mathbf{x}_i, \mathbf{f}(\mathbf{x}_i))$, and unlabeled test samples $\tilde{\mathbf{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. Moreover, we provide the first rigorous analysis of algorithms in this space when $\mathbf{f}$ is unrestricted, laying the groundwork for developing a solid theoretical foundation for covariate shift problems.
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},
}
Figure