  Supervised learning is often affected by a covariate shift in which the
marginal distributions of instances (covariates $x$) of training and testing
samples $\mathrm{p}_\text{tr}(x)$ and $\mathrm{p}_\text{te}(x)$ are different
but the label conditionals coincide. Existing approaches address such covariate
shift by either using the ratio
$\mathrm{p}_\text{te}(x)/\mathrm{p}_\text{tr}(x)$ to weight training samples
(reweighted methods) or using the ratio
$\mathrm{p}_\text{tr}(x)/\mathrm{p}_\text{te}(x)$ to weight testing samples
(robust methods). However, the performance of such approaches can be poor under
support mismatch or when the above ratios take large values. We propose a
minimax risk classification (MRC) approach for covariate shift adaptation that
avoids such limitations by weighting both training and testing samples. In
addition, we develop effective techniques that obtain both sets of weights and
generalize the conventional kernel mean matching method. We provide novel
generalization bounds for our method that show a significant increase in the
effective sample size compared with reweighted methods. The proposed method
also achieves enhanced classification performance in both synthetic and
empirical experiments.
