Research map / Learning theory and algorithms / Sample complexity
Universal Rates for Active Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a complete characterization of optimal universal learning rates for non-adaptive, label-query-only active learning of binary classifiers, yielding a four-case tetrachotomy based on Littlestone, star, and VCL trees.
Problem
Determining the optimal distribution-dependent (universal) learning rates achievable by active learners that use only label queries and a fixed number of unlabeled points, which was left open by Balcan et al. (2010).
Approach
Shifts from uniform to universal rates for active learning and identifies a new combinatorial measure, the star tree, which separates exponential rates from sublinear rates; introduces algorithms for partial concept classes with finite star number and for sublinear rates via partial VCL-game classes.
Key results
- Complete tetrachotomy for universal active learning rates: arbitrarily fast, exponential e^{-n}, o(1/n) but arbitrarily close to 1/n, or arbitrarily slow, determined by infinite Littlestone, star, and VCL trees.
- Classes with infinite Littlestone tree but no infinite star tree (e.g., intervals on R) achieve exponential universal rates, in contrast to uniform rate 1/n.
- Halfspaces on R^d have an infinite star tree but no infinite VCL tree, so they get sublinear rates but not exponential ones.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a concept class with no infinite Littlestone tree | Active learning · Universal rates | misclassification error rate | Helped |
| Use a concept class with an infinite Littlestone tree but no infinite star tree | Active learning · Universal rates | misclassification error rate | Helped |
| Use a concept class with an infinite star tree but no infinite VCL tree | Active learning · Universal rates | misclassification error rate | Mixed |
| Use a concept class with an infinite VCL tree | Active learning · Universal rates | misclassification error rate | Hurt |
Surprising findings
- Interval classifiers have uniform active rate 1/n but achieve exponential universal rates, showing a sharp gap between uniform and universal active learning.
Limitations
- Assumes the learner does not know the marginal distribution P_X; the case where it is known is left open.
- Algorithms are non-constructive in parts and rely on unlabeled sample sizes that are unbounded functions of n.
Experimental setup
Baselines: Bousquet et al. (2021) passive universal learner Hanneke et al. (2022) general interactive learner
Builds on: Bousquet et al. (2021) universal rates Hanneke et al. (2022) interactive learning Hanneke and Yang (2015) star number Hanneke (2012) active learning sublinear rates Alon et al. (2021) partial concept classes
Closest papers by meaning
- Universal Rates for Interactive Learning (NeurIPS 2022 · similarity 0.89)
- Active Learning From Positive and Unlabeled Examples (NeurIPS 2026 · similarity 0.87)
- Universal Rates of Empirical Risk Minimization (NeurIPS 2024 · similarity 0.86)
- Active Classification with Few Queries under Misspecification (NeurIPS 2024 · similarity 0.86)
- Fast Co-Training under Weak Dependence via Stream-Based Active Learning (ICML 2024 · similarity 0.85)
- A Cross-Domain Benchmark for Active Learning (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.