mlsanityData to 7 Oct 2026

Agnostic Proper Learning of Halfspaces under Gaussian Marginals

arXiv 2102.05629 ↗First posted 10 Feb 2021cs.LG cs.DS math.STcited by 21

Not on the map. Why?

Abstract (arXiv)

We study the problem of agnostically learning halfspaces under the Gaussian distribution. Our main result is the em first proper learning algorithm for this problem whose sample complexity and computational complexity qualitatively match those of the best known improper agnostic learner. Building on this result, we also obtain the first proper polynomial-time approximation scheme (PTAS) for agnostically learning homogeneous halfspaces. Our techniques naturally extend to agnostically learning linear models with respect to other non-linear activations, yielding in particular the first proper agnostic algorithm for ReLU regression.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 10 of its 37 references that are in the map. First posted on arXiv 10 Feb 2021.

Builds on

10 of 37 references.

References · 10

  1. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  2. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  3. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  4. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  5. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  6. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  7. 2020Approximation Schemes for ReLU Regressioncited by 34
  8. 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
  9. 2019Efficient Truncated Statistics with Unknown Truncationcited by 22
  10. 2014A PTAS for Agnostically Learning Halfspacescited by 21

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 1; 2023: 2; 2024: 6; 2025: 5; 2026: 4.

21 papers.

Sort:

  1. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  2. 2022Testing distributional assumptions of learning algorithmscited by 30
  3. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  4. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
  5. 2024Smoothed Analysis for Learning Concepts with Low Intrinsic Dimensioncited by 11
  6. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  7. 2021Semi-verified PAC Learning from the Crowdcited by 4
  8. 2024Distribution-Specific Auditing For Subgroup Fairnesscited by 4
  9. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  10. 2021Approximate Maximum Halfspace Discrepancycited by 3
  11. 2025Robust learning of halfspaces under log-concave marginalscited by 2
  12. 2025Learning and Testing Convex Functionscited by 2
9 more
  1. 2024Online Learning of Halfspaces with Massart Noisecited by 1
  2. 2024Reliable Learning of Halfspaces under Gaussian Marginalscited by 1
  3. 2025Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distributioncited by 1
  4. 2025A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercubecited by 1
  5. 2026Statistical Query Lower Bounds for Smoothed Agnostic Learningcited by 1
  6. 2024Efficient Testable Learning of General Halfspaces with Adversarial Label Noisecited by 0
  7. 2026Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginalscited by 0
  8. 2026A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspacescited by 0
  9. 2026Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginalscited by 0