mlsanityData to 7 Oct 2026

Non-Convex SGD Learns Halfspaces with Adversarial Label Noise

arXiv 2006.06742 ↗First posted 11 Jun 2020cs.LG stat.MLcited by 30

Not on the map. Why?

Abstract (arXiv)

We study the problem of agnostically learning homogeneous halfspaces in the distribution-specific PAC model. For a broad family of structured distributions, including log-concave distributions, we show that non-convex SGD efficiently converges to a solution with misclassification error O(opt)+eps, where opt is the misclassification error of the best-fitting halfspace. In sharp contrast, we show that optimizing any convex surrogate inherently leads to misclassification error of ω(opt), even under Gaussian marginals.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

30 papers.

Sort:

  1. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  2. 2022Testing distributional assumptions of learning algorithmscited by 30
  3. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  4. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  5. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  6. 2021Self-training Converts Weak Learners to Strong Learners in Mixture Modelscited by 19
  7. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
  8. 2023An Efficient Tester-Learner for Halfspacescited by 18
  9. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  10. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  11. 2023Agnostically Learning Single-Index Models using Omnipredictorscited by 16
  12. 2021Provable Robustness of Adversarial Training for Learning Halfspaces with Noisecited by 10
18 more
  1. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 8
  2. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited by 7
  3. 2025Learning Noisy Halfspaces with a Margin: Massart is No Harder than Randomcited by 5
  4. 2024Distribution-Specific Auditing For Subgroup Fairnesscited by 4
  5. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  6. 2021AdaBoost and robust one-bit compressed sensingcited by 2
  7. 2022Agnostic Learnability of Halfspaces via Logistic Losscited by 2
  8. 2025Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Ratecited by 2
  9. 2026Agnostic learning in (almost) optimal time via Gaussian surface areacited by 2
  10. 2024Reliable Learning of Halfspaces under Gaussian Marginalscited by 1
  11. 2025Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distributioncited by 1
  12. 2025A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercubecited by 1
  13. 2026Statistical Query Lower Bounds for Smoothed Agnostic Learningcited by 1
  14. 2024Efficient Testable Learning of General Halfspaces with Adversarial Label Noisecited by 0
  15. 2026Testable Learning of General Halfspaces under Massart Noisecited by 0
  16. 2026Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginalscited by 0
  17. 2026Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginalscited by 0
  18. 2026Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginalscited by 0