mlsanityData to 7 Oct 2026

Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise

arXiv 2306.16352 ↗First posted 28 Jun 2023cs.LG cs.DS math.STcited by 9

Not on the map. Why?

Abstract (arXiv)

We study the problem of PAC learning γ-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms. Concretely, the sample complexity of the problem is widetildeTheta(1/(γ2 ε)). We start by giving a simple efficient algorithm with sample complexity widetildeO(1/(γ2 ε2)). Our main result is a lower bound for Statistical Query (SQ) algorithms and low-degree polynomial tests suggesting that the quadratic dependence on 1/ε in the sample complexity is inherent for computationally efficient algorithms. Specifically, our results imply a lower bound of widetildeOmega(1/(γ1/2 ε2)) on the sample complexity of any efficient SQ learner or low-degree test.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 11 of its 31 references that are in the map. First posted on arXiv 28 Jun 2023.

Builds on

11 of 31 references.

References · 11

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  2. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  3. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  4. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  5. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  6. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  7. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  8. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  9. 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
  10. 2022Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noisecited by 14
  11. 2023SLaM: Student-Label Mixing for Distillation with Unlabeled Examplescited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 3; 2026: 3.

9 papers.

  1. 2024Replicable Learning of Large-Margin Halfspacescited by 12
  2. 2025A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noisecited by 6
  3. 2023Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noisecited by 5
  4. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  5. 2025Learning Noisy Halfspaces with a Margin: Massart is No Harder than Randomcited by 5
  6. 2025A General Framework for Estimating Preferences Using Response Time Datacited by 3
  7. 2026Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barrierscited by 0
  8. 2026Efficiently Learning Drifting Halfspaces with Massart Noisecited by 0
  9. 2026Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterizationcited by 0