On the Sample Complexity of Active Learning with Membership Queries
Abstract
This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, it has been observed that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular some hypothesis classes, such as two dimensional halfspaces, permit only polynomial error decay in the number of samples when the learner must draw its labels from the pool, yet become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its sample complexity for general hypothesis classes. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.
Related
- Beyond Overparameterization: Provable Learning of Input-Convex Multi-Layer Polynomial Networks with Active Queries
- On the sample complexity of the active subspace method
- Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model
- Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity
- Sample Complexity of Equivariant Reinforcement Learning
BibTeX
@misc{wang2026sample,
title = {{On the Sample Complexity of Active Learning with Membership Queries}},
author = {Ganghua Wang and Shaddin Dughmi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.27241},
eprint = {2609.27241},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27241},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Sample Complexity of Active Learning with Membership Queries
AU - Ganghua Wang
AU - Shaddin Dughmi
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2609.27241
UR - https://arxiv.org/abs/2609.27241
AB - This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, it has been observed that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular some hypothesis classes, such as two dimensional halfspaces, permit only polynomial error decay in the number of samples when the learner must draw its labels from the pool, yet become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its sample complexity for general hypothesis classes. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.
ER -