Active learning with synthetic queries can speed up learning exponentially
On the Sample Complexity of Active Learning with Membership Queries
Machine Learning
Summary
Active learning is a way for computers to learn by asking questions. Usually, the computer picks questions only from a fixed set of unlabeled examples, but this paper studies what happens if it can create any question it wants. The authors show that with this freedom, the computer can learn some things much faster—changing from slow, gradual learning to very quick learning. This means that being able to make up questions changes the whole way learning works and needs new ways to understand it.
What this means in practice
- •For machine learning engineers: Design learning algorithms that use synthetic queries to reduce training samples for some models.
- •For data labeling teams: Assess when creating new queries can speed up labeling efforts compared to only labeling from existing data pools.
A theory result. No direct application yet.
Authors
Ganghua Wang, Shaddin Dughmi
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, 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 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 complexity. 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.