  We consider the Domain Adaptation problem, also known as the covariate shift
problem, where the distributions that generate the training and test data
differ while retaining the same labeling function. This problem occurs across a
large range of practical applications, and is related to the more general
challenge of transfer learning. Most recent work on the topic focuses on
optimization techniques that are specific to an algorithm or practical use case
rather than a more general approach. The sparse literature attempting to
provide general bounds seems to suggest that efficient learning even under
strong assumptions is not possible for covariate shift. Our main contribution
is to recontextualize these results by showing that any Probably Approximately
Correct (PAC) learnable concept class is still PAC learnable under covariate
shift conditions with only a polynomial increase in the number of training
samples. This approach essentially demonstrates that the Domain Adaptation
learning problem is as hard as the underlying PAC learning problem, provided
some conditions over the training and test distributions. We also present
bounds for the rejection sampling algorithm, justifying it as a solution to the
Domain Adaptation problem in certain scenarios.
