acceptodds
Under review as a conference paper at ICLR 2027

Low-Budget Active Learning through Entropic Optimal Transport

Abstract

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 standard image and EEG benchmarks show that our method outperforms state-of-the-art heuristics in low-budget settings.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
active learning, low-budget, combinatorial optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_idGoOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies low-budget active learning through coreset selection. It selects exactly BB unlabeled samples by minimizing the Sinkhorn divergence between the selected subset and the full dataset in a self-supervised feature space. The proposed FW-Swap algorithm first runs Frank-Wolfe on a continuous relaxation and uses the intermediate active-set vertices as discrete candidates. It then improves each candidate using gradient-guided single-swap local search. The selected samples are labeled and used to train a classifier. The paper also provides a generalization bound and a suboptimality bound, and evaluates the method on image, histopathology, and EEG datasets.

Critical strengths
  1. The FW-Swap design is interesting. Although the continuous relaxation has a trivial optimum, the method extracts useful discrete candidates from the Frank-Wolfe trajectory and improves them using gradient-guided swaps.

  2. The method shows promising performance in several extremely low-budget settings, which is practically relevant when annotation is expensive.

Critical weaknesses
  1. The main theoretical motivation has a feasibility mismatch and a proof error. The optimization problem requires selecting exactly BB samples. However, the cluster-central-outlier example compares a one-point central configuration with a two-point extreme configuration. They are not simultaneously feasible under the same fixed-cardinality constraint. In addition, the proof defines p=m/(2m+1)p=m/(2m+1) but later states p−1/2=(2m−1)/(2(2m+1))>0p-1/2=(2m-1)/(2(2m+1))>0. The correct expression is p−1/2=−1/(2(2m+1))<0p-1/2=-1/(2(2m+1))<0. Since this positive bound is used in the subsequent proof, the current argument does not establish the claimed proposition.

  2. The experiments do not sufficiently isolate the contributions of the debiased Sinkhorn objective, Frank-Wolfe initialization, and swap refinement. A controlled comparison of Sinkhorn cost versus Sinkhorn divergence under the same optimizer, and FW-only versus randomly initialized Swap versus FW-Swap, would make the contribution much clearer. Some empirical statements are also stronger than the detailed tables support, since FW-Swap is not the best method in every reported low-budget setting.

Questions for authors
  1. Can the authors reformulate the cluster-central-outlier example so that all compared configurations belong to the same fixed-cardinality feasible set? Can the authors also provide a corrected proof after fixing the incorrect identity for p−1/2p-1/2?

  2. In the mixture-bias proof, if F(t)=Dε(αxt,μ^D)F(t)=D_\varepsilon(\alpha_x^t,\hat{\mu}_D), the natural identity is F(λ)−F(0)=∫0λF′(t),dtF(\lambda)-F(0)=\int_0^\lambda F'(t),dt. Could the authors clarify the parameterization used in the current derivation and confirm whether the final suboptimality bound remains unchanged?

  3. The generalization theorem assumes squared Euclidean ground cost, while the experimental section describes Euclidean distance. Which cost is actually used in the implementation, and which theoretical guarantee applies to the experiments?

  4. Could the authors provide controlled ablations comparing Sinkhorn cost versus Sinkhorn divergence, and FW-only versus randomly initialized Swap versus FW-Swap, under the same representation, classifier training, and computational budget?

3 comments

Response to weaknesses

  1. The feasibility mismatch can be easily fixed, for instance by putting two atoms as the central outlier. Otherwise even with a single outlier, the biased Sinkhorn will select αL\alpha_L instead of αE\alpha_E. We also corrected the proof, only that last step of Proposition 6 needed to be fixed locally, the result still holds.

  2. We added a complete ablation study to the revised manuscript that properly compares Sinkhorn cost versus Sinkhorn divergence under the same optimizer, and randomly initialized Swap versus FW-Swap. The empirical statement has been revised to be clearer given the results.

Response to questions

  1. See W1.

  2. We fixed a typo, the potentials should have been indexed by λt\lambda t instead of just tt, the integral then uses a change of variable s=λts=\lambda t.

  3. We use the squared Euclidean ground cost in the proof simply to benefit from the Rigollet (2025) result. However, in practice, we find that the AL model achieves better results using a Euclidean ground cost.

  4. This has been added to the revised manuscript in the appendix under section ablation study. In this section, we detail how the FW-Swap algorithm changes with different parameters put to test. We vary the values of both the entropic regularizer ε\varepsilon and the stability mixing term λ\lambda. We compare the Sinkhorn divergence to both the Sinkhorn algorithm and the Wasserstein distance on the downstream task. Lastly, we added a table comparing the results given by each: FW-only, randomly initialized Swap, and FW-Swap. Both the parameters and the AL pipeline were fixed for the last two comparisons as they are in the main paper. FW-Swap remains the best on all these baselines.

Thank you for the response and revisions. The corrections to the theoretical example and proofs, together with the additional ablation studies, address several of my original concerns.

However, the mismatch between the squared Euclidean cost assumed in the theory and the Euclidean distance used in the experiments remains unresolved. The acknowledged baseline implementation errors and the use of ground-truth labels to construct class-balanced candidate pools also weaken the empirical evidence.

These remaining issues affect my confidence in the paper's main claims. I therefore maintain my rating.

We acknowledge the noticeable difference in the empirical results weakens our orginal claims. However, FWSwap remains competitive on most instances and the best performing when the budget is the same as the number of classes (B=10 for both STL-10 and SVHN, B=2 for GasHisSDB and the EEG datasets). Specifically, on SVHN, FWSwap yields the best performance on B=10, 20. For the higher budgets, we achieve similar results to the best method, which in this case would be TypiClust. More so, on the EEG datasets our positioning does not change. In all experiments, we also present the most stable results.

Regarding the class-balanced subsampled dataset, this step is done simply to reduce the pool to a size compatible with our compute power. It is applied once and is independent of the selection process. All other methods receive the same identical pool, and no method has access to the labels during selection. We also point out that all datasets used as reference benchmarks are typically made balanced by selecting from the different classes, we thus follow a standard process.

Regarding the mismatch between the ground cost in theory and experiments, we noticed that the distance performed better and kept it for practice. The reason for the squared one in theory is being able to leverage results from Stromme Rigollet, our manuscript is not about statistical OT theory but about a new method for active learning. The whole generalization bound could be adapted by re-adapting their whole set of results to the Euclidean distance, but this would create unnecessary auxiliary results that are incremental and not the focus of our paper, there is value in conciseness.

Finally, the baseline implementation errors have all been fixed with the correct results now in the available PDF.

Reviewer_vFsSOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses low-budget active learning from an optimal transport perspective. The authors propose to select a small subset of unlabeled data by minimizing the Sinkhorn divergence between the selected subset and the full dataset in a self-supervised feature space. To tackle the resulting discrete selection problem, they introduce FW-Swap, which runs Frank–Wolfe optimization to obtain initial candidates and then refines them through gradient-guided swaps. The paper also analyzes the bias of entropic OT and provides a generalization bound as well as a suboptimality bound for the proposed algorithm. Experiments on image and EEG datasets show gains over several existing coreset selection methods, particularly when the labeling budget is very small.

Critical strengths
  1. The paper tackles small-budget problem in active learning: the trained classifier became unreliable. The authors provide a clean formulation of sample selection as Sinkhorn divergence minimization and build a solution approach specifically tailored to this low-budget regime, which I found well thought out.

  2. The experimental results are encouraging, especially on the EEG datasets, where the method yields substantial gains with very few labeled examples. The evaluation also covers medical domains such as histopathology images and EEG signals, where annotation is particularly costly, which highlights the practical relevance of the problem setting.

  3. Both the selection criterion and the algorithm are supported by theoretical analysis. Proposition 1 clearly illustrates how the entropic bias can lead to degenerate selections, and the generalization and suboptimality bounds provide theoretical grounding for the approach. The OT perspective also connects the method to existing criteria such as k-medoids and ProbCover (Proposition 2).

Critical weaknesses
  1. My main concern is that the contributions of the main components are not sufficiently evaluated, as the paper lacks ablation studies on them. The paper argues that the Sinkhorn divergence is preferable to the standard entropic OT cost because it corrects the entropic bias. However, this advantage is demonstrated mainly through a simplified theoretical example. A direct comparison of the two objectives on the actual downstream tasks, using the same optimization algorithm, would be far more informative. Likewise, FW-Swap combines Frank–Wolfe initialization with gradient-based swapping, but it is hard to tell how much each component contributes to the final accuracy. Appendix E compares FW-Swap with randomly initialized swapping on synthetic data, which is helpful, but the corresponding comparison on downstream tasks is missing.

  2. I also think the experimental setting and the scope of the comparisons need clarification, as the experiments compare only against representation-based coreset selection methods such as TypiClust, ProbCover, and MaxHerding. I understand this choice, since the proposed method does not require a trained classifier for sample selection. However, the experimental protocol seem not to be clear. Phase 3 states that the classifier is trained at each active learning round, which suggests an iterative procedure. However, Algorithm 1 takes only the cost matrix, the budget, and ϵ\epsilon as inputs, and the selection problem in Eq. (3) does not condition on an already labeled set or on the trained classifier. Since the swap phase can also remove previously selected points, it is unclear how many samples are acquired per round, whether the selections are nested across rounds, and how, if at all, the rounds interact with the selection. If the method is intended to be used within an iterative active learning loop, comparisons with uncertainty-based or gradient-based methods such as Entropy Sampling, BADGE[1], and SAAL[2], given an initial labeled set, would be valuable. Such comparisons would help clarify when the proposed method should be preferred over model-dependent acquisition strategies.

I also have some concerns about computational efficiency. Section 3.3 analyzes the per-iteration cost and Appendix B reports the number of swap iterations, but the paper does not report wall-clock runtime or memory usage for FW-Swap or the baselines, nor the number of Frank–Wolfe iterations and the size of the resulting active set. Since each swap iteration requires a Sinkhorn computation that scales quadratically with the unlabeled pool size, and the swap phase is run from every vertex in the active set, these practical costs are important to assess, particularly for larger pools such as SVHN.

  1. Finally, the experimental evaluation lacks several key details and is limited in scope. Important settings are not reported, including λ\lambda, which directly enters the suboptimality bound in Theorem 2. The sensitivity to ϵ\epsilon is described only qualitatively, even though the paper states that values outside [0.05, 1.5] drastically change performance. Moreover, the value of the mixture parameter λ\lambda is not reported at all, and no sensitivity analysis is provided, although it directly enters the suboptimality bound in Theorem 2.

[1]: Ash, Jordan T., et al. "Deep batch active learning by diverse, uncertain gradient lower bounds." arXiv preprint arXiv:1906.03671 (2019).

[2]: Kim, Yoon-Yeong, et al. "Saal: sharpness-aware active learning." International Conference on Machine Learning. PMLR, 2023.

Questions for authors

Q1. Ablation of the selection criterion and the optimization procedure

Could the authors report downstream accuracy on the main benchmarks for the following variants?

  • (i) FW-Swap with the standard entropic OT cost in place of the Sinkhorn divergence,
  • (ii) the best vertex in the Frank–Wolfe active set, without the swap phase, and
  • (iii) the swap phase started from a random vertex instead of the Frank–Wolfe active set.

These comparisons would show how much of the improvement comes from the criterion itself and how much from each stage of FW-Swap, beyond the synthetic objective-value comparison in Appendix E.

Q2. Active learning protocol and model-dependent baselines

Phase 3 states that the classifier is trained at each active learning round, but Algorithm 1 takes only the cost matrix, the budget, and ε\varepsilon as inputs. Could the authors clarify how many samples are acquired per round, whether the selections are nested across rounds, and whether the selection at each round uses the previously labeled set or the trained classifier in any way?

If the method is intended to be used within an iterative active learning loop, could the authors compare against uncertainty-based or gradient-based methods such as Entropy Sampling, BADGE, or SAAL (I hope that authors include at least one baseline) , starting from the same initial labeled set and using the same total annotation budget?

Q3. Computational cost

Could the authors report wall-clock runtime and peak memory for the complete selection procedure, including both the Frank–Wolfe and swap phases, as well as for the baselines?

Q4. Hyperparameters and evaluation scope

  • What value of the mixture parameter λ\lambda was used in the experiments, and how sensitive are the results to it?
  • Could the authors report quantitative results for different values of ε\varepsilon, both within and outside the range [0.05, 1.5]? It would also help to explain how the values for the vision (ε=1.5\varepsilon = 1.5) and EEG (ε=0.5\varepsilon = 0.5) tasks were chosen.

Q5. Comparison with Yin et al. (2025) The paper positions itself as complementary to Yin et al. (2025), which also uses a Sinkhorn-based criterion for coreset selection, but no experimental comparison is provided. Could the authors clarify the main practical difference, in particular whether the method of Yin et al. selects existing data points or optimizes new support points? If it can be applied in the same setting of selecting existing points, a direct comparison would help establish the contribution.

2 comments

Response to weaknesses

  1. We now report in the revised manuscript test accuracy on STL-10 across all low-budgets for:
  • the best vertex in the Frank–Wolfe active set, without the swap phase,
  • the swap phase started from a random vertex instead of the Frank–Wolfe active set.

This is added to Appendix E. Another table comparing different objective functions using the same FWSwap algorithm is added to the new Appendix G titled "Ablation study". We compare the performance of the Sinkhorn divergence to the one of Sinkhorn and Wasserstein. The experimental setup does not change from that mentioned in the main paper.

  1. Our wording may have caused confusion as to what the experimental setup looks like, we clarified it in the revised version. Our method is not an iterative AL strategy, it addresses the one-shot, cold-start low-budget setting, the same as TypiClust, MaxHerding, and ProbCover do. For a given budget BB, FW-Swap selects B points using only the cost matrix CC. This is why Algorithm 1 only takes B,C,εB, C, \varepsilon as arguments. The classifier in Phase 3 indeed plays no role in the selection process.

  2. The mixture parameter λ\lambda used in the experiments is 1e-2. A sensitivity report for both the entropic regularizing term ε\varepsilon and the stability mixture term λ\lambda is now provided in the revised version of the PDF. This further explains our initial choice for the values of the parameters.

Response to questions

Q1,2,4. These concerns are all addressed in response to the weaknesses.

Q3. Yes, a runtime report across budgets on the STL-10 dataset, using the same parameters described in the paper (ε=1.5,λ=0.01\varepsilon=1.5, \lambda=0.01), has also been added to the manuscript. It details the total time in seconds for the FW-Swap algorithm, as well as the time for both the FW step alone and the swap step alone.

Q5. The setup here is pool-based AL, where the problem is combinatorial by design. We can only query existing examples for labeling from the unlabeled pool. What the Yin et al. (2025) paper does is different. They illustrate their method using an AL example, however, they instead optimize the locations of B free points, so the resulting points are generally synthetic. The authors acknowledge in their paper that the coreset does not inherently ensure that the samples are drawn from the original dataset. In fact, in their AL example, they use synthetic data labeled by a logistic regression model trained on the full dataset. This is not available in pool-based AL on real data.

Thank you for the revision. The new ablations on STL-10 (Tables 6 and 11) address my main question about the criterion and the two stages of FW-Swap, and the clarification on Yin et al. (2025) is helpful. Some concerns remain.

(1) The new sensitivity results do not support the claims in the main text. Table 9 contradicts the statement in Section 4.1 that ε\varepsilon has little effect within [0.05, 1.5], since the lower end of this range performs worse than random selection. The value of ε\varepsilon appears to be chosen by test accuracy on STL-10, one of the evaluation datasets, while ProbCover's δ\delta is set by a heuristic to avoid tuning, and the choice of ε\varepsilon for EEG is still not explained. The variation across λ\lambda in Table 10 is not monotone and, at the smallest budgets, exceeds the margin over the strongest baseline.

(2) The runtime report covers FW-Swap on STL-10 only. Baseline runtimes, peak memory, the number of Frank-Wolfe iterations and the active-set size are still missing, and the larger SVHN pool, where the quadratic cost matters most, is not covered.

(3) The response clarifies that FW-Swap solves each budget from scratch using only the cost matrix, which answers my question about the protocol. However, the main text still does not state the one-shot, cold-start setting, and Table 12 still reports runtime per AL round, so the revision does not yet reflect this clarification.

I will keep my current score.

Reviewer_aNJoOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies coreset selection for low-budget active learning using the Sinkhorn divergence. The authors formulate sample selection as a discrete optimization problem that minimizes the discrepancy between the selected subset and the full dataset in a self-supervised feature space. To solve this problem, they propose FW-Swap, which uses Frank-Wolfe optimization to generate candidate subsets, followed by gradient-guided local swaps. The paper also provides theoretical results concerning generalization and optimization error. Experiments on image classification and EEG datasets report improvements over several existing active learning methods, particularly at very small labeling budgets.

Critical strengths

1. A relevant problem with a reasonable methodological motivation.

The paper addresses the practically important setting of active learning under extremely limited labeling budgets. The use of Sinkhorn divergence is motivated by an explicit example showing that entropic OT bias can lead to undesirable selections. This provides a reasonable justification for the proposed objective.

2. An interesting approach to discrete coreset optimization.

The authors recognize that the continuous relaxation has a trivial optimum and propose to use Frank-Wolfe to identify promising discrete candidates, followed by local swaps. This is a sensible approach to the combinatorial structure of the problem.

Critical weaknesses

1. Serious concerns about the validity of the experimental comparisons.

The supplementary code appears inconsistent with the experimental protocol described in the paper.

In particular, TypiClust and MaxHerding are passed a pairwise distance matrix, although their implementations operate on input feature vectors. The k-center implementation similarly computes distances between columns of the distance matrix rather than using the original pairwise distances. Consequently, several baselines appear to be evaluated under a different geometry from that described in the manuscript.

More concerningly, the SVHN and GasHisSDB experiments use ground-truth labels to construct class-balanced candidate pools through class-wise medoid selection before active learning. This introduces label information into a stage that is supposed to operate on unlabeled data. The procedure is not adequately disclosed or justified in the paper.

There are also discrepancies in classifier architectures, training epochs, and hyperparameter settings between the manuscript and the provided scripts.

Since the empirical comparisons are central to the paper's contribution, these inconsistencies substantially weaken confidence in the reported improvements. I cannot determine whether the main conclusions would hold under the stated experimental protocol.

2. The theoretical guarantees are weaker than the paper suggests.

Theorem 1 provides a dimension-independent risk bound, but the bound contains a variance term that generally does not vanish as the sample size increases. Therefore, its practical significance as a generalization guarantee is limited.

Moreover, the coreset bound includes additional variance terms that are not optimized by the proposed objective. The connection between minimizing Sinkhorn divergence and improving downstream classification performance is therefore less direct than the paper suggests.

There is also a mismatch between the squared Euclidean cost assumed in the theoretical analysis and the Euclidean distance used in the experimental description. The applicability of the Lipschitz-loss assumption to the actual downstream learning setting requires further justification.

These concerns do not necessarily invalidate the mathematical results, but they limit the extent to which those results support the paper's claims.

Questions for authors
  1. Were the reported experimental results generated using the exact code provided in the supplementary material? In particular, can the authors explain why TypiClust, MaxHerding, and k-center operate on distance-matrix columns rather than the original feature-space distances? Results with correctly configured baselines would be important for assessing the paper.

  2. Why are ground-truth labels used to construct the candidate pools for SVHN and GasHisSDB? Can the authors provide results using candidate pools constructed entirely without label information?

  3. Can the authors clarify the practical significance of the generalization bound, particularly the non-vanishing variance term, and explain how the theoretical assumptions correspond to the experimental setting?

2 comments

Weaknesses

We thank the reviewer for pointing out the flaw in the code regarding TypiClust and MaxHerding. This error has been fixed, and indeed, MaxHerding surpasses FWSwap on multiple instances. However, FWSwap remains strong when the budget is the lowest. For higher budgets, we remain comparable to the best method, which is now MaxHerding. These changes have been added to the new version of the PDF in the experiments section.

For the SVHN and GasHisSDB experiments, we constructed class-balanced pools and then ran the experiment on the unlabaled feature space. The labels did not affect the downstream task. This was done only for computational reasons as we do not have the ressources high-memory GPUs.

The classifier architecture may vary from one layer to two in some experiments, the training epochs are either 30 or 150 (30 x 5 repetition rounds), and the hyperparameters are set exactly as the paper reports. We will pay closer attention to the reported details to ensure proper description of the pipeline for reproducibility.

Response to questions

  1. Yes, the results were generated using the exact code provided in the supplementary material. We thank the reviewer for bringing up this very important issue. The updated results are in the new version of the PDF in all the the tables reporting test accuracy and empirical results.

  2. The labels were only used to subsample the original datasets to a size that fits our compute (regarding the nxn cost matrix). They weren't passed down to any of the methods in the downstream task. FW-Swap, as all the other methods, only see the unlabeled features of the same pool. We understand that a class-balanced pool is rare in the real-world. The unbalanced case would be a good case to tackle in future works. However, the labels being passed at that stage do not affect the fairness of comparison between the methods.

  3. We favored simplicity for the generalization bound, and wanted in particular to use the dimension-free results of Stromme and Rigollet to avoir re-deriving multiple results for the Sinkhorn divergence from scratch. This is also why one assumption (squared Euclidean distance as ground cost) differs from the experiments (Euclidean): the non-squared distance performs better in practice.

Thank you for your response and the revisions. I appreciate the authors' efforts in correcting the baseline implementations and updating the experimental results. However, several concerns central to my original assessment remain unresolved.

W1: Effectiveness of FW-Swap. While I appreciate the correction of the baseline implementations, the updated results substantially weaken the empirical evidence for the proposed method. In particular, MaxHerding now outperforms FW-Swap at four of the six budgets on STL-10. On GasHisSDB at B=4, it seems that MaxHerding outperforms FW-Swap by more than 10pp. Although FW-Swap retains advantages in some extremely low-budget settings, its overall superiority over existing methods is not convincingly demonstrated, raising concerns about the practical benefits of the proposed approach given its additional optimization complexity.

W1: Label-informed candidate pools. My main concern remains that the candidate pools for SVHN and GasHisSDB are constructed using ground-truth labels through class-balanced subsampling and class-wise medoid selection. Standard pool-based active learning assumes that candidate selection operates on unlabeled data, without access to ground-truth labels. The label-informed preprocessing therefore introduces information unavailable in the standard setting, and may substantially affect the resulting sample distribution. While using identical pools across methods ensures fairness within this particular experimental setup, it does not establish their effectiveness under standard active learning conditions. The authors have not provided results using label-free candidate pools, so this concern remains unresolved.

W2. The response explains the motivation for retaining the non-vanishing variance terms and using a squared Euclidean cost in the analysis. However, these explanations do not resolve the limited connection between the theoretical guarantees and the actual downstream learning setting, particularly given the different ground cost used in the experiments.

A minor point: The caption of Figure 4 seems to be overlapping with Table 1. I encourage the authors to fix that in future revisions.

Overall, I acknowledge the authors' efforts in addressing the feedback, but the remaining issues with experimental validity and theoretical support continue to affect my assessment of the paper's soundness. I will therefore maintain my rating.

Reviewer_TAGXOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Authors consider a low-budget active learning scenario and aim to select the core-set that will allow for the efficient learner performance. The model uses as a training data already informative representations: it takes already learnt representations / features from previous task, e.g. self-supervised learning, and selects the core-set from this data manifold.

The proposed method uses Sinkhor divergence to assess how well the selected subset represents the distribution of the full dataset. Authors modify the Frank–Wolfe algorithm to generate candidate subsets and a gradient-guided swap procedure to improve them. A linear classifier is then trained on the selected core-set.

The paper is mostly clearly written and easy to follow.

Critical strengths
  • Authors identified highly interesting problem and provided interesting solution with promising ideas.

  • Selecting examples using learned features allows the method to benefit from information in the unlabelled dataset before spending the annotation budget.

  • The Sinkhorn divergence provides a precise objective for measuring how closely the selected examples represent the full dataset. This makes the selection process easier to analyze and compare with alternatives. The paper explains why the uncorrected transport cost can favor undesirable selections and motivates using the debiased Sinkhorn divergence instead.

  • In Frank-Wolfe: the idea of using gradient information avoids the need to evaluate every possible swap.

Critical weaknesses
  • In Theorem 1, p. 5, the generalisation bound does not establish the vanishing learning error: for �0��0� the error bound is bounded: L2Var[μ]L\sqrt{2 Var[\mu]}. Furthermore, the method minimises only DεD_\varepsilon. The core-set variance Var[μ^S]Var[\hat\mu_S] also depends on the selected subset and reducing the divergence does not necessarily reduce the full upper bound the theorem provides.

  • The analysis assumes a uniformly Lipschitz loss on the space used for optimal transport, whereas the experimental classification loss depends on both features and labels. Smoothness of the classifier alone does not establish smoothness across examples with different labels.

  • The method combines Sinkhorn debiasing, Frank–Wolfe initialization, gradient-guided swaps, and mixture stabilization, but the downstream experiments do not separately evaluate these.

  • The novelty seams to be incremental.

Questions for authors

Theorem 1:

  1. does y\bf{y} denote an embedding or a labelled example? What assumption about the relationship between embeddings and labels lets a feature-only Sinkhorn divergence control supervised classification loss?

  2. the variance term does not vanish as nn increases. Can you derive a guarantee that becomes small as the label budget BB grows?

Frank-Wolfe:

  1. What property of the Frank–Wolfe trajectory makes its active vertices good candidates, despite the trivial relaxation? How does candidate quality change with the number of Frank–Wolfe iterations?

  2. Which properties of the embedding predict an advantage for FW-Swap? Can we predict, using unlabelled data, the budget at which another selection strategy becomes preferable?

3 comments

Response to weaknesses

  1. The generalization bound indeed has a residual variance term that we keep as-is for simplicity and readability. Our approach proposes a practical method to find a representative coreset and the generalization bound provides some guarantee that a function of the Sinkhorn divergence is bounding the risk. Importantly, we did not want to expand the scope of the manuscript, (which already covers many aspects as pointed out by reviewers) to new results in statistical learning theory. That's also why we relied on the Rigollet & Stromme result and based ourselves on their assumptions to avoid producing new results orthogonal to the main message.

  2. We indeed use the fact that the loss is Lipschitz in the feature space, similar to the Sener and Savarese 2018, which is much more natural than Lipschitz jointly on the features and labels.

  3. A report comparing different ε\varepsilon values, varying from 0.010.01 to 10.010.0, was added to the revised manuscript in Appendix G titled "Ablation study". Along in the same section, we report on the different stability mixing values of λ\lambda. Finally, we compare using the Sinkhorn divergence, Sinkhorn, and Wasserstein as an objective function in FW-Swap algorithm on the downstream task. Another table comparing both FW only (selecting the best atom return by FW), randomly initialized swap, and FW-Swap is added to Appendix E.

Response to questions

Regarding Theorem 1:

  1. y denotes an embedding. We do not need any assumption on the mapping from feature to labels. Mahmood et al discuss the link between the two in their Appendix B.

  2. The guarantee we obtain is a tradeoff between tractability through smoothness (unlike Wasserstein), unbiasedness (unlike the Sinkhorn loss), unfortunately the guarantees we obtain are tight and the additional term cannot vanish while maintaining the dimension dependence.

The first inequality of Theorem 1, R_n(theta) - R_S(theta) <= ... is achieved by an instance with B points at the origin + 2d points at +- 1/2 e_j, j in [d], and f=||.||_2. The second inequality E[R(theta_hat) - R_n(theta_hat)] <= ... is achieved by the previous 2d points uniform, with f being the distance to the nearest sample in the training.

Frank-Wolfe

  1. The FW trajectory explores vertices that could be good candidates, we do not have a theoretical grounding but empirical evidence that this is better than the same budget of uniform samples of vertices.

  2. We do not have properties that comparatively improve FWSwap (or more broadly, the Sinkhorn divergence) compared to other criteria, and why this is consistently better at the lowest budgets.

I would like to thank authors for their response. I believe this is great research direction but there is more work needed on the paper to fix the theoretical flows.

For the next version I would suggest to include more informative Figure 1, that explains the advantage of the method over ASI, sharpen the claims related to theorems, clearly explain that it covers the worst case scenario. I appreciate that in the revised manuscript authors revised also some of the AI hallucinations, e.g. Section D has been replaced to Appendix D on l. 205 of original manuscript.

I will increase my score to weak accept.

We thank the reviewer for their response and for revising their original score.

We point out that ASI is an uncertainty-based method, which requires having an already trained model, and selects sample over iterative rounds. This is different that the setting we tackle in this paper.

We thank the reviewer as well for the suggested changes which we will make in the next version, with a focus on the theoretical aspects. We will state clearly in the main text that our guarantees cover the worst-case scenario.

We also thank the reviewer for noting the corrections already made in the revision. We point out this was not an AI hallucination but a display format from the cleveref latex package.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.