# A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 74 references that are in the map.
- First posted on arXiv 23 Nov 2022.

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

- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [Complexity theoretic limitations on learning DNF's](https://mlsanity.com/paper/1404.3378/) (2014)
- [Outlier-Robust Clustering of Non-Spherical Mixtures](https://mlsanity.com/paper/2005.02970/) (2020)
- [List Decodable Subspace Recovery](https://mlsanity.com/paper/2002.03004/) (2020)
- [List-Decodable Covariance Estimation](https://mlsanity.com/paper/2206.10942/) (2022)
- [Moment-Matching Polynomials](https://mlsanity.com/paper/1301.0820/) (2013)
- [On the Minimal Error of Empirical Risk Minimization](https://mlsanity.com/paper/2102.12066/) (2021)

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

- [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)
- [Out-of-Distribution Generalization in Time Series: A Survey](https://mlsanity.com/paper/2503.13868/) (2025)
- [Tolerant Algorithms for Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2406.02742/) (2024)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (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)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [Distribution-Specific Auditing For Subgroup Fairness](https://mlsanity.com/paper/2401.16439/) (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)
- [Smoothed Analysis of Learning from Positive Samples](https://mlsanity.com/paper/2504.10428/) (2025)
- [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)
- [Robust learning of halfspaces under log-concave marginals](https://mlsanity.com/paper/2505.13708/) (2025)
- [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)
- [Efficient Testable Learning of General Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2408.17165/) (2024)
- [High-Accuracy List-Decodable Mean Estimation](https://mlsanity.com/paper/2511.17822/) (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)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)
- [Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning](https://mlsanity.com/paper/2609.10886/) (2026)
- [Efficient Robust Learning at the Information-Theoretic Limit](https://mlsanity.com/paper/2609.17655/) (2026)

## Abstract (arXiv)

A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the study of testable learning, where the goal is to replace hard-to-verify distributional assumptions (such as Gaussianity) with efficiently testable ones and to require that the learner succeed whenever the unknown distribution passes the corresponding test. In this model, they gave an efficient algorithm for learning halfspaces under testable assumptions that are provably satisfied by Gaussians. In this paper we give a powerful new approach for developing algorithms for testable learning using tools from moment matching and metric distances in probability. We obtain efficient testable learners for any concept class that admits low-degree sandwiching polynomials, capturing most important examples for which we have ordinary agnostic learners. We recover the results of Rubinfeld and Vasilyan as a corollary of our techniques while achieving improved, near-optimal sample complexity bounds for a broad range of concept classes and distributions. Surprisingly, we show that the information-theoretic sample complexity of testable learning is tightly characterized by the Rademacher complexity of the concept class, one of the most well-studied measures in statistical learning theory. In particular, uniform convergence is necessary and sufficient for testable learning. This leads to a fundamental separation from (ordinary) distribution-specific agnostic learning, where uniform convergence is sufficient but not necessary.