Active Covering
This addresses the challenge of efficient data labeling in machine learning, particularly for applications like image classification, though it is incremental as it builds on existing support estimation methods.
The paper tackles the problem of active covering, where the goal is to label all positive examples in an unlabeled dataset with minimal label queries, showing that a simple active learning method achieves an improved excess query cost of ̃O(n^{(D-1)/D}) compared to an offline method's ̃Θ(n^{D/(D+1)}), and outperforms baselines on benchmark image datasets.
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 $\widetildeΘ(n^{D/(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 $\widetilde{O}(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.