# The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 95 references that are in the map.
- First posted on arXiv 26 May 2025.

## Builds on (most cited first, 30 of 50)

- [DataComp: In search of the next generation of multimodal datasets](https://mlsanity.com/paper/2304.14108/) (2023)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [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)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples](https://mlsanity.com/paper/2007.05145/) (2020)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [High-Dimensional Robust Mean Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1811.09380/) (2018)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Non-Convex SGD Learns Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2006.06742/) (2020)
- [Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2012.09720/) (2020)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [Efficient Statistics, in High Dimensions, from Truncated Samples](https://mlsanity.com/paper/1809.03986/) (2018)
- [Outlier-robust moment-estimation via sum-of-squares](https://mlsanity.com/paper/1711.11581/) (2017)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [Testable Learning with Distribution Shift](https://mlsanity.com/paper/2311.15142/) (2023)
- [Computationally and Statistically Efficient Truncated Regression](https://mlsanity.com/paper/2010.12000/) (2020)
- [Better Agnostic Clustering Via Relaxed Tensor Norms](https://mlsanity.com/paper/1711.07465/) (2017)
- [List Decodable Mean Estimation in Nearly Linear Time](https://mlsanity.com/paper/2005.09796/) (2020)
- [Efficient Testable Learning of Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2303.05485/) (2023)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [An Efficient Tester-Learner for Halfspaces](https://mlsanity.com/paper/2302.14853/) (2023)

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

- [Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2602.24178/) (2026)
- [Robust Learning with Optimal Error](https://mlsanity.com/paper/2604.02555/) (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)
- [High-Accuracy List-Decodable Mean Estimation](https://mlsanity.com/paper/2511.17822/) (2025)
- [Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization](https://mlsanity.com/paper/2606.17215/) (2026)
- [Efficient Robust Learning at the Information-Theoretic Limit](https://mlsanity.com/paper/2609.17655/) (2026)

## Abstract (arXiv)

Inspired by recent work on learning with distribution shift, we give a general outlier removal algorithm called iterative polynomial filtering and show a number of striking applications for supervised learning with contamination: (1) We show that any function class that can be approximated by low-degree polynomials with respect to a hypercontractive distribution can be efficiently learned under bounded contamination (also known as nasty noise). This is a surprising resolution to a longstanding gap between the complexity of agnostic learning and learning with contamination, as it was widely believed that low-degree approximators only implied tolerance to label noise. In particular, it implies the first efficient algorithm for learning halfspaces with η-bounded contamination up to error 2η+ε with respect to the Gaussian distribution. (2) For any function class that admits the (stronger) notion of sandwiching approximators, we obtain near-optimal learning guarantees even with respect to heavy additive contamination, where far more than 1/2 of the training set may be added adversarially. Prior related work held only for regression and in a list-decodable setting. (3) We obtain the first efficient algorithms for tolerant testable learning of functions of halfspaces with respect to any fixed log-concave distribution. Even the non-tolerant case for a single halfspace in this setting had remained open. These results significantly advance our understanding of efficient supervised learning under contamination, a setting that has been much less studied than its unsupervised counterpart.