  One of the central problems in machine learning is domain adaptation. Unlike
past theoretical work, we consider a new model for subpopulation shift in the
input or representation space. In this work, we propose a provably effective
framework for domain adaptation based on label propagation. In our analysis, we
use a simple but realistic ``expansion'' assumption, proposed in
\citet{wei2021theoretical}. Using a teacher classifier trained on the source
domain, our algorithm not only propagates to the target domain but also
improves upon the teacher. By leveraging existing generalization bounds, we
also obtain end-to-end finite-sample guarantees on the entire algorithm. In
addition, we extend our theoretical framework to a more general setting of
source-to-target transfer based on a third unlabeled dataset, which can be
easily applied in various learning scenarios.
