mlsanityData to 14 Oct 2026

A PTAS for Agnostically Learning Halfspaces

arXiv 1410.7050 ↗First posted 26 Oct 2014cs.DS cs.LGcited by 21

Not on the map. Why?

Abstract (arXiv)

We present a PTAS for agnostically learning halfspaces w.r.t. the uniform distribution on the d dimensional sphere. Namely, we show that for every μ>0 there is an algorithm that runs in time poly(d,frac1ε), and is guaranteed to return a classifier with error at most (1+μ)opt+ε, where opt is the error of the best halfspace classifier. This improves on Awasthi, Balcan and Long [ABL14] who showed an algorithm with an (unspecified) constant approximation ratio. Our algorithm combines the classical technique of polynomial regression (e.g. [LMN89, KKMS05]), together with the new localization technique of [ABL14].

Key facts. Cited by 21 papers in the map (data through 14 Oct 2026). First posted on arXiv 26 Oct 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

21 papers.

Sort:

  1. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  2. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  3. 2022Testing distributional assumptions of learning algorithmscited by 30
  4. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  5. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
  6. 2023An Efficient Tester-Learner for Halfspacescited by 18
  7. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  8. 2021Sample-Optimal PAC Learning of Halfspaces with Malicious Noisecited by 11
  9. 2023PAC Learning Linear Thresholds from Label Proportionscited by 10
  10. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  11. 2024Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFscited by 3
  12. 2022Agnostic Learnability of Halfspaces via Logistic Losscited by 2
9 more
  1. 2025Robust learning of halfspaces under log-concave marginalscited by 2
  2. 2026Agnostic learning in (almost) optimal time via Gaussian surface areacited by 2
  3. 2024Solving 0-1 Integer Programs with Unknown Knapsack Constraints Using Membership Oraclescited by 1
  4. 2025A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercubecited by 1
  5. 2021On Agnostic PAC Learning using L2-polynomial Regression and Fourier-based Algorithmscited by 0
  6. 2024Efficient Testable Learning of General Halfspaces with Adversarial Label Noisecited by 0
  7. 2026The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)cited by 0
  8. 2026Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginalscited by 0
  9. 2026A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspacescited by 0