mlsanityData to 14 Oct 2026

Semi-verified PAC Learning from the Crowd

arXiv 2106.07080 ↗First posted 13 Jun 2021cs.LG cs.DScited by 4

Not on the map. Why?

Abstract (arXiv)

We study the problem of crowdsourced PAC learning of threshold functions. This is a challenging problem and only recently have query-efficient algorithms been established under the assumption that a noticeable fraction of the workers are perfect. In this work, we investigate a more challenging case where the majority may behave adversarially and the rest behave as the Massart noise - a significant generalization of the perfectness assumption. We show that under the {semi-verified model} of Charikar et al. (2017), where we have (limited) access to a trusted oracle who always returns correct annotations, it is possible to PAC learn the underlying hypothesis class with a manageable amount of label queries. Moreover, we show that the labeling cost can be drastically mitigated via the more easily obtained comparison queries. Orthogonal to recent developments in semi-verified or list-decodable learning that crucially rely on data distributional assumptions, our PAC guarantee holds by exploring the wisdom of the crowd.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 28 of its 64 references that are in the map. First posted on arXiv 13 Jun 2021.

Builds on

28 of 64 references.

References · 28

  1. 2016Learning from Untrusted Datacited by 90
  2. 2015Simple, Robust and Optimal Ranking from Pairwise Comparisonscited by 70
  3. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  4. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  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. 2015Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issuescited by 32
  9. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  10. 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
  11. 2017Active classification with comparison queriescited by 27
  12. 2017Better Agnostic Clustering Via Relaxed Tensor Normscited by 21
16 more
  1. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  2. 2019The Power of Comparisons for Actively Learning Linear Classifierscited by 20
  3. 2020List Decodable Mean Estimation in Nearly Linear Timecited by 20
  4. 2020List-Decodable Mean Estimation via Iterative Multi-Filteringcited by 18
  5. 2020Noise-tolerant, Reliable Active Classification with Comparison Queriescited by 17
  6. 2016Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Predictioncited by 15
  7. 2020List Decodable Subspace Recoverycited by 13
  8. 2020A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noisecited by 13
  9. 2015Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisonscited by 11
  10. 2020On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noisecited by 11
  11. 2020The Sample Complexity of Best-k Items Selection from Pairwise Comparisonscited by 9
  12. 2016Achieving Budget-optimality with Adaptive Schemes in Crowdsourcingcited by 8
  13. 2017Efficient PAC Learning from the Crowdcited by 7
  14. 2020List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Timecited by 7
  15. 2020Efficient PAC Learning from the Crowd with Pairwise Comparisonscited by 7
  16. 2016Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisonscited by 6

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 2; 2025: 1.

4 papers.

  1. 2024Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attackscited by 5
  2. 2024Efficient PAC Learning of Halfspaces with Constant Malicious Noise Ratecited by 5
  3. 2023Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noisecited by 3
  4. 2025Robust Estimation Under Heterogeneous Corruption Ratescited by 1