# Provably Neural Active Learning Succeeds via Prioritizing Perplexing Samples

arXiv: https://arxiv.org/abs/2406.03944 · HTML: https://mlsanity.com/paper/2406.03944/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 54 of its 104 references that are in the map.
- First posted on arXiv 6 Jun 2024.

## Builds on (most cited first, 30 of 54)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Deep Bayesian Active Learning with Image Data](https://mlsanity.com/paper/1703.02910/) (2017)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds](https://mlsanity.com/paper/1906.03671/) (2019)
- [Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning](https://mlsanity.com/paper/2012.09816/) (2020)
- [Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit](https://mlsanity.com/paper/1902.06015/) (2019)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [Trainability and Accuracy of Neural Networks: An Interacting Particle System Approach](https://mlsanity.com/paper/1805.00915/) (2018)
- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [Discriminative Active Learning](https://mlsanity.com/paper/1907.06347/) (2019)
- [Deep Active Learning: Unified and Principled Method for Query and Training](https://mlsanity.com/paper/1911.09162/) (2019)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Diverse mini-batch Active Learning](https://mlsanity.com/paper/1901.05954/) (2019)
- [A Comparative Survey of Deep Active Learning](https://mlsanity.com/paper/2203.13450/) (2022)
- [How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?](https://mlsanity.com/paper/1911.12360/) (2019)
- [White-Box Transformers via Sparse Rate Reduction](https://mlsanity.com/paper/2306.01129/) (2023)
- [On the Origins of Linear Representations in Large Language Models](https://mlsanity.com/paper/2403.03867/) (2024)
- [A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity](https://mlsanity.com/paper/2302.06015/) (2023)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1902.01384/) (2019)
- [Convex Analysis of the Mean Field Langevin Dynamics](https://mlsanity.com/paper/2201.10469/) (2022)
- [Stochastic Particle Gradient Descent for Infinite Ensembles](https://mlsanity.com/paper/1712.05438/) (2017)
- [Towards Understanding Mixture of Experts in Deep Learning](https://mlsanity.com/paper/2208.02813/) (2022)
- [JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attention](https://mlsanity.com/paper/2310.00535/) (2023)
- [Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization](https://mlsanity.com/paper/2108.11371/) (2021)
- [Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscape](https://mlsanity.com/paper/2402.01258/) (2024)
- [Robust Learning with Progressive Data Expansion Against Spurious Correlation](https://mlsanity.com/paper/2306.04949/) (2023)
- [Active Learning for Convolutional Neural Networks: A Core-Set Approach](https://mlsanity.com/paper/1708.00489/) (2017)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)

## Built on by (most cited first, 5 of 5)

- [When is Task Vector Provably Effective for Model Editing? A Generalization Analysis of Nonlinear Transformers](https://mlsanity.com/paper/2504.10957/) (2025)
- [DPRM: A Plug-in Doob h transform-induced Token-Ordering Module for Discrete Diffusion Models](https://mlsanity.com/paper/2604.24357/) (2026)
- [Efficient Quantization of Mixture-of-Experts with Theoretical Generalization Guarantees](https://mlsanity.com/paper/2604.06515/) (2026)
- [MelissaDL x Breed: Towards Data-Efficient On-line Supervised Training of Multi-parametric Surrogates with Active Learning](https://mlsanity.com/paper/2410.05860/) (2024)
- [Robust Heterogeneous Analog-Digital Computing for Mixture-of-Experts Models with Theoretical Generalization Guarantees](https://mlsanity.com/paper/2603.02633/) (2026)

## Abstract (arXiv)

Neural Network-based active learning (NAL) is a cost-effective data selection technique that utilizes neural networks to select and train on a small subset of samples. While existing work successfully develops various effective or theory-justified NAL algorithms, the understanding of the two commonly used query criteria of NAL: uncertainty-based and diversity-based, remains in its infancy. In this work, we try to move one step forward by offering a unified explanation for the success of both query criteria-based NAL from a feature learning view. Specifically, we consider a feature-noise data model comprising easy-to-learn or hard-to-learn features disrupted by noise, and conduct analysis over 2-layer NN-based NALs in the pool-based scenario. We provably show that both uncertainty-based and diversity-based NAL are inherently amenable to one and the same principle, i.e., striving to prioritize samples that contain yet-to-be-learned features. We further prove that this shared principle is the key to their success-achieve small test error within a small labeled set. Contrastingly, the strategy-free passive learning exhibits a large test error due to the inadequate learning of yet-to-be-learned features, necessitating resort to a significantly larger label complexity for a sufficient test error reduction. Experimental results validate our findings.