mlsanityData to 7 Oct 2026

Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise

arXiv 2102.05312 ↗First posted 10 Feb 2021cs.LG stat.MLcited by 18

Not on the map. Why?

Abstract (arXiv)

We give a computationally-efficient PAC active learning algorithm for d-dimensional homogeneous halfspaces that can tolerate Massart noise (Massart and N'ed'elec, 2006) and Tsybakov noise (Tsybakov, 2004). Specialized to the η-Massart noise setting, our algorithm achieves an information-theoretically near-optimal label complexity of tildeOleft( fracd(1-2η)2 polylog(frac1ε) right) under a wide range of unlabeled data distributions (specifically, the family of "structured distributions" defined in Diakonikolas et al. (2020)). Under the more challenging Tsybakov noise condition, we identify two subfamilies of noise conditions, under which our efficient algorithm provides label complexity guarantees strictly lower than passive learning algorithms.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 15 of its 50 references that are in the map. First posted on arXiv 10 Feb 2021.

Builds on

15 of 50 references.

References · 15

  1. 2017A Hitting Time Analysis of Stochastic Gradient Langevin Dynamicscited by 70
  2. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  3. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  4. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  5. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  6. 2017Active Learning for Cost-Sensitive Classificationcited by 40
  7. 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
  8. 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
  9. 2014Beyond Disagreement-based Agnostic Active Learningcited by 21
  10. 2020Learning Halfspaces with Tsybakov Noisecited by 15
  11. 2018Efficient active learning of sparse halfspacescited by 13
  12. 2020Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvabilitycited by 13
3 more
  1. 2020A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noisecited by 13
  2. 2020Noise in Classificationcited by 10
  3. 2013Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacycited by 4

Built on by

Cited by year (2026 to 7 Oct)

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

18 papers.

Sort:

  1. 2021Batch Active Learning at Scalecited by 127
  2. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  3. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  4. 2022Semi-Random Sparse Recovery in Nearly-Linear Timecited by 18
  5. 2023An Efficient Tester-Learner for Halfspacescited by 18
  6. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  7. 2021Forster Decomposition and Learning Halfspaces with Noisecited by 16
  8. 2022Fast Rates in Pool-Based Batch Active Learningcited by 15
  9. 2024Neural Active Learning Beyond Banditscited by 10
  10. 2024Learning Linear Utility Functions From Pairwise Comparison Queriescited by 6
  11. 2023Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noisecited by 5
  12. 2024Efficient PAC Learning of Halfspaces with Constant Malicious Noise Ratecited by 5
6 more
  1. 2025Learning Noisy Halfspaces with a Margin: Massart is No Harder than Randomcited by 5
  2. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  3. 2022Agnostic Learnability of Halfspaces via Logistic Losscited by 2
  4. 2023Learning to Abstain From Uninformative Datacited by 2
  5. 2023Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approachcited by 1
  6. 2026Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterizationcited by 0