We revisit the fundamental problem of domain adaptation, where 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 prove a generalization bound in terms of some notion of distance between D and D′. These distances, however, are 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 (TDS learning), where a learner is allowed to reject if it detects distribution shift relative to a fixed output classifier. Moreover, whenever samples from D and D′ pass an associated test, the output classifier is guaranteed to have low test error.  We will describe how this approach leads to the first set of efficient algorithms for a variety of basic concept classes and training distributions without taking any assumptions on the test distribution.    

Joint work with Konstantinos Stravopoulos and Arsen Vasilyan