# Efficient and Parsimonious Agnostic Active Learning

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2015.

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

- [Active Fairness Auditing](https://mlsanity.com/paper/2206.08450/) (2022)
- [Efficient Active Learning with Abstention](https://mlsanity.com/paper/2204.00043/) (2022)
- [Streaming Active Learning with Deep Neural Networks](https://mlsanity.com/paper/2303.02535/) (2023)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (2022)
- [Improved Algorithms for Agnostic Pool-based Active Classification](https://mlsanity.com/paper/2105.06499/) (2021)
- [Active Learning with Neural Networks: Insights from Nonparametric Statistics](https://mlsanity.com/paper/2210.08367/) (2022)
- [Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation](https://mlsanity.com/paper/2312.09196/) (2023)
- [AHA: Human-Assisted Out-of-Distribution Generalization and Detection](https://mlsanity.com/paper/2410.08000/) (2024)
- [Selective Sampling for Online Best-arm Identification](https://mlsanity.com/paper/2110.14864/) (2021)
- [Multi-task Representation Learning for Pure Exploration in Linear Bandits](https://mlsanity.com/paper/2302.04441/) (2023)
- [Data-Efficient Learning via Minimizing Hyperspherical Energy](https://mlsanity.com/paper/2206.15204/) (2022)
- [Improved Adaptive Algorithm for Scalable Active Learning with Weak Labeler](https://mlsanity.com/paper/2211.02233/) (2022)
- [Corruption Robust Active Learning](https://mlsanity.com/paper/2106.11220/) (2021)
- [Learning from Snapshots of Discrete and Continuous Data Streams](https://mlsanity.com/paper/2412.06079/) (2024)
- [Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach](https://mlsanity.com/paper/2310.15411/) (2023)
- [Towards Fundamental Limits for Active Multi-distribution Learning](https://mlsanity.com/paper/2506.17607/) (2025)
- [Deep Active Learning with Structured Neural Depth Search](https://mlsanity.com/paper/2306.02808/) (2023)

## Abstract (arXiv)

We develop a new active learning algorithm for the streaming setting satisfying three important properties: 1) It provably works for any classifier representation and classification problem including those with severe noise. 2) It is efficiently implementable with an ERM oracle. 3) It is more aggressive than all previous approaches satisfying 1 and 2. To do this we create an algorithm based on a newly defined optimization problem and analyze it. We also conduct the first experimental analysis of all efficient agnostic active learning algorithms, evaluating their strengths and weaknesses in different settings.