# Active Learning for Binary Classification with Abstention

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2019.

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

- [Online Decision Mediation](https://mlsanity.com/paper/2310.18601/) (2023)
- [Beyond Labels: Information-Efficient Human-in-the-Loop Learning using Ranking and Selection Queries](https://mlsanity.com/paper/2602.15738/) (2026)

## Abstract (arXiv)

We construct and analyze active learning algorithms for the problem of binary classification with abstention. We consider three abstention settings: fixed-cost and two variants of bounded-rate abstention, and for each of them propose an active learning algorithm. All the proposed algorithms can work in the most commonly used active learning models, i.e., membership-query, pool-based, and stream-based sampling. We obtain upper-bounds on the excess risk of our algorithms in a general non-parametric framework and establish their minimax near-optimality by deriving matching lower-bounds. Since our algorithms rely on the knowledge of some smoothness parameters of the regression function, we then describe a new strategy to adapt to these unknown parameters in a data-driven manner. Since the worst case computational complexity of our proposed algorithms increases exponentially with the dimension of the input space, we conclude the paper with a computationally efficient variant of our algorithm whose computational complexity has a polynomial dependence over a smaller but rich class of learning problems.