Abstract
We develop and analyze a principled approach to kernel ridge regression (KRR) under covariate shift. The goal is to learn a regression function with small mean squared error over a target distribution, based on unlabeled data from there and labeled data that may have a different feature distribution. We propose to split the labeled data into two subsets and conduct KRR on them separately to obtain a collection of candidate models and an imputation model. We use the latter to fill the missing labels and then select the best candidate model accordingly. Our non-asymptotic excess risk bounds show that in quite general scenarios, our estimator adapts to the structure of the target distribution as well as the covariate shift. It achieves the minimax optimal error rate up to a logarithmic factor. The use of pseudo-labels in model selection does not have major negative impacts.
Introduction
In many real-world machine learning applications, the distribution of features in the training data (source) often differs from the distribution encountered during deployment (target). This phenomenon, known as covariate shift, poses a significant challenge for model selection. Traditional cross-validation relies on labeled data from the target distribution to tune hyperparameters, but in practice, target labels are often expensive or unavailable. While unlabeled target data is frequently abundant, the question remains: how can we leverage this unlabeled data to select a near-optimal model trained on source data?
Methodology: Pseudo-Labeling for KRR
This paper introduces a four-step framework designed to address model selection under covariate shift using Pseudo-Labeling for Kernel Ridge Regression:
- Data Splitting: The labeled source dataset is divided into two independent subsets, $D_1$ and $D_2$.
- Training:
- A set of candidate models is trained on $D_1$ using a range of regularization parameters ($\lambda$).
- An imputation model is trained on $D_2$ using a very small penalty parameter to achieve an "undersmoothed" fit.
- Pseudo-Labeling: The imputation model generates labels for the unlabeled target features.
- Model Selection: Candidate models are evaluated against these pseudo-labels on the target distribution to select the final predictor.
A critical insight of this approach is the power of undersmoothing. The imputation model does not need to be perfectly accurate; it primarily needs to be low-bias. The authors demonstrate that the variance of pseudo-labels has a significantly weaker impact on final model selection than their bias. By using a small penalty (as seen in the "small" curve in Figure 1), the imputation model maintains the low bias necessary for effective selection.
Theoretical Contributions
The authors provide a rigorous theoretical foundation for this method, introducing the concept of Effective Sample Size ($n_{eff}$). This metric quantifies the value of source data relative to the target task, showing that $n$ source samples are roughly equivalent to $n_{eff}$ labeled target samples.
Furthermore, the proposed estimator is shown to be minimax optimal up to a logarithmic factor. It automatically adapts to the unknown covariate shift without requiring explicit knowledge of the target density or the likelihood ratio between distributions.
Empirical Results
Numerical simulations on synthetic datasets, including Sobolev spaces and various kernel classes, validate the theoretical findings. The pseudo-labeling (PL) approach consistently outperforms "naive" validation (tuning solely on source data).
As illustrated in Figure 3, the PL estimator achieves performance remarkably close to an "Oracle" model—a hypothetical scenario where true target labels are available for validation. This confirms that using synthetic labels for model selection is a robust and effective strategy when the imputation model is correctly undersmoothed.
Conclusion and Future Work
This work provides a principled framework for KRR under covariate shift, demonstrating that pseudo-labeling can bridge the gap between source and target distributions. While currently focused on least squares loss and well-specified models within Reproducing Kernel Hilbert Spaces (RKHS), future research may extend these principles to other loss functions (e.g., logistic regression) and explore connections to broader distribution distance metrics like Wasserstein distance.
Summary updated