mlsanityData to 14 Oct 2026

Efficient Testable Learning of General Halfspaces with Adversarial Label Noise

arXiv 2408.17165 ↗First posted 30 Aug 2024cs.LG cs.DS stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the task of testable learning of general -- not necessarily homogeneous -- halfspaces with adversarial label noise with respect to the Gaussian distribution. In the testable learning framework, the goal is to develop a tester-learner such that if the data passes the tester, then one can trust the output of the robust learner on the data.Our main result is the first polynomial time tester-learner for general halfspaces that achieves dimension-independent misclassification error. At the heart of our approach is a new methodology to reduce testable learning of general halfspaces to testable learning of nearly homogeneous halfspaces that may be of broader interest.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 16 of its 27 references that are in the map. First posted on arXiv 30 Aug 2024.

Builds on

16 of 27 references.

References · 16

  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. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  6. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  7. 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
  8. 2022Testing distributional assumptions of learning algorithmscited by 30
  9. 2022A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexitycited by 27
  10. 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
  11. 2014A PTAS for Agnostically Learning Halfspacescited by 21
  12. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
4 more
  1. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
  2. 2023An Efficient Tester-Learner for Halfspacescited by 18
  3. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  4. 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16

Built on by

Not cited yet.