Positive Distribution Shift as a Framework for Understanding Tractable Learning

We study a setting where the goal is to learn a target function f(x) with respect to a target distribution D(x), but training is done on i.i.d. samples from a different training distribution D’(x), labeled by the true target f(x). Such a distribution shift (here in the form of covariate shift) is usually viewed negatively, as hurting or making learning harder, and the traditional distribution shift literature is mostly concerned with limiting or avoiding this negative effect. In contrast, we argue that with a well-chosen D'(x), the shift can be positive and make learning easier -- a perspective called Positive Distribution Shift (PDS). Such a perspective is central to contemporary machine learning, where much of the innovation is in finding good training distributions D’(x), rather than changing the training algorithm. We further argue that the benefit is often computational rather than statistical, and that PDS allows computationally hard problems to become tractable even using standard gradient-based training. We formalize different variants of PDS, show how certain hard classes are easily learnable under PDS, and make connections with membership query learning.

Machine learning systems learn from examples, much like students learn from practice problems. Usually, researchers worry when the examples used for training differ from the situations where the system will later be used. This paper asks whether that difference can sometimes be helpful instead of harmful. We show that carefully choosing the training examples can make a difficult learning task much easier, even when the final goal stays the same. The advantage is not only that the system may need fewer examples; in many cases, the right examples can make a problem much easier to solve at all. The paper develops a framework for understanding this “helpful shift” in training data and relates it to older ideas about learning from carefully chosen examples.