  Many machine learning models appear to deploy effortlessly under distribution
shift, and perform well on a target distribution that is considerably different
from the training distribution. Yet, learning theory of distribution shift
bounds performance on the target distribution as a function of the discrepancy
between the source and target, rarely guaranteeing high target accuracy.
Motivated by this gap, this work takes a closer look at the theory of
distribution shift for a classifier from a source to a target distribution.
Instead of relying on the discrepancy, we adopt an Invariant-Risk-Minimization
(IRM)-like assumption connecting the distributions, and characterize conditions
under which data from a source distribution is sufficient for accurate
classification of the target. When these conditions are not met, we show when
only unlabeled data from the target is sufficient, and when labeled target data
is needed. In all cases, we provide rigorous theoretical guarantees in the
large sample regime.
