# Semi-verified PAC Learning from the Crowd

arXiv: https://arxiv.org/abs/2106.07080 · HTML: https://mlsanity.com/paper/2106.07080/

## 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 (most cited first, 28 of 28)

- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Simple, Robust and Optimal Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1512.08949/) (2015)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues](https://mlsanity.com/paper/1510.05610/) (2015)
- [Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2012.09720/) (2020)
- [Efficient active learning of sparse halfspaces with arbitrary bounded noise](https://mlsanity.com/paper/2002.04840/) (2020)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Better Agnostic Clustering Via Relaxed Tensor Norms](https://mlsanity.com/paper/1711.07465/) (2017)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [List Decodable Mean Estimation in Nearly Linear Time](https://mlsanity.com/paper/2005.09796/) (2020)
- [List-Decodable Mean Estimation via Iterative Multi-Filtering](https://mlsanity.com/paper/2006.10715/) (2020)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction](https://mlsanity.com/paper/1606.05374/) (2016)
- [List Decodable Subspace Recovery](https://mlsanity.com/paper/2002.03004/) (2020)
- [A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise](https://mlsanity.com/paper/2010.01705/) (2020)
- [Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1507.04457/) (2015)
- [On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise](https://mlsanity.com/paper/2012.10793/) (2020)
- [The Sample Complexity of Best-k Items Selection from Pairwise Comparisons](https://mlsanity.com/paper/2007.03133/) (2020)
- [Achieving Budget-optimality with Adaptive Schemes in Crowdsourcing](https://mlsanity.com/paper/1602.03481/) (2016)
- [Efficient PAC Learning from the Crowd](https://mlsanity.com/paper/1703.07432/) (2017)
- [List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time](https://mlsanity.com/paper/2002.05139/) (2020)
- [Efficient PAC Learning from the Crowd with Pairwise Comparisons](https://mlsanity.com/paper/2011.01104/) (2020)
- [Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons](https://mlsanity.com/paper/1603.06881/) (2016)

## Built on by (most cited first, 4 of 4)

- [Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2407.10867/) (2024)
- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise](https://mlsanity.com/paper/2306.00673/) (2023)
- [Robust Estimation Under Heterogeneous Corruption Rates](https://mlsanity.com/paper/2508.15051/) (2025)

## 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.