# Active classification with comparison queries

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2017.

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

- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [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)
- [Binary Classification with Confidence Difference](https://mlsanity.com/paper/2310.05632/) (2023)
- [Teaching an Active Learner with Contrastive Examples](https://mlsanity.com/paper/2110.14888/) (2021)
- [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)
- [Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback](https://mlsanity.com/paper/2302.03805/) (2023)
- [Active Learning with Label Comparisons](https://mlsanity.com/paper/2204.04670/) (2022)
- [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)
- [Active Learning of Classifiers with Label and Seed Queries](https://mlsanity.com/paper/2209.03996/) (2022)
- [The Cost of Replicability in Active Learning](https://mlsanity.com/paper/2412.09686/) (2024)
- [On the Sample Complexity of Rank Regression from Pairwise Comparisons](https://mlsanity.com/paper/2105.01463/) (2021)
- [A Markovian Formalism for Active Querying](https://mlsanity.com/paper/2306.08001/) (2023)
- [Towards Fundamental Limits for Active Multi-distribution Learning](https://mlsanity.com/paper/2506.17607/) (2025)
- [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)
- [Preference Elicitation for Policy Optimization and Application to Aligning Heart Transplantation with Human Values](https://mlsanity.com/paper/2608.28620/) (2026)
- [Fast Interactive Search with a Scale-Free Comparison Oracle](https://mlsanity.com/paper/2306.01814/) (2023)
- [Manipulating Predictions over Discrete Inputs in Machine Teaching](https://mlsanity.com/paper/2401.17865/) (2024)
- [Minimizing Human Intervention in Online Classification](https://mlsanity.com/paper/2510.23557/) (2025)
- [Improving Selective Classification with Pairwise Queries for Binary Classification](https://mlsanity.com/paper/2605.30615/) (2026)
- [On the Sample Complexity of Active Learning with Membership Queries](https://mlsanity.com/paper/2609.27241/) (2026)

## Abstract (arXiv)

We study an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a specific restaurant (a label query); or which one of two restaurants did she like more (a comparison query). We focus on the class of half spaces, and show that under natural assumptions, such as large margin or bounded bit-description of the input examples, it is possible to reveal all the labels of a sample of size n using approximately O(log n) queries. This implies an exponential improvement over classical active learning, where only label queries are allowed. We complement these results by showing that if any of these assumptions is removed then, in the worst case, Omega(n) queries are required. Our results follow from a new general framework of active learning with additional queries. We identify a combinatorial dimension, called the inference dimension, that captures the query complexity when each additional query is determined by O(1) examples (such as comparison queries, each of which is determined by the two compared examples). Our results for half spaces follow by bounding the inference dimension in the cases discussed above.