mlsanityData to 14 Oct 2026

Cryptographic Hardness of Learning Halfspaces with Massart Noise

arXiv 2207.14266 ↗First posted 28 Jul 2022cs.LG cs.CC cs.DScited by 25

Not on the map. Why?

Abstract (arXiv)

We study the complexity of PAC learning halfspaces in the presence of Massart noise. In this problem, we are given i.i.d. labeled examples (x, y) ∈ ℝN × ± 1, where the distribution of x is arbitrary and the label y is a Massart corruption of f(x), for an unknown halfspace f: ℝN → ± 1, with flipping probability η(x) ≤ η < 1/2. The goal of the learner is to compute a hypothesis with small 0-1 error. Our main result is the first computational hardness result for this learning problem. Specifically, assuming the (widely believed) subexponential-time hardness of the Learning with Errors (LWE) problem, we show that no polynomial-time Massart halfspace learner can achieve error better than Omega(η), even if the optimal 0-1 error is small, namely OPT = 2^-logc (N) for any universal constant c ∈ (0, 1). Prior work had provided qualitatively similar evidence of hardness in the Statistical Query model. Our computational hardness result essentially resolves the polynomial PAC learnability of Massart halfspaces, by showing that known efficient learning algorithms for the problem are nearly best possible.

Key facts. Cited by 25 papers in the map (data through 14 Oct 2026). Builds on 10 of its 51 references that are in the map. First posted on arXiv 28 Jul 2022.

Builds on

10 of 51 references.

References · 10

  1. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  2. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  3. 2020Continuous LWEcited by 37
  4. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  5. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  6. 2021Forster Decomposition and Learning Halfspaces with Noisecited by 16
  7. 2022Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noisecited by 14
  8. 2020Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvabilitycited by 13
  9. 2021Boosting in the Presence of Massart Noisecited by 10
  10. 2019Slide Reduction, Revisited---Filling the Gaps in SVP Approximationcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 8; 2024: 3; 2025: 7; 2026: 5.

25 papers.

Sort:

  1. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  2. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
  3. 2023An Efficient Tester-Learner for Halfspacescited by 18
  4. 2022A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learningcited by 11
  5. 2023Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noisecited by 9
  6. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 9
  7. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited by 7
  8. 2024Improved Hardness Results for Learning Intersections of Halfspacescited by 6
  9. 2025A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noisecited by 6
  10. 2022SQ Lower Bounds for Learning Single Neurons with Massart Noisecited by 5
  11. 2023Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noisecited by 5
  12. 2025Smoothed Agnostic Learning of Halfspaces over the Hypercubecited by 3
13 more
  1. 2026Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimensioncited by 3
  2. 2024Collaborative Learning with Different Labeling Functionscited by 2
  3. 2025Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noisecited by 2
  4. 2023Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptionscited by 1
  5. 2023Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approachcited by 1
  6. 2023Agnostically Learning Multi-index Models with Queriescited by 1
  7. 2026Statistical Query Lower Bounds for Smoothed Agnostic Learningcited by 1
  8. 2024Efficient Testable Learning of General Halfspaces with Adversarial Label Noisecited by 0
  9. 2025Faster Algorithms for Agnostically Learning Disjunctions and their Implicationscited by 0
  10. 2025Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contaminationcited by 0
  11. 2026Testable Learning of General Halfspaces under Massart Noisecited by 0
  12. 2026Efficiently Learning Drifting Halfspaces with Massart Noisecited by 0
  13. 2026Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterizationcited by 0