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

Gokul Bhusal, Delanna Do, Kevin Miller, Ekaterina Merkurjev, Stephan WojtowytscharXiv 2026 · arXiv

TL;DR

PC-Fermat is a new active learning method designed for the "low-budget" regime, where you only have enough resources to label a handful of data points. By replacing standard Euclidean distance with Fermat distance—a metric that follows the high-density "curves" of your data—it selects more representative samples and significantly outperforms traditional methods on complex, high-dimensional datasets.

What Problem Does This Paper Address?

Machine learning thrives on labeled data, but labeling is expensive, slow, and sometimes ethically sensitive. Active Learning (AL) tries to solve this by picking only the most "informative" samples for humans to label.

In the low-budget regime (e.g., labeling only 10-20 samples for a dataset of thousands), standard AL strategies often fail:

  1. Uncertainty-based methods (picking samples the model is "confused" about) struggle because, with so few labels, the model hasn't even learned a basic decision boundary yet.
  2. Representation-based methods (like ProbCover) try to "cover" the data space with a few points. However, they usually rely on Euclidean distance. In high-dimensional spaces, Euclidean distance is "blind" to the underlying structure; it might think two points are close just because they are spatially near, even if they belong to completely different clusters separated by a gap.

Methods

The authors propose PC-Fermat, which adapts the ProbCover algorithm by swapping Euclidean distance for Fermat distance.

The Fermat Advantage

Fermat distance is a "density-weighted" path metric. Instead of a straight line, it calculates the distance between two points by finding a path through the densest regions of the data.

  • The Power Parameter ($p$): By raising edge weights to a power $p \ge 1$, the metric heavily penalizes "jumps" across low-density gaps.
  • Manifold Awareness: As shown in the figure below, while a Euclidean path cuts straight across a gap, a Fermat path follows the actual shape (manifold) of the data.
Fig. 1: Fermat paths between two points at opposite ends of a moon- shaped dataset for different p values.

The Algorithm

  1. Graph Construction: Build a weighted $\epsilon$-neighborhood graph where edges are Euclidean distances raised to the power $p$.
  2. Fermat Coverage: Use a truncated version of Dijkstra’s algorithm to find "Fermat balls"—sets of points reachable within a certain Fermat distance $r$.
  3. Greedy Selection: Iteratively pick the unlabeled point that "covers" the most currently uncovered points in the Fermat coverage graph.
  4. Classification: Once the budget is spent, a simple 1-Nearest Neighbor (1-NN) classifier is trained on the labeled set.

Datasets

The authors evaluated PC-Fermat on eight diverse classification benchmarks:

  • Image Datasets: COIL-20 (objects on turntables), MNIST & USPS (handwritten digits), Fashion-MNIST (clothing items).
  • Tabular/Sensor Datasets: Opt-Digits (digits), Landsat (satellite multi-spectral data), Jasper Ridge (hyperspectral images), Pendigits (pen-based digits).
  • Embeddings: For high-dimensional images like MNIST, they used Variational Autoencoders (VAEs) to learn lower-dimensional latent representations before applying the algorithm.

Key Insights and Ideas

  • Geometry Matters: Euclidean balls are rigid spheres. Fermat balls are "stretchy"—they expand along dense clusters and contract at boundaries. This ensures that a selected representative point actually represents its own cluster, rather than accidentally "covering" points from a neighboring class across a small gap.
Comparison of Euclidean vs. Fermat balls. The Fermat ball (right) stays within the dense region of the lower moon, whereas the Euclidean ball (left) spills over into the upper moon.
  • Efficiency via Truncation: Computing all-pairs shortest paths is expensive ($O(n^3)$). By using a distance cutoff $r$ in Dijkstra’s algorithm, the authors make the computation feasible for larger datasets.
  • Exploration vs. Exploitation: The paper reinforces that in the early stages of learning (low budget), exploration (covering the whole manifold) is far more valuable than exploitation (refining a specific boundary).

Key Results

PC-Fermat consistently outperformed the Euclidean version of ProbCover, Random sampling, and other popular methods like KMeans++ and TypiClust.

  • Accuracy Boost: On datasets like Landsat and Fashion-MNIST, PC-Fermat showed a clear lead in accuracy, especially when the number of labeled points was very small (e.g., < 50 labels).
  • Robustness: While uncertainty-based "Margin" sampling occasionally performed well on very clean, well-separated clusters (like COIL-20), PC-Fermat was the most consistently competitive algorithm across the entire suite of datasets.

Limitations and Future Work

  • Computational Overhead: PC-Fermat is more computationally intensive than random sampling or KMeans++ because it requires graph construction and shortest-path calculations.
  • Hyperparameter Sensitivity: The performance depends on choosing a good radius $r$ and power $p$. The authors suggest coupling $r = \epsilon^p$ to simplify this, but some tuning is still required.
  • Scalability: While truncated Dijkstra helps, applying this to millions of points would likely require further optimizations or approximate nearest neighbor search techniques.
  • Future Directions: The authors suggest exploring how Fermat distances could be integrated into more complex deep learning architectures beyond the 1-NN classifier used here.

Summary updated

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.
BibTeX
@misc{bhusal2026fermat,
  author = {Gokul Bhusal and Delanna Do and Kevin Miller and Ekaterina Merkurjev and Stephan Wojtowytsch},
  title = {{Fermat ProbCover: Coverage-Based Active Learning on Fermat Distance Graphs}},
  year = {2026},
  eprint = {2611.13448},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13448},
}
Figure