# Neural Active Learning with Performance Guarantees

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 46 references that are in the map.
- First posted on arXiv 6 Jun 2021.

## Builds on (most cited first, 23 of 23)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds](https://mlsanity.com/paper/1906.03671/) (2019)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning](https://mlsanity.com/paper/1906.08158/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [Towards Understanding the Spectral Bias of Deep Learning](https://mlsanity.com/paper/1912.01198/) (2019)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Diverse mini-batch Active Learning](https://mlsanity.com/paper/1901.05954/) (2019)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Regret Bound Balancing and Elimination for Model Selection in Bandits and RL](https://mlsanity.com/paper/2012.13045/) (2020)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima](https://mlsanity.com/paper/1712.00779/) (2017)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [Deep Ensemble Bayesian Active Learning : Addressing the Mode Collapse issue in Monte Carlo dropout via Ensembles](https://mlsanity.com/paper/1811.03897/) (2018)
- [Adaptivity to Noise Parameters in Nonparametric Active Learning](https://mlsanity.com/paper/1703.05841/) (2017)
- [Active Nearest-Neighbor Learning in Metric Spaces](https://mlsanity.com/paper/1605.06792/) (2016)
- [MaxiMin Active Learning in Overparameterized Model Classes}](https://mlsanity.com/paper/1905.12782/) (2019)
- [Nonparametric adaptive active learning under local smoothness condition](https://mlsanity.com/paper/2102.11077/) (2021)

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

- [A Framework and Benchmark for Deep Batch Active Learning for Regression](https://mlsanity.com/paper/2203.09410/) (2022)
- [Deep Active Learning by Leveraging Training Dynamics](https://mlsanity.com/paper/2110.08611/) (2021)
- [PINNACLE: PINN Adaptive ColLocation and Experimental points selection](https://mlsanity.com/paper/2404.07662/) (2024)
- [Sample-Then-Optimize Batch Neural Thompson Sampling](https://mlsanity.com/paper/2210.06850/) (2022)
- [Fast Rates in Pool-Based Batch Active Learning](https://mlsanity.com/paper/2202.05448/) (2022)
- [PageRank Bandits for Link Prediction](https://mlsanity.com/paper/2411.01410/) (2024)
- [Active Learning with Neural Networks: Insights from Nonparametric Statistics](https://mlsanity.com/paper/2210.08367/) (2022)
- [Norm-Agnostic Linear Bandits](https://mlsanity.com/paper/2205.01257/) (2022)
- [Improved Algorithms for Neural Active Learning](https://mlsanity.com/paper/2210.00423/) (2022)
- [Contextual Rollout Bandits for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2602.08499/) (2026)
- [Neural Active Learning Beyond Bandits](https://mlsanity.com/paper/2404.12522/) (2024)
- [Neural Exploitation and Exploration of Contextual Bandits](https://mlsanity.com/paper/2305.03784/) (2023)
- [Meta Clustering of Neural Bandits](https://mlsanity.com/paper/2408.05586/) (2024)
- [Active Learning for Deep Neural Networks on Edge Devices](https://mlsanity.com/paper/2106.10836/) (2021)
- [Training-Free Neural Active Learning with Initialization-Robustness Guarantees](https://mlsanity.com/paper/2306.04454/) (2023)
- [Provably Neural Active Learning Succeeds via Prioritizing Perplexing Samples](https://mlsanity.com/paper/2406.03944/) (2024)
- [Active Cost-aware Labeling of Streaming Data](https://mlsanity.com/paper/2304.06808/) (2023)
- [Few Clicks Suffice: Active Test-Time Adaptation for Semantic Segmentation](https://mlsanity.com/paper/2312.01835/) (2023)
- [Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach](https://mlsanity.com/paper/2310.15411/) (2023)
- [Neural Active Learning Meets the Partial Monitoring Framework](https://mlsanity.com/paper/2405.08921/) (2024)
- [Constrained Online Decision-Making: A Unified Framework](https://mlsanity.com/paper/2505.07101/) (2025)
- [Empirical Bound Information-Directed Sampling for Norm-Agnostic Bandits](https://mlsanity.com/paper/2503.05098/) (2025)

## Abstract (arXiv)

We investigate the problem of active learning in the streaming setting in non-parametric regimes, where the labels are stochastically generated from a class of functions on which we make no assumptions whatsoever. We rely on recently proposed Neural Tangent Kernel (NTK) approximation tools to construct a suitable neural embedding that determines the feature space the algorithm operates on and the learned model computed atop. Since the shape of the label requesting threshold is tightly related to the complexity of the function to be learned, which is a-priori unknown, we also derive a version of the algorithm which is agnostic to any prior knowledge. This algorithm relies on a regret balancing scheme to solve the resulting online model selection problem, and is computationally efficient. We prove joint guarantees on the cumulative regret and number of requested labels which depend on the complexity of the labeling function at hand. In the linear case, these guarantees recover known minimax results of the generalization error as a function of the label complexity in a standard statistical learning setting.