CS Paper Radar

Fermat ProbCover: Coverage-Based Active Learning on Fermat Distance Graphs

Gokul Bhusal, Delanna Do, Kevin Miller, Ekaterina Merkurjev, Stephan Wojtowytsch

cs.LG ·submitted 2026-11-10 01:47 UTC · v1

Abstract

Active learning aims to reduce annotation cost by selecting the most informative examples for labeling. In the low-budget regime, where uncertainty-based methods often fail, coverage-based active learning methods such as ProbCover have been shown to be effective. However, these methods typically rely on Euclidean distance, which may not adequately capture the underlying geometry of data. In this article, we propose PC-Fermat, a coverage-based active learning method that replaces Euclidean coverage neighborhoods with neighborhoods defined by a Fermat distance, i.e., a data-adaptive distance that reflects the underlying distribution of the data points. To facilitate computation, we construct a weighted Euclidean neighborhood graph and use a truncated shortest-path algorithm to compute the Fermat coverage graph. We also establish sufficient conditions under which this construction exactly preserves the Fermat coverage computed on the complete graph. Finally, we evaluate PC-Fermat on eight classification datasets across varying labeling budgets, with particular emphasis on the very low-budget regime. Our experimental results demonstrate that PC-Fermat outperforms several existing active learning methods on the majority of the datasets.

Closest papers

Nearest neighbours by meaning across the whole index.

Improving Category-Aware Active Domain Adaptation via Uncertainty-Guided Region Coverage

cs.CV ·2026-10-14 ·My Tra Nguyen Huynh, Viet Cuong Ta
top venuecode/data similarity 0.63
Abstract · Accepted at Machine Learning Journal through ACML Journal Track 2026

Active domain adaptation researches focus on alleviating the annotation cost, which comprises source data and target data labelling, as well as enhancing the performance of unsupervised domain adaptation. However, optimizing the adaptation model based on the average accuracy can lead to the drop in performance of some difficult categories. To overcome this issue, a point-wise selection strategy built upon the influence function can be used to improve domain adaptation performance. In our work, we first address the sensitive and redundant aspects of point-wise selection, which can lead to overfitting of the acquisition function. We thus introduce a region-based approach that ensures the improvement of the adaptation model by maximizing a positive manifold coverage. An uncertainty score is further introduced to the selection mechanism to learn a better decision boundary for the target domain. In comprehensive experiments, our proposed method surpasses the first category-aware active domain adaptation baseline as well as existing active domain adaptation methods across multiple domain adaptation benchmarks. Our implementation is available at: https://github.com/nhtm2702/WHO IS NEXT.

0.45

Active Learning of Robust Models

cs.LG cs.AI ·2026-11-06 ·Mizu Nishikawa-Toomey, Andreas Kirsch, Laurent Charlin, Dhanya Sridhar
similarity 0.63
Abstract

In many domains from species identification to cancer diagnosis, labelling data to train predictive models remains costly. In these settings, it is advantageous to intelligently select data points to label to achieve the maximum information gain, this is the motivation behind the study of active learning. In addition to the high costs of acquiring data in such domains, there is the added complexity of data distribution shifts that can occur between training and deployment. For example, the features of cancerous skin cells taken in one country may be different in another region of the world. These two challenges - efficient labelling of data, and learning models robust to distribution shifts have been studied separately but not together, even though these challenges often co-occur in real-life settings. We identify failure modes of standard active learning approaches when the distribution of data at deployment is different from the distribution in which the data is sampled for labelling. We propose a new strategy for efficiently learning classifiers that generalise under specific forms of distribution shift, namely subpopulation shift. Drawing on work in learning from heterogeneous data, we aim to train models that perform well across subpopulations of the data, through active learning. To handle this challenging setting, we exploit the fact that many datasets include metadata about data collection that can serve as a noisy proxy for each sample's underlying subpopulation. We demonstrate how to leverage these noisy labels during active learning selection, and demonstrate empirically that our approach improves classifier accuracy across subpopulations.

0.28

Diversity-Based Active Learning: An Evaluation of Metric Spaces for Active Learning Selection

cs.LG ·2026-08-24 ·Siddharth Chilamkur, Dorit S. Hochbaum
similarity 0.62
Abstract

With rapid advancement over the last few years, many different methods are now widely used for classification. However, training these models requires substantial labeled data. Active Learning is a potential solution to this problem. Pool-based active learning minimizes costs by querying only the most informative samples from an unlabeled dataset. Diversity-based approaches, on the other hand, attempt to select a representative subset of the data. There are many different objectives for determining the selection process, including exact K-center, exact K-median, and Greedy K-center. In this paper, we will focus on evaluating the performance of Greedy K-center across a variety of metric spaces: the raw feature space, a Linear Discriminant Analysis (LDA) space, and a model-derived probability space (with and without entropy-based weighting). Using Random Forest classifiers as a baseline evaluator, our empirical results on synthetic and real-world datasets demonstrate that mapping unlabeled instances into a predictive probability space and weighting the result by entropy often dominates the other options for active learning selection with Greedy K-center.

0.27

VC-Dimension and Generalization in Geometric Machine Learning with Applications to Active Learning

cs.LG stat.MLmath.DG ·2026-11-09 ·Gokul Bhusal, Delanna Do, Ekaterina Merkurjev, Kevin Miller, Stephan Wojtowytsch
theory similarity 0.60
Abstract · 19 pages + appendices

We compute the VC-dimension of metric ball classifiers in the model spaces of Riemannian geometry (Euclidean, spherical, hyperbolic) and present upper and lower bounds on the VC-dimension of metric balls in several other situations, including general normed vector spaces (potentially infinite VC-dimension), vector spaces with $\ell^p$-norms (VC-dimension grows at least linearly in the dimension, faster than Euclidean for $p=1$), flat tori, and general Riemannian manifolds (arbitrarily large VC-dimension after a conformal change). In several situations where the VC-dimension is large or even infinite, we prove generalization bounds under additional assumptions on the data distribution using covering arguments. Both in the VC-dimension and covering setting, we consider data on low-dimensional subsets of high-dimensional Euclidean spaces. As an application, we consider coverage-based algorithms in active learning.

0.29

On the Sample Complexity of Active Learning with Membership Queries

cs.LG stat.MLmath.ST ·2026-09-23 ·Ganghua Wang, Shaddin Dughmi
similarity 0.59
Abstract

This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, it has been observed that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular some hypothesis classes, such as two dimensional halfspaces, permit only polynomial error decay in the number of samples when the learner must draw its labels from the pool, yet become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its sample complexity for general hypothesis classes. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.

0.23

SPARCL: Spatially Adaptive Regional Coverage for Active Learning in Chest X-ray Analysis

cs.CV cs.LG ·2026-10-13 ·Juho Jung, Seongjae Kang, Mijoo Kim, Sungduk Cho, Yunkyoung Jun +2 more
similarity 0.58
Abstract · 10 pages, 7 figures

Pixel-level annotation for chest X-ray (CXR) lesion segmentation is expensive, making active learning (AL) essential. However, existing AL strategies fail to account for the spatial distribution of selected samples, resulting in inconsistent performance across focal (e.g., aortic calcification) and diffuse (e.g., nodules) pathologies. In this paper, we propose SPARCL (Spatially Adaptive Regional Coverage for Active Learning) to dynamically balance predictive uncertainty with cumulative spatial coverage. By employing a concave coverage function, SPARCL imposes diminishing returns on previously annotated regions, naturally directing the annotation budget toward under-labeled areas. Furthermore, an entropy gate reverts the algorithm to standard uncertainty sampling when spatial variation is absent. This coverage objective is monotone submodular, guaranteeing near-optimal greedy batch selection. To address how aggregate metrics like Dice obscure regional failures, we further introduce two metrics---Spatial Inconsistency (SI) and Performance Coverage (PC)---to quantify anatomical fairness across AL rounds. Evaluated on an in-house calcification cohort and public CXR benchmarks, SPARCL reaches 95% of fully supervised performance using only 24% of the data, compared to 29% for the best baseline. Ultimately, SPARCL ensures robust spatial reliability, surfacing regional gains that aggregate metrics miss.

0.25

k-Volume: a Unified Active Learning Strategy

cs.LG stat.ML ·2026-11-06 ·Eliot Tron, Alain Celisse, Christophe Denis, Alice Le Brigant
similarity 0.58
Abstract

In the classification context where revealing the label of a sample is costly, we propose a new Active Learning (AL) strategy named k-Volume (kVol). It randomly selects a sample to be labeled according to the volume of the smallest ball containing its k nearest neighbors. kVol is highly versatile: it can be applied either in the input space or in the output space, and it enjoys the desirable properties of the three main families of AL strategies: density, diversity, and (when performed in the output space) uncertainty. From a theoretical perspective, we establish that kVol is asymptotically equivalent to uniform sampling over the support of the (input or output) data distribution. Based on experiments on various synthetic and real-life tabular datasets and images, we observe that kVol is surprisingly stable: whatever the classifier or the experimental setup, it still lies among the best AL strategies unlike other competitors that fail dramatically. In particular, kVol outperforms state-of-the-art competitors such as CoreSet, TypiClust or Uncertainty on several real-life datasets, at a low computational cost.

0.19

ALF: An Active Learning Framework for Scientific Discovery

cs.LG ·2026-09-25 ·Shikha Surana, Alex Hawkins-Hooker, Olivia Gallup, Christoph Brunken, Jules Tilly +1 more
code/data similarity 0.58
Abstract · 14 pages, 7 figures

Machine learning for scientific discovery is almost systematically data bound. Producing relevant high quality data, under budget constraints, is amongst the most promising ways to advance the field. Active learning (AL) offers promise wherever labelling requires expensive experiment, measurement, or simulation. Most existing tools cover only part of the data acquisition loop, and typically focus on either offline benchmarking or online deployment, but not both. We present ALF, a modular AL Framework that runs the full data acquisition loop via five modular components. One clear API for both settings: offline, against an existing dataset for controlled and reproducible experimentation; and online, against an oracle for acquiring new candidates in real-world deployments. ALF is open-source and available at https://github.com/instadeepai/alf.

0.45