# Active Learning with Label Comparisons

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 10 Apr 2022.

## Builds on (most cited first, 10 of 10)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [A Neural Representation of Sketch Drawings](https://mlsanity.com/paper/1704.03477/) (2017)
- [Contextual Dueling Bandits](https://mlsanity.com/paper/1502.06362/) (2015)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Adversarial Dueling Bandits](https://mlsanity.com/paper/2010.14563/) (2020)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Active Learning Polynomial Threshold Functions](https://mlsanity.com/paper/2201.09433/) (2022)

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

- [Always Tell Me The Odds: Fine-grained Conditional Probability Estimation](https://mlsanity.com/paper/2505.01595/) (2025)
- [Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback](https://mlsanity.com/paper/2302.03805/) (2023)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Actively learning a Bayesian matrix fusion model with deep side information](https://mlsanity.com/paper/2306.05331/) (2023)
- [A Markovian Formalism for Active Querying](https://mlsanity.com/paper/2306.08001/) (2023)

## Abstract (arXiv)

Supervised learning typically relies on manual annotation of the true labels. When there are many potential classes, searching for the best one can be prohibitive for a human annotator. On the other hand, comparing two candidate labels is often much easier. We focus on this type of pairwise supervision and ask how it can be used effectively in learning, and in particular in active learning. We obtain several insightful results in this context. In principle, finding the best of k labels can be done with k-1 active queries. We show that there is a natural class where this approach is sub-optimal, and that there is a more comparison-efficient active learning scheme. A key element in our analysis is the "label neighborhood graph" of the true distribution, which has an edge between two classes if they share a decision boundary. We also show that in the PAC setting, pairwise comparisons cannot provide improved sample complexity in the worst case. We complement our theoretical results with experiments, clearly demonstrating the effect of the neighborhood graph on sample complexity.