# Learning Geometric Concepts with Nasty Noise

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2017.

## Built on by (most cited first, 30 of 46)

- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [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)
- [Tolerant Algorithms for Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2406.02742/) (2024)
- [On Optimal Learning Under Targeted Data Poisoning](https://mlsanity.com/paper/2210.02713/) (2022)
- [Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds](https://mlsanity.com/paper/2404.02364/) (2024)
- [Sample-Optimal PAC Learning of Halfspaces with Malicious Noise](https://mlsanity.com/paper/2102.06247/) (2021)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [Efficient Discrepancy Testing for Learning with Distribution Shift](https://mlsanity.com/paper/2406.09373/) (2024)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Active Learning of General Halfspaces: Label Queries vs Membership Queries](https://mlsanity.com/paper/2501.00508/) (2024)
- [Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2307.08438/) (2023)
- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [Learning Constant-Depth Circuits in Malicious Noise Models](https://mlsanity.com/paper/2411.03570/) (2024)
- [Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals](https://mlsanity.com/paper/2411.14349/) (2024)
- [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025)
- [Testing Noise Assumptions of Learning Algorithms](https://mlsanity.com/paper/2501.09189/) (2025)
- [Robust Estimation for Nonparametric Families via Generative Adversarial Networks](https://mlsanity.com/paper/2202.01269/) (2022)
- [Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise](https://mlsanity.com/paper/2306.00673/) (2023)
- [Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs](https://mlsanity.com/paper/2404.00529/) (2024)
- [Robust learning of halfspaces under log-concave marginals](https://mlsanity.com/paper/2505.13708/) (2025)
- [Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness](https://mlsanity.com/paper/2506.03075/) (2025)
- [Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning](https://mlsanity.com/paper/2506.05252/) (2025)
- [Robustly Learning Monotone Single-Index Models](https://mlsanity.com/paper/2508.04670/) (2025)

## Abstract (arXiv)

We study the efficient learnability of geometric concept classes - specifically, low-degree polynomial threshold functions (PTFs) and intersections of halfspaces - when a fraction of the data is adversarially corrupted. We give the first polynomial-time PAC learning algorithms for these concept classes with dimension-independent error guarantees in the presence of nasty noise under the Gaussian distribution. In the nasty noise model, an omniscient adversary can arbitrarily corrupt a small fraction of both the unlabeled data points and their labels. This model generalizes well-studied noise models, including the malicious noise model and the agnostic (adversarial label noise) model. Prior to our work, the only concept class for which efficient malicious learning algorithms were known was the class of origin-centered halfspaces. Specifically, our robust learning algorithm for low-degree PTFs succeeds under a number of tame distributions -- including the Gaussian distribution and, more generally, any log-concave distribution with (approximately) known low-degree moments. For LTFs under the Gaussian distribution, we give a polynomial-time algorithm that achieves error O(ε), where ε is the noise rate. At the core of our PAC learning results is an efficient algorithm to approximate the low-degree Chow-parameters of any bounded function in the presence of nasty noise. To achieve this, we employ an iterative spectral method for outlier detection and removal, inspired by recent work in robust unsupervised learning. Our aforementioned algorithm succeeds for a range of distributions satisfying mild concentration bounds and moment assumptions. The correctness of our robust learning algorithm for intersections of halfspaces makes essential use of a novel robust inverse independence lemma that may be of broader interest.