# Bounded Memory Active Learning through Enriched Queries

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 63 references that are in the map.
- First posted on arXiv 9 Feb 2021.

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

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [Memory-Sample Tradeoffs for Linear Regression with Small Error](https://mlsanity.com/paper/1904.08544/) (2019)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Extractor-Based Time-Space Lower Bounds for Learning](https://mlsanity.com/paper/1708.02639/) (2017)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost](https://mlsanity.com/paper/1908.04976/) (2019)
- [Space lower bounds for linear prediction in the streaming model](https://mlsanity.com/paper/1902.03498/) (2019)
- [Exact Recovery of Mangled Clusters with Same-Cluster Queries](https://mlsanity.com/paper/2006.04675/) (2020)
- [Approximate Correlation Clustering Using Same-Cluster Queries](https://mlsanity.com/paper/1712.06865/) (2017)
- [Interactive Bayesian Hierarchical Clustering](https://mlsanity.com/paper/1602.03258/) (2016)
- [Towards a combinatorial characterization of bounded memory learning](https://mlsanity.com/paper/2002.03123/) (2020)
- [Universal guarantees for decision tree induction via a higher-order splitting criterion](https://mlsanity.com/paper/2010.08633/) (2020)
- [Generalized comparison trees for point-location problems](https://mlsanity.com/paper/1804.08237/) (2018)
- [A General Memory-Bounded Learning Algorithm](https://mlsanity.com/paper/1712.03524/) (2017)
- [Active Learning a Convex Body in Low Dimensions](https://mlsanity.com/paper/1903.03693/) (2019)
- [Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms](https://mlsanity.com/paper/2009.01161/) (2020)
- [Optimal bounds for approximate counting](https://mlsanity.com/paper/2010.02116/) (2020)

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

- [Tight Memory-Regret Lower Bounds for Streaming Bandits](https://mlsanity.com/paper/2306.07903/) (2023)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Active Learning Polynomial Threshold Functions](https://mlsanity.com/paper/2201.09433/) (2022)
- [On Language Generation in the Limit with Bounded Memory](https://mlsanity.com/paper/2605.30324/) (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)
- [Active Learning for Decision Trees with Provable Guarantees](https://mlsanity.com/paper/2601.20775/) (2026)
- [Improving Selective Classification with Pairwise Queries for Binary Classification](https://mlsanity.com/paper/2605.30615/) (2026)

## Abstract (arXiv)

The explosive growth of easily-accessible unlabeled data has lead to growing interest in active learning, a paradigm in which data-hungry learning algorithms adaptively select informative examples in order to lower prohibitively expensive labeling costs. Unfortunately, in standard worst-case models of learning, the active setting often provides no improvement over non-adaptive algorithms. To combat this, a series of recent works have considered a model in which the learner may ask enriched queries beyond labels. While such models have seen success in drastically lowering label costs, they tend to come at the expense of requiring large amounts of memory. In this work, we study what families of classifiers can be learned in bounded memory. To this end, we introduce a novel streaming-variant of enriched-query active learning along with a natural combinatorial parameter called lossless sample compression that is sufficient for learning not only with bounded memory, but in a query-optimal and computationally efficient manner as well. Finally, we give three fundamental examples of classifier families with small, easy to compute lossless compression schemes when given access to basic enriched queries: axis-aligned rectangles, decision trees, and halfspaces in two dimensions.