# Generalized Coverage for More Robust Low-Budget Active Learning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 61 references that are in the map.
- First posted on arXiv 16 Jul 2024.

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

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Emerging Properties in Self-Supervised Vision Transformers](https://mlsanity.com/paper/2104.14294/) (2021)
- [Class-Balanced Loss Based on Effective Number of Samples](https://mlsanity.com/paper/1901.05555/) (2019)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds](https://mlsanity.com/paper/1906.03671/) (2019)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [SCAN: Learning to Classify Images without Labels](https://mlsanity.com/paper/2005.12320/) (2020)
- [Active Learning on a Budget: Opposite Strategies Suit High and Low Budgets](https://mlsanity.com/paper/2202.02794/) (2022)
- [Active Learning Through a Covering Lens](https://mlsanity.com/paper/2205.11320/) (2022)
- [Active Learning by Feature Mixing](https://mlsanity.com/paper/2203.07034/) (2022)
- [Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms](https://mlsanity.com/paper/1810.05691/) (2018)
- [Stein Points](https://mlsanity.com/paper/1803.10161/) (2018)
- [Fast and Eager k-Medoids Clustering: O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms](https://mlsanity.com/paper/2008.05171/) (2020)
- [Active Finetuning: Exploiting Annotation Budget in the Pretraining-Finetuning Paradigm](https://mlsanity.com/paper/2303.14382/) (2023)
- [Low Budget Active Learning via Wasserstein Distance: An Integer Programming Approach](https://mlsanity.com/paper/2106.02968/) (2021)
- [All you need are a few pixels: semantic segmentation with PixelPick](https://mlsanity.com/paper/2104.06394/) (2021)
- [Making Look-Ahead Active Learning Strategies Feasible with Neural Tangent Kernels](https://mlsanity.com/paper/2206.12569/) (2022)
- [Active and Continuous Exploration with Deep Neural Networks and Expected Model Output Changes](https://mlsanity.com/paper/1612.06129/) (2016)
- [How to Select Which Active Learning Strategy is Best Suited for Your Specific Problem and Budget](https://mlsanity.com/paper/2306.03543/) (2023)
- [On Data Efficiency of Meta-learning](https://mlsanity.com/paper/2102.00127/) (2021)
- [Active Distance-Based Clustering using K-medoids](https://mlsanity.com/paper/1512.03953/) (2015)
- [Exploring Active Learning in Meta-Learning: Enhancing Context Set Labeling](https://mlsanity.com/paper/2311.02879/) (2023)

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

- [Uncertainty Herding: One Active Learning Method for All Label Budgets](https://mlsanity.com/paper/2412.20644/) (2024)
- [Active Learning with a Noisy Annotator](https://mlsanity.com/paper/2504.04506/) (2025)
- [A2LC: Active and Automated Label Correction for Semantic Segmentation](https://mlsanity.com/paper/2506.11599/) (2025)
- [Cleaning the Pool: Progressive Filtering of Unlabeled Pools in Deep Active Learning](https://mlsanity.com/paper/2511.22344/) (2025)
- [Combining Discrepancy-Confusion Uncertainty and Calibration Diversity for Active Fine-Grained Image Classification](https://mlsanity.com/paper/2509.24181/) (2025)
- [Diffusion-Driven Two-Stage Active Learning for Low-Budget Semantic Segmentation](https://mlsanity.com/paper/2510.22229/) (2025)
- [Federated Active Learning Under Extreme Non-IID and Global Class Imbalance](https://mlsanity.com/paper/2603.10341/) (2026)
- [Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers](https://mlsanity.com/paper/2604.08336/) (2026)
- [Active Learning for Cascaded Object Detection: Balancing Coverage and Uncertainty in Table Extraction Pipelines](https://mlsanity.com/paper/2607.00747/) (2026)
- [Group-invariant Coresets for Data-efficient Active Learning](https://mlsanity.com/paper/2607.01089/) (2026)
- [One Knob to Rule Them All: A Unified Optimal Transport View of Cold-Start Active Learning](https://mlsanity.com/paper/2608.03249/) (2026)
- [SUGFW+: An Uncertainty-guided Feature Weighting Framework for Cold Start Active Adaptation of SAM in Medical Image Segmentation](https://mlsanity.com/paper/2608.16110/) (2026)
- [Probing Association Instability with Track-State Perturbations for Clip-Level Active Learning in Query-Propagation Multi-Object Tracking](https://mlsanity.com/paper/2608.17224/) (2026)
- [Coordination on a Budget: Federated Active Learning with Few Labels](https://mlsanity.com/paper/2608.18634/) (2026)
- [Low-Budget Active Learning through Entropic Optimal Transport](https://mlsanity.com/paper/2610.01199/) (2026)
- [Improving Category-Aware Active Domain Adaptation via Uncertainty-Guided Region Coverage](https://mlsanity.com/paper/2610.19803/) (2026)

## Abstract (arXiv)

The ProbCover method of Yehuda et al. is a well-motivated algorithm for active learning in low-budget regimes, which attempts to "cover" the data distribution with balls of a given radius at selected data points. We demonstrate, however, that the performance of this algorithm is extremely sensitive to the choice of this radius hyper-parameter, and that tuning it is quite difficult, with the original heuristic frequently failing. We thus introduce (and theoretically motivate) a generalized notion of "coverage," including ProbCover's objective as a special case, but also allowing smoother notions that are far more robust to hyper-parameter choice. We propose an efficient greedy method to optimize this coverage, generalizing ProbCover's algorithm; due to its close connection to kernel herding, we call it "MaxHerding." The objective can also be optimized non-greedily through a variant of k-medoids, clarifying the relationship to other low-budget active learning methods. In comprehensive experiments, MaxHerding surpasses existing active learning methods across multiple low-budget image classification benchmarks, and does so with less computational cost than most competitive methods.