mlsanityData to 14 Oct 2026

Tester-Learners for Halfspaces: Universal Algorithms

arXiv 2305.11765 ↗First posted 19 May 2023cs.LG cs.DS stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

We give the first tester-learner for halfspaces that succeeds universally over a wide class of structured distributions. Our universal tester-learner runs in fully polynomial time and has the following guarantee: the learner achieves error O(opt) + ε on any labeled distribution that the tester accepts, and moreover, the tester accepts whenever the marginal is any distribution that satisfies a Poincar'e inequality. In contrast to prior work on testable learning, our tester is not tailored to any single target distribution but rather succeeds for an entire target class of distributions. The class of Poincar'e distributions includes all strongly log-concave distributions, and, assuming the Kannan--L'ovasz--Simonovits (KLS) conjecture, includes all log-concave distributions. In the special case where the label noise is known to be Massart, our tester-learner achieves error opt + ε while accepting all log-concave distributions unconditionally (without assuming KLS). Our tests rely on checking hypercontractivity of the unknown distribution using a sum-of-squares (SOS) program, and crucially make use of the fact that Poincar'e distributions are certifiably hypercontractive in the SOS framework.

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). Builds on 21 of its 45 references that are in the map. First posted on arXiv 19 May 2023.

Builds on

21 of 45 references.

References · 21

  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. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  4. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  5. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  6. 2019List-Decodable Linear Regressioncited by 42
  7. 2019List Decodable Learning via Sum of Squarescited by 37
  8. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  9. 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
  10. 2022Testing distributional assumptions of learning algorithmscited by 30
  11. 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
  12. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
9 more
  1. 2022A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexitycited by 27
  2. 2014A PTAS for Agnostically Learning Halfspacescited by 21
  3. 2017Better Agnostic Clustering Via Relaxed Tensor Normscited by 21
  4. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
  5. 2021Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noisecited by 18
  6. 2023An Efficient Tester-Learner for Halfspacescited by 18
  7. 2018Efficient active learning of sparse halfspacescited by 13
  8. 2020Noise in Classificationcited by 11
  9. 2018The Kannan-Lov'asz-Simonovits Conjecturecited by 4

Built on by

Cited by year (2026 to 14 Oct)

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

17 papers.

Sort:

  1. 2024Tolerant Algorithms for Learning with Arbitrary Covariate Shiftcited by 15
  2. 2024Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Boundscited by 13
  3. 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
  4. 2024Efficient Discrepancy Testing for Learning with Distribution Shiftcited by 9
  5. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited by 7
  6. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  7. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  8. 2025Smoothed Analysis of Learning from Positive Samplescited by 3
  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. 2026Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shiftcited by 1
5 more
  1. 2024Efficient Testable Learning of General Halfspaces with Adversarial Label Noisecited by 0
  2. 2026Testable Learning of General Halfspaces under Massart Noisecited by 0
  3. 2026Relatively Smart: A New Approach for Instance-Optimal Learningcited by 0
  4. 2026Algorithms with Polynomially-Improved Approximation Factors for the 2 rightarrow q Norm, and Applicationscited by 0
  5. 2026Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learningcited by 0