PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-Budget Active Learning through Entropic Optimal Transport

Rim Hajal, Mathieu Besançon, Jérôme Malick

arXiv:2610.01199v1cs.LGmath.OC

TL;DR

Low-budget active learning must select a small coreset despite the combinatorial difficulty of discrete selection. The paper uses the Sinkhorn divergence with a Frank-Wolfe-initialized swap search, and reports superior low-budget accuracy, especially at very small budgets.

  • Problem

    Low-budget active learning requires choosing a useful small coreset, while the discrete selection problem is combinatorially hard.

    Source: §1 · p. 2

  • Method

    The method selects coresets using the Sinkhorn divergence and applies FW-Swap, which uses Frank-Wolfe candidates to warm-start gradient-based swap local search.

    Source: §1 · p. 2

  • Results

    FW-Swap achieves superior accuracy in the low-budget regime, with its advantage most pronounced at very small budgets.

    Source: §6 · p. 9

  • Takeaways & Limitations

    The results indicate the method may be highly suitable for medical applications such as EEG signals and radio imaging.

    Source: §6 · p. 9

    Computationally expensive cost matrices and Sinkhorn kernels constrain scaling to large datasets.

    Source: §5 · p. 9

Abstract

from arXiv · show

We consider low-budget active learning, which consists of selecting a limited number of points, the coreset, such that a model can be trained to high accuracy on the selection only. This problem is particularly relevant in contexts where labeling requires costly expert intervention, as in medical applications. We leverage features extracted from a pretrained self-supervised model to represent the data, and perform coreset selection directly in this feature space. In this paper, we use entropic optimal transport, specifically the Sinkhorn divergence, as the coreset selection criterion, which first allows us to get dimension-free sample complexity results, and second admits computationally efficient gradient evaluations. This opens the way to using gradient-based algorithms to rapidly compute solution candidates, further improved by a swap-based local search, with guarantees on the solution quality. Experiments on image benchmarks and medical datasets show that our method outperforms state-of-the-art heuristics in low-budget settings.

1 Introduction

The paper frames low-budget active learning as selecting representative coresets and proposes Sinkhorn-divergence selection with an algorithm tailored to discrete low-budget optimization. It reports competitive or superior accuracy across low-budget vision and EEG benchmarks.

1 Introduction

  • Representation-based active learning selects a task-independent coreset, while uncertainty-based strategies require an already-trained model and typically a high labeling budget.The central challenge for representation-based methods is choosing a criterion that identifies representative samples for learning.Source: §1 · p. 1
  • Optimal transport measures discrepancy between a coreset and the full dataset, and entropic regularization enables scalable Sinkhorn approximation with favorable statistical properties.Related coreset work addresses compression or both low- and high-budget regimes, whereas this work targets the discrete-selection challenge at low budgets.Source: §1 · pp. 1–2
  • The Sinkhorn divergence corrects entropic OT bias that can cause degenerate selections and supports a dimension-free generalization bound for models trained on the resulting coreset.The framework uses this divergence as its selection criterion.Source: §1 · p. 2
  • FW-Swap uses inexpensive Sinkhorn-divergence gradients, Frank-Wolfe active-set candidates, and swap-based local search, with a worst-case suboptimality guarantee.It is designed to approximately solve the coreset selection problem.Source: §1 · p. 2
  • The approach achieves competitive or superior accuracy against previously proposed methods across low-budget vision and EEG benchmarks.The paper identifies experiments on both benchmark types as evidence of its empirical performance.Source: §1 · p. 2

2 Active learning from the Sinkhorn divergence

The section formulates coreset selection as minimizing Sinkhorn divergence to the full dataset, explains why this divergence is preferred to entropic OT cost, and establishes conditional generalization bounds.

2.1 Preliminaries on optimal transport

  • Entropic OT is computable with Sinkhorn but biased; Sinkhorn divergence corrects that bias and provides gradients used by the later algorithm.The entropic OT cost is not a distance or divergence and can be positive when comparing a measure with itself.Source: §2.1 · pp. 2–3

2.2 Entropic optimal transport framework for active learning

  • The method selects B dataset points by minimizing Sinkhorn divergence to the full empirical measure; relaxing the discrete selection set yields a constant solution with zero value regardless of the instance.The paper uses continuous optimization methods in an original way to obtain information about the combinatorial problem.Source: §2.2 · pp. 3–4

2.3 Sinkhorn bias on active learning instances

  • For every ε>0, Sinkhorn divergence favors the desirable extreme configuration, while entropic OT cost favors the central configuration above a finite regularization threshold.The extreme configuration selects one point from each cluster.Source: Figure 1 · p. 4, §2.3 · p. 4

2.4 Generalization bound for the Sinkhorn divergence coreset

  • With Lipschitz losses and squared-Euclidean cost, the theorem bounds coreset loss via Sinkhorn divergence and variance terms and gives dimension-independent generalization bounds under a unit-norm data assumption.Lipschitzness is required only for the final classifier, not the self-supervised feature model.Source: §2.4 · p. 5

3 Solution methods for the Sinkhorn divergence coreset

FW-Swap combines Frank–Wolfe active-set construction with gradient-directed swaps to optimize coreset selection by Sinkhorn divergence. The paper gives a suboptimality guarantee and analyzes the method’s computational cost and runtime behavior.

3.1 The Frank-Wolfe Swap Algorithm

  • FW-Swap builds an active set with Frank–Wolfe, then refines candidates through gradient-directed single swaps instead of evaluating every neighboring solution.The swap search stops when it cycles and returns the lowest-divergence vertex encountered.Source: §3.1 · pp. 5–6

3.2 Approximation guarantees

  • The swap method’s suboptimality bound combines local-search error with mixture-term bias and, for small λ, depends on the number of swaps to an optimum.The stated bound applies to the swap algorithm run with mixture parameter λ.Source: §3.2 · p. 6

3.3 Runtime analysis

  • Each swap iteration is dominated by one Sinkhorn OT computation of complexity O(n^2), while exhaustive local search requires O(B(n − B)) evaluations per iteration.The authors report that exhaustive local search was prohibitively expensive in their experiments.Source: §3.3 · p. 6
  • Under the core assumption, the method acquires the B0-point core within B0 iterations, then reduces the problem to a hypersimplex with n − B0 candidates and budget B − B0.The core assumption requires those points to be acquired before, and never removed in favor of, points outside the core.Source: §3.3 · p. 6

4 Computational experiments

The experiments evaluate FW-Swap against established and recent selection methods across image, medical-image, and EEG classification tasks. FW-Swap performs best in the low-budget settings reported, with lower performance variance across experiments.

4.1 Experimental setup

  • The five tasks cover STL-10 and SVHN image classification, GasHisSDB histopathology, and left-versus-right-hand movement classification in two EEG datasets.The EEG datasets contain recordings from 109 and 52 subjects, respectively.Source: §4.1 · p. 7
  • Feature learning uses pretrained DINOv3 for STL-10, fine-tuned SimCLR for lower-resolution images, and SimCLR for both EEG datasets.The pretrained DINOv3 backbone is used without fine-tuning.Source: §4.1 · p. 7
  • Comparisons include random selection, k-medoids, k-centers, MaxHerding, TypiClust, and ProbCover; Wasserstein integer selection was stopped after three hours without competitive solutions.A linear classifier is trained on selected features for 30 epochs per active-learning round; results average 10 seeds.Source: §4.1 · p. 7, §4.2 · p. 8

4.2 Empirical results

  • FW-Swap leads on SVHN at every low budget, on STL-10 at low budgets (comparable from B = 40), and on GasHisSDB at small budgets.The reported figures show test accuracy (mean ± standard deviation).Source: §4.2 · p. 8, Figure 2 · p. 8, Figure 3 · p. 8
  • On both EEG datasets, FW-Swap achieves better accuracy at every budget, with a particularly large difference at B = 2.The comparisons are presented in Tables 1 and 2.Source: §4.2 · p. 8, Table 1 · p. 8, Table 2 · p. 9
  • Across the experiments, FW-Swap’s performance variance is lower than that of the other methods.Source: §4.2 · p. 8

5 Limitations

The approach depends on learned feature quality, faces computational costs that may impede scaling to large datasets, and is less consistent as the budget increases.

5 Limitations

  • Performance depends on learned feature quality; the cost matrix and Sinkhorn kernel can be expensive for large datasets, and results become less consistent as budgets increase.Source: §5 · p. 9

6 Conclusion

The conclusion presents FW-Swap as a theoretically grounded approach to low-budget active learning, with superior low-budget accuracy and particular promise for medical applications. The appendix collects proofs, technical developments, and additional computational results.

6 Conclusion

  • FW-Swap combines Sinkhorn divergence with combinatorial local search, supported by quantitative suboptimality bounds and statistical guarantees.The conclusion reports superior accuracy in the low-budget regime, especially at very small budgets.Source: §6 · p. 9

Appendix

  • The appendix supplies proofs, auxiliary technical developments, and additional computational results, including runtime analysis, feature-space comparisons, and complementary experiments.Source: Appendix · p. 12

A Auxiliary results

The section recasts ProbCover and k-medoids as Wasserstein-distance minimization problems, then shows that convex relaxation of the coreset problem yields a trivial optimization over the hypersimplex.

A Auxiliary results

  • ProbCover and k-medoids can be formulated as minimizing Wasserstein distance from the dataset to a measure supported on B points.The formulations use Euclidean distance for k-medoids and ProbCover’s ground cost for ProbCover.Source: A Auxiliary results · p. 12
  • For any divergence, the convex relaxation of coreset minimization is a trivial optimization over the hypersimplex.Its equal-weight center achieves objective value zero.Source: A Auxiliary results · p. 13

B Number of swap iterations analysis

The swap-iteration analysis describes a trajectory with a tail followed by a cycle and examines how acquiring a persistent core relates to its length. Empirically, the core accounts for more than 90% of the final selection.

B Number of swap iterations analysis

  • Under the core assumption, acquiring the persistent core precedes a reduced hypersimplex problem to which the iteration observations apply.The assumption requires that core points are acquired before outside points and are not subsequently removed.Source: B Number of swap iterations analysis · p. 13
  • On STL-10, the swap trajectory has a tail roughly proportional to budget on average, while its cycle remains small and constant.The tail comprises vertices visited once; Table 3 reports the two trajectory parts separately.Source: B Number of swap iterations analysis · p. 13, Table 3 · p. 14
  • On all budgets, the core accounts for more than 90% of the final selection, providing empirical evidence for the core assumption.The reported core combines points acquired once during swapping with original points retained from initialization.Source: B Number of swap iterations analysis · p. 13, Table 4 · p. 14

C Generalization bound

The section gives a generalization bound for Sinkhorn-divergence coreset selection under Lipschitz-loss and bounded-data assumptions. It also establishes a sample-complexity result for estimating the Sinkhorn divergence.

C Generalization bound

  • For bounded-support data, the sample complexity of the Sinkhorn divergence depends on a constant that depends exponentially only on the regularization parameter.The stated sample-complexity lemma assumes i.i.d. samples and a bounded ground cost.Source: C Generalization bound · p. 14
  • The entropic self-transport cost is bounded by twice the variance, and the stated bounded-data setting also gives an upper bound of one.The proof uses the product coupling as a valid coupling.Source: C Generalization bound · p. 16
  • Theorem 1 bounds coreset loss uniformly over parameters using the Sinkhorn divergence between the selected coreset and dataset, together with their empirical variances.The theorem also gives a true-risk generalization bound for any estimator when the underlying data satisfy the stated norm bound.Source: C Generalization bound · p. 16

D Sinkhorn bias for Cluster-Central-Outlier instances

The section compares Wasserstein and Sinkhorn costs for central, left, and extreme selections. Sinkhorn cost can favor the central configuration at finite regularization, whereas the Sinkhorn divergence prefers the extreme configuration for every regularization value.

D Sinkhorn bias for Cluster-Central-Outlier instances

  • The Wasserstein costs of the three selections rank the extreme configuration lowest.The passage identifies the extreme configuration as the minimum-cost choice.Source: D Sinkhorn bias for… · p. 17
  • The Sinkhorn-cost ranking matches the low-regularization ranking but inverts above a threshold as regularization increases.In the infinite-regularization limit, the transport plan becomes the product of the input weights.Source: D Sinkhorn bias for… · p. 17
  • At some finite regularization value, the central configuration has the smallest Sinkhorn cost.The central configuration is preferred above a finite threshold as regularization grows.Source: D Sinkhorn bias for… · p. 17
  • The Sinkhorn cost’s centrality bias can lead to selecting fewer points than the allocated budget.The authors note that this may oppose the expected and empirical behavior of using as many points as the budget allows.Source: D Sinkhorn bias for… · p. 17
  • For every regularization value, the Sinkhorn divergence prefers the extreme configuration over the left or central configurations.The section presents this contrast as avoiding the centrality bias and underfilling paradox of the Sinkhorn cost.Source: D Sinkhorn bias for… · pp. 17–18

E Analysis of the vertex descent algorithms

The analysis bounds swap descent’s suboptimality and tests FW-Swap against an exhaustively computed optimum on a synthetic problem. It also reports performance differences between SimCLR and DINOv3 feature spaces and notes a runtime cutoff for Wasserstein results.

E Analysis of the vertex descent algorithms

  • The smoothness analysis bounds the Hessian using Sinkhorn-potential stability; its constant depends on exp(M/ε), which the authors consider manageable with large regularization and small diameter.Source: E Analysis of the vertex descent… · p. 20
  • Theorem 2 gives swap descent a suboptimality bound, with k* swaps from its output to a minimizer and a smoothness constant depending on ε and λ.The analysis conservatively bounds k* by B for an instance-independent guarantee.Source: E Analysis of the vertex descent… · p. 21
  • On a 500-point, two-class synthetic dataset, FW-Swap had a small gap to the true minimum, and its Frank-Wolfe initialization produced closer values than random initialization.The true minimizer was computed by complete enumeration of the hypersimplex.Source: E Analysis of the vertex descent… · p. 22, Table 5 · p. 22

F Comparison of the self-supervised learning representation

G Detailed experimental results

Detailed experimental tables support the reported low-budget performance of FW-Swap across the evaluated datasets. It has the highest test accuracy in most cases and remains competitive with the strongest-performing methods otherwise.

Related papers

Loading 2610.01199v1…