We revisit the fundamental problem of learning with distribution shift, in
which a learner is given labeled samples from training distribution $D$,
unlabeled samples from test distribution $D'$ and is asked to output a
classifier with low test error. The standard approach in this setting is to
bound the loss of a classifier in terms of some notion of distance between $D$
and $D'$. These distances, however, seem difficult to compute and do not lead
to efficient algorithms.
We depart from this paradigm and define a new model called testable learning
with distribution shift, where we can obtain provably efficient algorithms for
certifying the performance of a classifier on a test distribution. In this
model, a learner outputs a classifier with low test error whenever samples from
$D$ and $D'$ pass an associated test; moreover, the test must accept if the
marginal of $D$ equals the marginal of $D'$. We give several positive results
for learning well-studied concept classes such as halfspaces, intersections of
halfspaces, and decision trees when the marginal of $D$ is Gaussian or uniform
on $\{\pm 1\}^d$. Prior to our work, no efficient algorithms for these basic
cases were known without strong assumptions on $D'$.
For halfspaces in the realizable case (where there exists a halfspace
consistent with both $D$ and $D'$), we combine a moment-matching approach with
ideas from active learning to simulate an efficient oracle for estimating
disagreement regions. To extend to the non-realizable setting, we apply recent
work from testable (agnostic) learning. More generally, we prove that any
function class with low-degree $L_2$-sandwiching polynomial approximators can
be learned in our model. We apply constructions from the pseudorandomness
literature to obtain the required approximators.

在学习分布转移的基本问题中，我们提出了一个新模型，称为可测试学习，可以通过一个相关的测试来得到分类器在测试分布上的性能证明，并证明了对于一些常见概念类别如半空间、半空间的交、决策树等，以及具有低次 $L_2$- 夹逼多项式逼近器的任何函数类别都可以在这个模型下学习。