# Efficient PAC Learning from the Crowd with Pairwise Comparisons

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2020.

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

- [Binary Classification with Confidence Difference](https://mlsanity.com/paper/2310.05632/) (2023)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [Transferring Annotator- and Instance-dependent Transition Matrix for Learning from Crowds](https://mlsanity.com/paper/2306.03116/) (2023)
- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise](https://mlsanity.com/paper/2306.00673/) (2023)
- [LLM-Augmented Computational Phenotyping of Long Covid](https://mlsanity.com/paper/2603.18115/) (2026)

## Abstract (arXiv)

We study crowdsourced PAC learning of threshold functions, where the labels are gathered from a pool of annotators some of whom may behave adversarially. This is yet a challenging problem and until recently has computationally and query efficient PAC learning algorithm been established by Awasthi et al. (2017). In this paper, we show that by leveraging the more easily acquired pairwise comparison queries, it is possible to exponentially reduce the label complexity while retaining the overall query complexity and runtime. Our main algorithmic contributions are a comparison-equipped labeling scheme that can faithfully recover the true labels of a small set of instances, and a label-efficient filtering process that in conjunction with the small labeled set can reliably infer the true labels of a large instance set.