# Noise-tolerant, Reliable Active Classification with Comparison Queries

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2020.

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

- [A Survey on Cost Types, Interaction Schemes, and Annotator Performance Models in Selection Algorithms for Active Learning in Classification](https://mlsanity.com/paper/2109.11301/) (2021)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)
- [Bounded Memory Active Learning through Enriched Queries](https://mlsanity.com/paper/2102.05047/) (2021)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)
- [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Active Learning Polynomial Threshold Functions](https://mlsanity.com/paper/2201.09433/) (2022)
- [Do PAC-Learners Learn the Marginal Distribution?](https://mlsanity.com/paper/2302.06285/) (2023)
- [Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds](https://mlsanity.com/paper/2602.20111/) (2026)
- [On Margin-Based Cluster Recovery with Oracle Queries](https://mlsanity.com/paper/2106.04913/) (2021)
- [The Cost of Replicability in Active Learning](https://mlsanity.com/paper/2412.09686/) (2024)
- [Active Learning for Decision Trees with Provable Guarantees](https://mlsanity.com/paper/2601.20775/) (2026)
- [Sorting from Counterexamples](https://mlsanity.com/paper/2608.21579/) (2026)
- [Metric k-clustering using only Weak Comparison Oracles](https://mlsanity.com/paper/2601.19333/) (2026)
- [Improving Selective Classification with Pairwise Queries for Binary Classification](https://mlsanity.com/paper/2605.30615/) (2026)

## Abstract (arXiv)

With the explosion of massive, widely available unlabeled data in the past years, finding label and time efficient, robust learning algorithms has become ever more important in theory and in practice. We study the paradigm of active learning, in which algorithms with access to large pools of data may adaptively choose what samples to label in the hope of exponentially increasing efficiency. By introducing comparisons, an additional type of query comparing two points, we provide the first time and query efficient algorithms for learning non-homogeneous linear separators robust to bounded (Massart) noise. We further provide algorithms for a generalization of the popular Tsybakov low noise condition, and show how comparisons provide a strong reliability guarantee that is often impractical or impossible with only labels - returning a classifier that makes no errors with high probability.