mlsanityData to 7 Oct 2026

A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise

arXiv 2501.09691 ↗First posted 16 Jan 2025cs.LG cs.DS math.STcited by 6

Not on the map. Why?

Abstract (arXiv)

We study the problem of PAC learning γ-margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem is known to be widetildeTheta(1/(γ2 ε)). Prior computationally efficient algorithms for the problem incur sample complexity tildeO(1/(γ4 ε3)) and achieve 0-1 error of η+ε, where η<1/2 is the upper bound on the noise rate. Recent work gave evidence of an information-computation tradeoff, suggesting that a quadratic dependence on 1/ε is required for computationally efficient algorithms. Our main result is a computationally efficient learner with sample complexity widetildeTheta(1/(γ2 ε2)), nearly matching this lower bound. In addition, our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 20 of its 37 references that are in the map. First posted on arXiv 16 Jan 2025.

Builds on

20 of 37 references.

References · 20

  1. 2017A Hitting Time Analysis of Stochastic Gradient Langevin Dynamicscited by 70
  2. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  3. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  4. 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
  5. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  6. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  7. 2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
  8. 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
  9. 2021Forster Decomposition and Learning Halfspaces with Noisecited by 16
  10. 2020Learning Halfspaces with Tsybakov Noisecited by 15
  11. 2022Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noisecited by 14
  12. 2020Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvabilitycited by 13
8 more
  1. 2020A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noisecited by 13
  2. 2022A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learningcited by 11
  3. 2021Boosting in the Presence of Massart Noisecited by 10
  4. 2021ReLU Regression with Massart Noisecited by 10
  5. 2023SLaM: Student-Label Mixing for Distillation with Unlabeled Examplescited by 9
  6. 2023Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noisecited by 9
  7. 2022SQ Lower Bounds for Learning Single Neurons with Massart Noisecited by 5
  8. 2023Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noisecited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 5; 2026: 1.

6 papers.

  1. 2025A General Framework for Estimating Preferences Using Response Time Datacited by 3
  2. 2025Conservative classifiers do consistently well with improving agents: characterizing statistical and online learningcited by 2
  3. 2025A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercubecited by 1
  4. 2025Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learningcited by 0
  5. 2025Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contaminationcited by 0
  6. 2026Efficiently Learning Drifting Halfspaces with Massart Noisecited by 0