# Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift

arXiv: https://arxiv.org/abs/2605.07005 · HTML: https://mlsanity.com/paper/2605.07005/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 34 references that are in the map.
- First posted on arXiv 7 May 2026.

## Builds on (most cited first, 19 of 19)

- [A survey on domain adaptation theory: learning bounds and theoretical guarantees](https://mlsanity.com/paper/2004.11829/) (2020)
- [Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples](https://mlsanity.com/paper/2007.05145/) (2020)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [Testable Learning with Distribution Shift](https://mlsanity.com/paper/2311.15142/) (2023)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Efficient Testable Learning of Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2303.05485/) (2023)
- [An Efficient Tester-Learner for Halfspaces](https://mlsanity.com/paper/2302.14853/) (2023)
- [Tester-Learners for Halfspaces: Universal Algorithms](https://mlsanity.com/paper/2305.11765/) (2023)
- [Efficient Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2102.07802/) (2021)
- [Tolerant Algorithms for Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2406.02742/) (2024)
- [Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds](https://mlsanity.com/paper/2404.02364/) (2024)
- [A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning](https://mlsanity.com/paper/2212.03008/) (2022)
- [Testably Learning Polynomial Threshold Functions](https://mlsanity.com/paper/2406.06106/) (2024)
- [Efficient Discrepancy Testing for Learning with Distribution Shift](https://mlsanity.com/paper/2406.09373/) (2024)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Improved Hardness Results for Learning Intersections of Halfspaces](https://mlsanity.com/paper/2402.15995/) (2024)
- [Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees](https://mlsanity.com/paper/2502.16021/) (2025)
- [Limitations of Membership Queries in Testable Learning](https://mlsanity.com/paper/2512.02279/) (2025)

## Built on by (most cited first, 1 of 1)

- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)

## Abstract (arXiv)

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.