  In unsupervised domain adaptation, existing theory focuses on situations
where the source and target domains are close. In practice, conditional entropy
minimization and pseudo-labeling work even when the domain shifts are much
larger than those analyzed by existing theory. We identify and analyze one
particular setting where the domain shift can be large, but these algorithms
provably work: certain spurious features correlate with the label in the source
domain but are independent of the label in the target. Our analysis considers
linear classification where the spurious features are Gaussian and the
non-spurious features are a mixture of log-concave distributions. For this
setting, we prove that entropy minimization on unlabeled target data will avoid
using the spurious feature if initialized with a decently accurate source
classifier, even though the objective is non-convex and contains multiple bad
local minima using the spurious features. We verify our theory for spurious
domain shift tasks on semi-synthetic Celeb-A and MNIST datasets. Our results
suggest that practitioners collect and self-train on large, diverse datasets to
reduce biases in classifiers even if labeling is impractical.
