# Active Covering

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 49 references that are in the map.
- First posted on arXiv 4 Jun 2021.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep Learning](https://mlsanity.com/paper/1803.04765/) (2018)
- [Accelerating Very Deep Convolutional Networks for Classification and Detection](https://mlsanity.com/paper/1505.06798/) (2015)
- [Deep k-NN for Noisy Labels](https://mlsanity.com/paper/2004.12289/) (2020)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Analysis of KNN Density Estimation](https://mlsanity.com/paper/2010.00438/) (2020)
- [Density Level Set Estimation on Manifolds with DBSCAN](https://mlsanity.com/paper/1703.03503/) (2017)
- [A New Perspective on Pool-Based Active Classification and False-Discovery Control](https://mlsanity.com/paper/2008.06555/) (2020)
- [Locally Adaptive Label Smoothing for Predictive Churn](https://mlsanity.com/paper/2102.05140/) (2021)
- [Learning the Truth From Only One Side of the Story](https://mlsanity.com/paper/2006.04858/) (2020)

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

- [Amortized nonmyopic active search via deep imitation learning](https://mlsanity.com/paper/2405.15031/) (2024)

## Abstract (arXiv)

We analyze the problem of active covering, where the learner is given an unlabeled dataset and can sequentially label query examples. The objective is to label query all of the positive examples in the fewest number of total label queries. We show under standard non-parametric assumptions that a classical support estimator can be repurposed as an offline algorithm attaining an excess query cost of widetildeTheta(nD/(D+1)) compared to the optimal learner, where n is the number of datapoints and D is the dimension. We then provide a simple active learning method that attains an improved excess query cost of widetildeO(n(D-1)/D). Furthermore, the proposed algorithms only require access to the positive labeled examples, which in certain settings provides additional computational and privacy benefits. Finally, we show that the active learning method consistently outperforms offline methods as well as a variety of baselines on a wide range of benchmark image-based datasets.