# A Compression Technique for Analyzing Disagreement-Based Active Learning

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

## Key facts

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

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

- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms](https://mlsanity.com/paper/2310.14772/) (2023)
- [Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstention](https://mlsanity.com/paper/2310.14770/) (2023)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [Understanding Uncertainty Sampling via Equivalent Loss](https://mlsanity.com/paper/2307.02719/) (2023)
- [Universal Rates of Empirical Risk Minimization](https://mlsanity.com/paper/2412.02810/) (2024)
- [Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs](https://mlsanity.com/paper/2609.33760/) (2026)
- [Sample Compression Scheme Reductions](https://mlsanity.com/paper/2410.13012/) (2024)
- [Towards Fundamental Limits for Active Multi-distribution Learning](https://mlsanity.com/paper/2506.17607/) (2025)

## Abstract (arXiv)

We introduce a new and improved characterization of the label complexity of disagreement-based active learning, in which the leading quantity is the version space compression set size. This quantity is defined as the size of the smallest subset of the training data that induces the same version space. We show various applications of the new characterization, including a tight analysis of CAL and refined label complexity bounds for linear separators under mixtures of Gaussians and axis-aligned rectangles under product densities. The version space compression set size, as well as the new characterization of the label complexity, can be naturally extended to agnostic learning problems, for which we show new speedup results for two well known active learning algorithms.