SOURCE-LINKED INTELLIGENCE

On the Sample Complexity of Active Learning with Membership Queries

arXiv · AI, language, vision and robotics · article · Sep 23, 2026 · UTC

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, we find that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular, some hypothesis classes that are inherently slow to learn in the pool-based setting, achieving only polynomial error decay in the number of samples, become exponentially learnable once synthesized queries are allowed. This striking ga

Read original source ↗ Open in workspace

recordType

paper

region

Global