Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
For theorists studying learning under distribution shift, this paper clarifies the relationship between two prominent models and establishes fundamental hardness results.
The paper proves an equivalence between PQ learning and TDS learning in the distribution-free setting, showing that any PQ learning problem can be reduced to a TDS learning problem. This yields the first hardness results for distribution-free TDS learning of halfspaces, while also showing that membership queries enable efficient PQ learning of halfspaces.
Recent work on provably efficient algorithms for learning with distribution shift has focused on two models: PQ learning (Goldwasser et al. (2020)) and TDS learning (Klivans et al. (2024)). Algorithms for TDS learning are allowed to reject a test set entirely if distribution shift is detected. In contrast, PQ learners may only reject points that are deemed out-of-distribution on an individual basis. Our main result is a surprising equivalence between these two models in the distribution-free setting. In particular, we give an efficient black-box reduction from PQ learning to TDS learning for any Boolean concept class. This equivalence implies the first hardness results for distribution-free TDS learning of basic classes such as halfspaces. The main technical contribution underlying our equivalence is a method for boosting, via branching programs, the weak distinguishing power of TDS learners that have rejected the target domain. We also show that giving a learner access to membership queries sidesteps these hardness results and allows for efficient, distribution-free PQ learnability of halfspaces. Our algorithm iteratively recovers large-margin separators obtained by applying successive Forster transforms on the training data.