# Testable Learning with Distribution Shift

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 45 references that are in the map.
- First posted on arXiv 25 Nov 2023.

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

- [A survey on domain adaptation theory: learning bounds and theoretical guarantees](https://mlsanity.com/paper/2004.11829/) (2020)
- [An Efficient Tester-Learner for Halfspaces](https://mlsanity.com/paper/2302.14853/) (2023)

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

- [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)
- [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)
- [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024)
- [Learning Constant-Depth Circuits in Malicious Noise Models](https://mlsanity.com/paper/2411.03570/) (2024)
- [Specialization after Generalization: Towards Understanding Test-Time Training in Foundation Models](https://mlsanity.com/paper/2509.24510/) (2025)
- [Help Me Help You: The Aggregate Value of Source and Target Data in Transfer Learning](https://mlsanity.com/paper/2408.16189/) (2024)
- [Learning multivariate Gaussians with imperfect advice](https://mlsanity.com/paper/2411.12700/) (2024)
- [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)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Limitations of Membership Queries in Testable Learning](https://mlsanity.com/paper/2512.02279/) (2025)
- [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)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [α-LoRA: Effective Fine-Tuning via Base Model Rescaling](https://mlsanity.com/paper/2510.21345/) (2025)
- [Testable Learning of General Halfspaces under Massart Noise](https://mlsanity.com/paper/2602.22300/) (2026)
- [Relatively Smart: A New Approach for Instance-Optimal Learning](https://mlsanity.com/paper/2603.01346/) (2026)
- [A Note on Non-Negative L1-Approximating Polynomials](https://mlsanity.com/paper/2605.08072/) (2026)
- [The Label Complexity of Useful Class-Conditional Prediction Sets under Distribution Shift](https://mlsanity.com/paper/2607.18088/) (2026)
- [Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning](https://mlsanity.com/paper/2609.10886/) (2026)
- [When Can Old Evaluations Certify a New Model? Label-Efficient Release Decisions under Evaluator Drift](https://mlsanity.com/paper/2609.32267/) (2026)

## Abstract (arXiv)

We revisit the fundamental problem of learning with distribution shift, in which 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 bound the loss of a classifier in terms of some notion of distance between D and D'. These distances, however, seem 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, where we can obtain provably efficient algorithms for certifying the performance of a classifier on a test distribution. In this model, a learner outputs a classifier with low test error whenever samples from D and D' pass an associated test; moreover, the test must accept if the marginal of D equals the marginal of D'. We give several positive results for learning well-studied concept classes such as halfspaces, intersections of halfspaces, and decision trees when the marginal of D is Gaussian or uniform on ± 1d. Prior to our work, no efficient algorithms for these basic cases were known without strong assumptions on D'. For halfspaces in the realizable case (where there exists a halfspace consistent with both D and D'), we combine a moment-matching approach with ideas from active learning to simulate an efficient oracle for estimating disagreement regions. To extend to the non-realizable setting, we apply recent work from testable (agnostic) learning. More generally, we prove that any function class with low-degree L2-sandwiching polynomial approximators can be learned in our model. We apply constructions from the pseudorandomness literature to obtain the required approximators.