# Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2020.

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

- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [An Efficient Tester-Learner for Halfspaces](https://mlsanity.com/paper/2302.14853/) (2023)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [Non-Gaussian Component Analysis via Lattice Basis Reduction](https://mlsanity.com/paper/2112.09104/) (2021)
- [Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2201.09818/) (2022)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning](https://mlsanity.com/paper/2212.03008/) (2022)
- [Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2306.16352/) (2023)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Improved Hardness Results for Learning Intersections of Halfspaces](https://mlsanity.com/paper/2402.15995/) (2024)
- [Statistical Query Lower Bounds for Learning Truncated Gaussians](https://mlsanity.com/paper/2403.02300/) (2024)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)
- [A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise](https://mlsanity.com/paper/2501.09691/) (2025)
- [SQ Lower Bounds for Learning Single Neurons with Massart Noise](https://mlsanity.com/paper/2210.09949/) (2022)
- [Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2307.08438/) (2023)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models](https://mlsanity.com/paper/2206.04589/) (2022)
- [Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2602.24178/) (2026)
- [Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise](https://mlsanity.com/paper/2502.11413/) (2025)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)
- [Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions](https://mlsanity.com/paper/2309.11657/) (2023)
- [Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach](https://mlsanity.com/paper/2310.15411/) (2023)
- [SQ Lower Bounds for Learning Bounded Covariance GMMs](https://mlsanity.com/paper/2306.13057/) (2023)
- [On Learning Parallel Pancakes with Mostly Uniform Weights](https://mlsanity.com/paper/2504.15251/) (2025)
- [Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination](https://mlsanity.com/paper/2510.10665/) (2025)
- [Testable Learning of General Halfspaces under Massart Noise](https://mlsanity.com/paper/2602.22300/) (2026)
- [A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces](https://mlsanity.com/paper/2605.02350/) (2026)
- [Efficiently Learning Drifting Halfspaces with Massart Noise](https://mlsanity.com/paper/2606.11149/) (2026)
- [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)

## Abstract (arXiv)

We study the problem of PAC learning halfspaces with Massart noise. Given labeled samples (x, y) from a distribution D on ℝd ×  ± 1 such that the marginal Dx on the examples is arbitrary and the label y of example x is generated from the target halfspace corrupted by a Massart adversary with flipping probability η(x) ≤ η ≤ 1/2, the goal is to compute a hypothesis with small misclassification error. The best known poly(d, 1/ε)-time algorithms for this problem achieve error of η+ε, which can be far from the optimal bound of OPT+ε, where OPT = Ex ~ Dx [η(x)]. While it is known that achieving OPT+o(1) error requires super-polynomial time in the Statistical Query model, a large gap remains between known upper and lower bounds. In this work, we essentially characterize the efficient learnability of Massart halfspaces in the Statistical Query (SQ) model. Specifically, we show that no efficient SQ algorithm for learning Massart halfspaces on ℝd can achieve error better than Omega(η), even if OPT = 2^-logc (d), for any universal constant c ∈ (0, 1). Furthermore, when the noise upper bound η is close to 1/2, our error lower bound becomes η - oη(1), where the oη(1) term goes to 0 when η approaches 1/2. Our results provide strong evidence that known learning algorithms for Massart halfspaces are nearly best possible, thereby resolving a longstanding open problem in learning theory.