Research map / Label-efficient and robust learning / Recognition and long-tail
Provably Neural Active Learning Succeeds via Prioritizing Perplexing Samples
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.
Provides a feature-learning theory showing that uncertainty-based and diversity-based neural active learning both prioritize "perplexing" samples containing yet-to-be-learned weak/rare features, yielding benign overfitting with far fewer labels than random sampling.
Problem
Lack of theoretical understanding of why the two dominant query criteria of neural active learning (uncertainty-based and diversity-based) work, and whether they are intrinsically connected.
Approach
Analyzes 2-layer ReLU CNNs trained by gradient descent on a feature-noise data model with strong/common and weak/rare features; shows Least-confidence uncertainty sampling and max-feature-distance diversity sampling both select samples carrying yet-to-be-learned (weak, rare) features, which explains their small test error and lower label complexity versus random sampling.
Key results
- On synthetic data (d=2000, p=0.2, n0=10, n*=30), uncertainty and diversity sampling reach test performance comparable to the full-trained CNN, while random sampling keeps poor weak-feature learning and test error.
- Theory: NAL test error is bounded by exp(-Theta(n~ ||mu_l||^4/(sigma_p^4 d))), whereas random sampling stays at Theta(1) >= 0.12 p*.
- Label complexity: NAL needs Omega(sigma_p^2 d ||mu_2||^-4) labels versus Omega(p^-1 sigma_p^2 d ||mu_2||^-4) for passive learning, a Theta(1/p) saving.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use uncertainty sampling to prioritize low-confidence samples instead of random sampling | Two-layer ReLU CNN active learning · Synthetic feature-noise data | test error | Helped |
| Use diversity sampling to prioritize samples far from labeled data in feature space instead of random sampling | Two-layer ReLU CNN active learning · Synthetic feature-noise data | test error | Helped |
| Prioritize samples with yet-to-be-learned weak features through uncertainty sampling | Uncertainty Sampling · Synthetic feature-noise data | weak-feature learning | Helped |
| Prioritize samples with yet-to-be-learned weak features through diversity sampling | Diversity Sampling · Synthetic feature-noise data | weak-feature learning | Helped |
| Use uncertainty or diversity sampling rather than random sampling | Neural active learning · Synthetic feature-noise data | label complexity | Helped |
| Use uncertainty or diversity sampling rather than random sampling | Neural active learning · XOR data | test error | Helped |
Surprising findings
- Uncertainty and diversity sampling can outperform the fully-trained CNN in the experiments, attributed to a large learning rate emphasizing weak/rare features.
- Passive learning test error grows with p*, exploding in out-of-distribution settings where p* > 0.5 > p.
Limitations
- Analysis restricted to single-round querying with 2-layer ReLU CNN and synthetic data model.
- Experiments are small-scale synthetic simulations rather than real datasets.
- Behavior when feature learning disparity is weak (criteria preference) is only discussed informally.
Experimental setup
Datasets: synthetic feature-noise data model
Benchmarks: synthetic feature-noise data
Metrics: 0-1 test error test loss test accuracy feature learning coefficient gamma noise memorization coefficient rho
Baselines: Random Sampling fully-trained ReLU CNN
Builds on: feature learning theory of CNNs (multi-view data model) signal-noise decomposition benign overfitting analysis
Closest papers by meaning
- Towards Robust and Reproducible Active Learning Using Neural Networks (CVPR 2022 · similarity 0.89)
- Neural Active Learning Beyond Bandits (ICLR 2024 · similarity 0.87)
- Deep Active Learning with Noise Stability (AAAI 2024 · similarity 0.86)
- Transductive Active Learning: Theory and Applications (NeurIPS 2024 · similarity 0.86)
- NEAR: A Training-Free Pre-Estimator of Machine Learning Model Performance (ICLR 2025 · similarity 0.85)
- Active Classification with Few Queries under Misspecification (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.