# Efficient Discrepancy Testing for Learning with Distribution Shift

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 49 references that are in the map.
- First posted on arXiv 13 Jun 2024.

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

- [A survey on domain adaptation theory: learning bounds and theoretical guarantees](https://mlsanity.com/paper/2004.11829/) (2020)
- [Marginal Singularity, and the Benefits of Labels in Covariate-Shift](https://mlsanity.com/paper/1803.01833/) (2018)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [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)
- [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)
- [On Localized Discrepancy for Domain Adaptation](https://mlsanity.com/paper/2008.06242/) (2020)
- [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)
- [Limits of Model Selection under Transfer Learning](https://mlsanity.com/paper/2305.00152/) (2023)
- [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024)

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

- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Testing Noise Assumptions of Learning Algorithms](https://mlsanity.com/paper/2501.09189/) (2025)
- [Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees](https://mlsanity.com/paper/2502.16021/) (2025)
- [Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds](https://mlsanity.com/paper/2602.20111/) (2026)
- [Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2602.24178/) (2026)
- [Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift](https://mlsanity.com/paper/2605.07005/) (2026)
- [Iterative Chow Filtering for Learning with Distribution Shift](https://mlsanity.com/paper/2605.17251/) (2026)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)

## Abstract (arXiv)

A fundamental notion of distance between train and test distributions from the field of domain adaptation is discrepancy distance. While in general hard to compute, here we provide the first set of provably efficient algorithms for testing localized discrepancy distance, where discrepancy is computed with respect to a fixed output classifier. These results imply a broad set of new, efficient learning algorithms in the recently introduced model of Testable Learning with Distribution Shift (TDS learning) due to Klivans et al. (2023). Our approach generalizes and improves all prior work on TDS learning: (1) we obtain universal learners that succeed simultaneously for large classes of test distributions, (2) achieve near-optimal error rates, and (3) give exponential improvements for constant depth circuits. Our methods further extend to semi-parametric settings and imply the first positive results for low-dimensional convex sets. Additionally, we separate learning and testing phases and obtain algorithms that run in fully polynomial time at test time.