mlsanityData to 7 Oct 2026

Efficient Testable Learning of Halfspaces with Adversarial Label Noise

arXiv 2303.05485 ↗First posted 9 Mar 2023cs.LG stat.MLcited by 19

Not on the map. Why?

Abstract (arXiv)

We give the first polynomial-time algorithm for the testable learning of halfspaces in the presence of adversarial label noise under the Gaussian distribution. In the recently introduced testable learning model, one is required to produce 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 tester-learner runs in time poly(d/eps) and outputs a halfspace with misclassification error O(opt)+eps, where opt is the 0-1 error of the best fitting halfspace. At a technical level, our algorithm employs an iterative soft localization technique enhanced with appropriate testers to ensure that the data distribution is sufficiently similar to a Gaussian.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 15 of its 30 references that are in the map. First posted on arXiv 9 Mar 2023.

Builds on

15 of 30 references.

References · 15

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

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 5; 2025: 6; 2026: 6.

19 papers.

Sort:

  1. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  2. 2024Tolerant Algorithms for Learning with Arbitrary Covariate Shiftcited by 15
  3. 2024Efficient Discrepancy Testing for Learning with Distribution Shiftcited by 9
  4. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited by 7
  5. 2023Classical Verification of Quantum Learningcited by 6
  6. 2024Active Learning of General Halfspaces: Label Queries vs Membership Queriescited by 6
  7. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  8. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  9. 2026Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimensioncited by 3
  10. 2024Optimal Algorithms for Augmented Testing of Discrete Distributionscited by 2
  11. 2025Limitations of Membership Queries in Testable Learningcited by 2
  12. 2025Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distributioncited by 1
7 more
  1. 2026Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shiftcited by 1
  2. 2024Efficient Testable Learning of General Halfspaces with Adversarial Label Noisecited by 0
  3. 2025High-Accuracy List-Decodable Mean Estimationcited by 0
  4. 2026Testable Learning of General Halfspaces under Massart Noisecited by 0
  5. 2026Relatively Smart: A New Approach for Instance-Optimal Learningcited by 0
  6. 2026Testing Distributions Against Bounded Distinguisherscited by 0
  7. 2026Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learningcited by 0