# Complexity Theoretic Limitations on Learning Halfspaces

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2015.

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

- [Theory of overparametrization in quantum neural networks](https://mlsanity.com/paper/2109.11676/) (2021)
- [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)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [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)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [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)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise](https://mlsanity.com/paper/2101.01152/) (2021)
- [Forster Decomposition and Learning Halfspaces with Noise](https://mlsanity.com/paper/2107.05582/) (2021)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2201.09818/) (2022)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Provable Robustness of Adversarial Training for Learning Halfspaces with Noise](https://mlsanity.com/paper/2104.09437/) (2021)
- [Boosting in the Presence of Massart Noise](https://mlsanity.com/paper/2106.07779/) (2021)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)
- [Learning Linear Utility Functions From Pairwise Comparison Queries](https://mlsanity.com/paper/2405.02612/) (2024)
- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Omnipredicting Single-Index Models with Multi-Index Models](https://mlsanity.com/paper/2411.13083/) (2024)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs](https://mlsanity.com/paper/2201.07206/) (2022)
- [SQ Lower Bounds for Learning Single Neurons with Massart Noise](https://mlsanity.com/paper/2210.09949/) (2022)
- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025)
- [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)

## Abstract (arXiv)

We study the problem of agnostically learning halfspaces which is defined by a fixed but unknown distribution D on mathbbQn× ± 1. We define ErrHALF(D) as the least error of a halfspace classifier for D. A learner who can access D has to return a hypothesis whose error is small compared to ErrHALF(D). Using the recently developed method of the author, Linial and Shalev-Shwartz we prove hardness of learning results under a natural assumption on the complexity of refuting random K-XOR formulas. We show that no efficient learning algorithm has non-trivial worst-case performance even under the guarantees that ErrHALF(D) ≤ η for arbitrarily small constant η>0, and that D is supported in ± 1n× ± 1. Namely, even under these favorable conditions its error must be ≥ frac12-frac1nc for every c>0. In particular, no efficient algorithm can achieve a constant approximation ratio. Under a stronger version of the assumption (where K can be poly-logarithmic in n), we can take η = 2^-log1-nu(n) for arbitrarily small nu>0. Interestingly, this is even stronger than the best known lower bounds (Arora et. al. 1993, Feldamn et. al. 2006, Guruswami and Raghavendra 2006) for the case that the learner is restricted to return a halfspace classifier (i.e. proper learning).