Uncertainty Herding: One Active Learning Method for All Label Budgets
Authors: Wonho Bae
Danica J. Sutherland
Gabriel L. Oliveira
Venue: ICLR 2025 Poster (2025)
Keywords: Active learning
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: Most active learning methods struggle to perform well across both low- and high-budget settings. We propose Uncertainty Herding, a fast and flexible method that adapts to all regimes, consistently matching or surpassing state-of-the-art performance.

Abstract: Most active learning research has focused on methods which perform well when many labels are available, but can be dramatically worse than random selection when label budgets are small.
Other methods have focused on the low-budget regime, but do poorly as label budgets increase.
As the line between "low" and "high" budgets varies by problem,
this is a serious issue in practice.
We propose *uncertainty coverage*,
an objective which generalizes a variety of low- and high-budget objectives,
as well as natural, hyperparameter-light methods to smoothly interpolate between low- and high-budget regimes.
We call greedy optimization of the estimate Uncertainty Herding;
this simple method is computationally fast,
and we prove that it nearly optimizes the distribution-level coverage.
In experimental validation across a variety of active learning tasks,
our proposal matches or beats state-of-the-art performance in essentially all cases;
it is the only method of which we are aware that reliably works well in both low- and high-budget settings.

Published as a conference paper at ICLR 2025
UNCERTAINTY HERDING: ONE ACTIVE LEARNING METHOD FOR ALL LABEL BUDGETS
Wonho Bae
Danica J. Sutherland
University of British Columbia & Borealis AT whbaeêcs cateeescsubc.cco
University of British Columbia & Amii dsuthãcs ubc.ca
Gabriel L. Oliveira'
Borealis AI
gabriel wwwveeiratorrrrlllaa............
ABSTRACT
Most active learning research has focused on methods which perform well when many labels are available, but can be dramatically worse than random selection when label budgets are small. Other methods have focused on the low-budget regime, but do poorly as label budgets increase. As the line between "low" and "high" budgets varies by problem, this is a serious issue in practice. We propose uncertainty coverage, objective which generalizes variety of low- and high- budget objectives, as well as natural, hyperparameter-lighh methods to smoothly interpolate between low- and high-budget regimes. We call greedy optimization of the estimate Uncertainty Herding; this simple method is computationally fast, and we prove that nearly optimizes the distribution-level coverage. In experimental validation across a variety of active learning tasks, our proposal matches or beats state-of- the art performance in essentially all cases; is the only method of which settings.
we are aware that reliably works well in both low- and
INTRODUCTION
In active learning, rather than being provided a dataset of input-output pairs as in passive learning, a model strategically requests annotations for specific unlabeled inputs. The aim is to learn good model while minimizing the number of required output annotations. This procedure is generally iterative: model is initially trained on small, labeled dataset, then selects the most "informative" data points from an unlabeled pool to annotate. This is particularly useful when labeling is expensive or time-consuming. For example, manual annotations of medical imaging by radiologists or pathol- ogists may be especially time-consuming and costly. Measuring whether a compound interacts with certain biological compound may require slow, high-aceuracy chemical simulations or even lab experiments. Discovering a customer's product preferences may require giving them many offers, which is slow, potentially expensive, and may produce a poor customer experience.
The most popular line of work in active learning has used notions of uncertainty to measure how informative each candidate data point is expected to be, and selects data points for labeling to maxi- mize that measure. Although these uncertainty- based approaches often work well in the experimen- tal settings where they are evaluated, |Hachen et al. (2022); Yehuda al. (2022) have shown that in low-budget gegimes-wheree budget refers to the total number of labeled data points-ther can be substantially worse than random selection, presumably because the model's estimate of uncertainty is not yet reliable. To address this, they (and some others) have proposed methods that prioritize "representative" data points, often built on clustering methods such as k-means. These methods can work substantially better in low-budget regimes, but themselves often saturate performance and do worse than uncertainty-base selection once budgets are large enough.
In practice it is difficult to know whether given budget is "high" or "low" for particular problem; greatly depends on the particular dataset and model architecture. Hacohen & Weinshall (2024)
'These authors contributed equally.

---

Published as a conference paper at ICLR 2025
proposed algorithm, SelectAL, select whether to use high- or low-budget method. This ap- proach, however, assumes discrete budget regimes when there is often not a clear boundary, and because of the form of the algorithm is also unable to consider uncertainty-basee active learning measures directly. SelectAl. also requires re-training models many times, which may be computa- tionally infeasible, and requires nontrivial amount of data holdout for validation, issue when budgets are low. Perhaps most importanly, the algorithm appears quite sensitive to small, subtle decisions; our attempts at replication gave extremely inconsistent and unreliable estimates of the regime, overall yielding worse performance than reported in the paper.
This motivates the aim of finding a single active learning algorithm which can seamlessly adapt from low- to high-budget regimes. While there have been various hybrid methods combining representa- tion and uncertainty, we find in practice that none of these methods work well in low-budget settings. We therefore propose an objective called uncertainty coverage, adding a notion of uncertainty to the "generalized coverage" of Bae et al. (2024) and its greedy optimizer MaxHerding. We call greedy optimization of the empirical estimate of the uncertainty coverage, which we prove nearly optimizes the true uncertainty coverage, Uncertainty Herding (UHerding).
The uncertainty coverage agrees with the generalized coverage in one extreme of parameter setting, while agreeing with uncertainty measures in another. To naturally interpolate between those settings, propose simple method to adaptively and automatically adjust these parameters such that the objective moves itself from mostly representation-basee this parameter adaptation scheme, we demonstrate that UHerding outperforms MaxHerding (and all other methods) in low-budget regimes, while also outperforming uncertainty sampling (and all other methods) in high-budget regimes, across several benchmark datasets (CIFAR-10 and -100, Tiny- ImageNet, DomainNet, and ImageNet) in both standard supervised and transfer learning settings. Furthermore, we describe how several existing hybrid active learning methods are closely related to UHerding, and confirm that our parameter adaptation schemes also benefit existing hybrid methods.
to mostly umcertainty-basee behavior. With
2 RELATED WORK AND BACKGROUND
The most common framework in active learning is pool-based active learning: at each step t e 21, ... .T) a labeled set L S X' is iteratively expanded by querying set of new data points S, (xx) ) from an unlabeled pool of data points U, S X' where X denotes the support set of the data distribution of interest. A model is then trained on the new L Usually, the most important component is determining which points annotate.
Uncertainty-based Methods "Myopic" methods that rely only on a current model's predictions include entropy (Wang& & Shang 2014), margin [Scheffer et al.] (200T), confidence, and posterior probability (Lewis& & Catleti 1994 Lewis &
In the Bayesian setting, BALD (Gal et al.
2017 Kirsch et al. 2019) uses mutual information between labels and model parameters. BAIT (Ash al. 2021) tries to select data points that minimize Bayes risk. Instead of using snapshot of trained model. Kye et al. (2023) exploit uncertainties computed in the process of model training.
Some models focus "looking ahead" to predict how data point will change the model. These include methods based on expected changes in model parameters (Settles) 2009; (Stttles et al. Ash et al. 2020), expected changes in model predictions (Freytag |014| Käding al. 2016
2007
2018). and expected error reduction (Roy & McCallum) 2001] Zhu et al., [2003] Guo & Greiner
2007 These approaches are primarily used with simple models like linear and Naive Bayes models.
For deep models, a neural tangent kernel-based linearization (Mohamadi et al. 2022) can be used,
though it offers limited improvement over uncertainty sampling relative to its computational cost.
Representation--aael Methods These methods select data points that represent (or cover) the data distribution. Traditional methods include k-means (Xu et al. 2003). medoids (Aghaee et al.) 2016) and medians (Voevodski et al. 2012). [Hacohen et al. (2022) show that selecting representative points is particularly helpful in budget regimes, and propose Typiclust, which selects the "most typical" points in each cluster. Biyık al. (2019) utilize determinantal point processes instead.
'The authors have not publicly released code though indicated in private communication they plan do so.
2

---

Published as a conference paper at ICLR 2025
Another approach is to minimize distance between the labeled and unlabeled data distributions, whether kernel MMD (Chen et al. 2010). Wasserstein distance (Mahmood et al. 2022) or an esti- mate of the KL divergence tailored transfer learning in ActiveFT (Xie et al. 2023).
Sener & Savarese 2018) convert the objective active learning into maximum coverage, proposing greedy k-center. Instead of finding the minimum radius cover all data points, ProbCover (Yehuda et al. 2 greedily select data points to cover the most data points with a fixed radius. While its performance sensitive the choice of radius (also difficult set), MaxHerding (Bae et al. (024) generalizes to a continuous notion of coverage, generalized coverage (or GCoverage), which is less sensitive parameter choice. As we build directly on this method, we describe it in more detail.
GCoverage is defined in terms of a function k X' x X x (X' - V) - R>o, which computes V.
similarity between x and x' based on feature mapping 9
Bac et al. (2024) mostly use
the Gaussian kerne Ko (x,x'; g': g)
exp
llg(x) g (x')) I|2 /o² with g based self-supervised
feature extractors such as SimCLR (Chen et al. 2020). The GCoverage and its estimator are
Ck. (S) : Ex max Ko (x, x':g) x'ES
max ko (xn, (x.:x' =; Ck, (8) with E U. (1) x'ES
#=1
MaxHerding greedily maximizes the estimated GCoverage: x* arg maX Ck (CU This a (1 approximation algorithm for optimizing the monotone submodular function Ck
Hybrid Methods These methods aim select informative yet representative data points. Nguyen & Smeulders (2004); Donmez et al. (2007) use margin- selection weighted by clustering scores. Settles & Craven 2008) weight uncertainty measures like entropy by cosine similarity. For neural networks, BADGE (Ash et al., 2020) uses k-means++ on loss gradient space, while ALFA- Mix (Parvanch et al. 2022) applics k-means to uncertain points based on feature interpolation.
Since uncertainty and reprrssentation-aasee active learning approaches behave differently in different budget regimes, SelectAL (Hacohen Weinshall 2024) and TCM (Doucet et al.. 2024) provide methods decide when to switch from low-budgen to high-budget methods. TCM provides some insights for a transition point, but their insights are based on extensive experimentation, and hard to generalize to different settings. SelectAL. was discussed in the previous section. In this work, propose a more robust approach with minimal re-training, covering continuous budget regimes.
Clustering in active learning k-means is widely used in active learning to promote diversity in selection. BADGE, ALFA-Mix, and Typiclust, for example, use k-means variants.
k-means centroids, however, do not in general correspond to any available point, and thus other methods (such as Typiclust's density criterion) must be used to choose point from cluster. It would be natural to instead enforce centroids to be data points, yielding k-medoids. The com- mon alternating update scheme similar to k-means often leads poor local optima (Schubert & Rousseeuw 2021). The Partitioning Around Medoids (PAM) algorithm (Kaufman & Rousseeuw 2009 Schubert Rousseeuw 2019 Schubert & Lenssen 2022) gives better clusters, but is much slower. MaxHerding selects points with essentially equivalent downstream performance as using the far more expensive Faster PAM algorithm (Schubert & Rousseeuw 202T) for GCoverage.
As we demonstrate empirically in Figure MaxHerding achieves significantly better performance than both k-mmans and k-means++ for active learning. Thus, in Section 3.4 we replace k k-means with MaxHerding for the theoretical analysis of some clustering based active learning methods.
METHOD
We introduce novel approach called Uncertainty Herding (UHerding), designed to "interpo- late" between the statc-of-the-art representation-bart based method MaxHerding and any choice of uncertainty-based method (e.g., Margin), providing effectiveness across different budget regimes.
Ithough we call the function h and use the term "kernel," it is not generally necessary that the function he positive semi-definite in kernel methods, nor that integrate as in kernel density estimation.
3

---

Published as a conference paper at ICLR 2025
5.00
Uiceratry
Selected
4.75
Selerted
4.00
(a) Comparison of ProbCover, GCoverage, and UCoverage.
(b) Temperature T, lengthscale a.
Figure 1: Left: illustration of coverages (Section 3.1
Right: parameter adaptation (Section) 3.2
3.1 UNCERTAINTY COVERAGE
We first define measure of how much uncertainty set of data points covers. Definition 1. For any subset S C X, nonnegative-valued function ko and nonnegative-valuee uncertainty function U, uncertainty coverage (UCoverage) is defined and empirically estimated
N
UCK,, (S) = Ex U(x; f) maxk, (x, (x,, x'E8
Σ n=1
U(xai f) max ko (x,, x':9) = =UCk. (S). x'E8
= N
Here, the uncertainty function U is based on a model f which is updated as the model trains, while ko uses fixed feature extractor g. UCoverage weights the GCoverage of ( with a choice of uncertainty measure Uxx; f); choosing [xxx = immediately recovers GCoverage.
In Figure la we visualize differences in assessing coverage. ProbCover (left) treats all data points within a o-radius ball around selected points equally, assigning uniform weight to each. GCover (middle) introduces a smooth proximity measure by applying kernel function, such as the RBF ker- nel, to weigh nearby points more effectively. UCover (right) additionally incorporates uncertainty. The green circles represent uncertainty, with their size proportional to each point's 's uncertainty. Ulti- mately, UCover evaluates how well the selected data points account for uncertainty across the space.
We now show UCk, is good estimator of UCK,- All proofs are in Appendix A
Theorem 2. Let U(x: f) [0, m. hig (x, gg) = kr (g(x))), g(x))) E [0, (g(x) E S (t Rd ||t|| < R), and (t, tt,
T. ||t' -tt''th t. Let L X be arbitrary and fixed. Assume B/N < 16R Then, with probability least 8 over the choice of the N iid data points in S X used to estimate UCK., all size-B sets (not only subsets of U)) have low error:
sup SCX [S
UCk, (CUS) UC,, (CUS) Umax
B N
8L + 2 ddlog
1
N R2
+
2
log
2
B
Since typically B < N wwe query up to perhaps a few hundred points at time, out of a dataset of at least tens of thousands but perhaps millions- even optimizing our noisy estimate of the uncertainty coverage does not introduce substantial error If U is given by the margin between probabilistic predictions, then Umax < 1; other notions can also be easily bounded. Assuming ko < for convenience, but a different upper bound can simply be absorbed into Umax- The bound is indeed for the Gaussian kernel on g used by Bae et al. (2024) (as well as by us); this kernel also has
Lo = V J. The kernel which corresponds to the probability coverage of Yehuda et al. 2022 however, is not Lipschitz, suggesting why it is so sensitive to a. Self-supervised representations in g are often normalized to R 1, and usually have d at most a few hundred.
(x, x': 9)) is in the form of ((((() g(x')
((x'')()'/)))))) 11/a))////)))/ ) [0, 1] for some function v and feature mapping g-
'It is worth emphasizing that, although Bae et al. 2004) mentioned simple Hoeffding bound for Cz, this
bound only applies to fixed S independent 2f while in reality S C U. Ignoring this problem and taking
union bound over all (?) subsets 2f would yield a uniform convergence bound of Unax V 2N log (()) 8) <
max
olg ())) + 1 log 2]. The rate of Theorem 2 EN
B
very similar, with the advantage of being correct.
4

---

Published as a conference paper at ICLR 2025
Algorithm 1: Uncertainty herding with parameter adaptation
Input: Initial labeled set Lo, Initial unlabeled set Ug. set of temperatures T, the number of iterations T, a of query budgets (B)) a classifier f. and feature extractor g
for t E [0, 10.., 1 1] do
// Parameter adaptation
Compute T" arg ei ECE(f"* ..(²)) where C and 2ia are random split from Ci, and fc: refers to classifier f trained on Ct
Compute k E [R with k, = maxx'et, Ko (Xn, x') for o* wen D(u, v:g) // Greedy selection based for b 21,2,- ... B,] do
the uncertainty coverage
Select x arg max 1 En U(Ini f+.). max (Xn, x) kn, 0)
N
, Vn E [24g] Update k., + max(ko (ko (Xn, x,),,,),
Update L(+1 Le U {xx (x 10=1 and U4+1 Ui fxF
3.2 PARAMETER ADAPTATION
We wish to choose parameters of UCoverage such that it smoothly changes from behaving like generalized coverage low-budget regimes to behaving like uncertainty in high-budget regimes.
Handling the low-budger case: calibration When [S] is small, we would like to roughly replicate GCoverage. We can do this by making our uncertainty function constant:
Proposition 3. If Vx E U,U (x: f) - C. where c 2 0, the estimated UCoverage UCk. (S) ap- proaches the estimated GCoverage Ck,(S)), up to a constant.
When |4] very small, our model is bad. Models with poor predictive power will generally have near- constatnt uncertainty if they are well-calibrated. We thus encourage calibration primarily through temperature scaling, a simple but effective post-hoc calibration method (Guo et al., 2017):
1. Split L, into Crain and Cral, and train a model f on Limin, obtaining fc
2. Choose 7 among some candidate set T minimize the expected calibration error (ECE
(Nacini et al. 2015) of the temperature-scalle
predictions f fxx)/T on C. where f(x)
R denotes logit vector with K being the number of classes.
3. Compute uncertainties with -*-scaled softmax: log Pr. (x) x (x) == f(x)/T".
The selected temperatures r" generally large when [C] is small and so f has poor predictions, which makes U (xx f) close to constant. As [C] increases and f's predictions improve, T" decreases (see Figure Tb. left panel), making uncertainty values more distinct.
Handling the high-budget case: decreasing a As [C] increases, the effect of single new data point on the trained model tends become more "semantically local," implying is reasonable to treat points as "covering" only closer and closer points in space by decreasing the radius a. As heuristic, we choose the radius to be the minimum distance between data points in the labeled set Z:
o² min viiinvved v. ugv (lg(u) - g(v)].. Since WI is bounded, as JL] grows we have that o* - (see Aepposittooneeentualll
applies, becoming incertainty-basee selection. Proposition 4. Suppose k. (x,''s g) = *b ((g(x) g(x)))/a) for a fixed g X + Rd which is injective U and function 2/ Id + [0, with (0) = 1 and for all t Rd with ||||| = 1, lima-100 (aatt = 0. Ifa + O, the estimated uncertainty coverage UC2, (8) approaches Σ E U(x;; f), up to constant.
Figure [b] right panel); thus
x':
As we shall see in Section 4.4 UCoverage with fixed t and a is not robust across budget levels, performing worse than MaxHerding in low-budget and worse than Margin in high-budget regimes. With our adaption techniques, however, UCoverage outperforms competitors across label budgets.
'ECE(J. D) = াo Σm= [Bm] |Ace(Bm. f) - Conf(Bn. f)] measures the difference between actual outcomes (Acc) and confidence (Conf) for model and dataset D. Bm is set of samples falling in bin m.
5

---

Published as a conference paper at ICLR 2025
1.5
Selections Seat Selections
Free Selectiies Seat Selections
Selections
1.0
Seat Selections
Foanre 2
0.5
0.5
Feannee 2
0.5
0.5
0.5
0.5
-1.0
-1.9
-1.0
1.0
0.5
0.0
0.5
10
1.5
20
1.0
0.5
0.0
0.5
1.5
2.0
1.0
0.5
0.0
0.5
1.0
1.5
200
Fenture
Feature
Fenture
(a) Margin
(b) MaxHerding
(c) UHerding
Figure 2: Comparison of Margin, MaxHerding and proposed UHerding on half-moon toy data.
3.3 UNCERTAINTY HERDING
To obtain an actual active learning method, we still need an algorithm to maximize UCK,, We could select batch by finding S E arg sax, UC2, UUU). This is equivalent the weighted kernel k-medoids objective, with weights determined by uncertainty Uxx f); thus, we could use Partitioning Around Medoids (PAM) KKaffman & Rousseeuw 2009) to try to find S.
Bae al. 2024 however, observed that with highly optimized implementation, this al- gorithm is much slower to optimize GCoverage than greedy methods, with little improvement in active learning performance. We thus focus on greedy selection, which we call Uncertainty Herding (UHerding) by analogy to MaxHerding (itself an analogy to kernel herding, Chen et al.) 2010).
Definition (Uncertainty Herding). To greedily add a single data point to a set L' = L. U. select
N
x" E arg max UCK, (8)) = arg max REU
U(xni
ft)
max XECUU(X
(x,s x':
(2)
REu
R=1
UHerding selects new batch S of size |S] by picking one point at a time to add to C'.
UHerding improves uncertainty measures by accounting for both the uncertainty of a selected point and its influence reducing nearby uncertainty. It improves on MaxHerding by incorporating uncertainty, putting less weight on covering already-certain points.
Corollary 6. In the setting of Theorem C. and UC* = =B UC (CUS) the optimal coverage obtainable among U. Then
2
let S C u be the result of UHerding for B steps to add to
UCK (CUS)
1 (1-2) uc - -2--)
(2-
U max
B N
8L
1 2\ d
112 N
2
log
Figure 2 visually compares the next selected data points (in red) by Margin, MaxHerding, and UHerding (using Margin uncertainty) on a two-class half-moon dataset represented by O and 4. A logistic regression model with fifth-order polynomial features is trained at each iteration, with the decision boundary after training on 12 previously selected points (in green) shown as dashed lines. As expected, Margin selects points near the decision boundary, which lead to suboptimal models the predicted boundary deviates from the true one. MaxHerding selects the most represen- tative points based on prior selections but ignores model predictions; this gives quick generalization with few labeled points, but performance saturates over time as it neglects points near the bound- ary. UHerding balances these approaches by initially selecting representative points and gradually focusing on uncertain points near the boundary, improving performance over time.
3.4 CONNECTION TO HYBRID METHOPS
UHerding is closely connected to existing hybrid active learning methods. As mentioned in Sec- tion 2 we replace k-means and k-means++ in various algorithms with greedy kernel h-medoids (MaxHerding) to simplify our arguments; this does not harm their effectiveness. We also apply a self-supervised feature extractor g instead of feature extractor from classifier f, since feature

---

Published as a conference paper at ICLR 2025
embeddings from g more informative when f is trained a small labeled Finally, we often assume that Kg is in fact a positive definite (RKHS) kernel; this is true for the kernels we use.
Proposition 7 (Weighted k-means of of/Zhdaoov 2019). Define an uncertainty measure (x; f) from another uncertainty measure Uxx f) as U(x U"(; f) (x;" 2 v/. where v 2 0 satis- fies En= A(0"(xmn f) v| M, pre-defined number. Then weighted k-means with uncertainty U", changed to use greedy kernel k-medoids, is UHerding with uncertainty U and the same kernel.
As shall see in Section UHerding significantly outperforms weighted k-means, indicating that is crucial to (a) convert k-means into MaxHerding and (b) apply parameter adaptation.
Proposition 8 (ALFA-Mix of Parvanch et 2022). Let ((: be the predicted label of an input under f. Define an uncertainty measure
f(x = 33 class s.t. ((a,(x) +1 (1-a + ū(g(x);
(3)
where g' is the mean of feature representations belonging to class j and aj az E 10. is the same parameter as determined by ALFA-Mix. Then ALFA-Mix, with clustering replaced by greedy kernel k-medoids, is UHerding with uncertainty U and the same kernel.
The equivalence of weighted k-means and ALFA-Mix to UHerding with the right choice of uncer- Jnd allso apply them. There is weaker connection to BADGE; UHerding and BADGE are not equivalent with any choice of uncertainty measure. How- ever, a variant of BADGE with greedy kernel k-medoids uses the kernel,
tainty measure implies that Propositions and
(x,.,, x') (g (('')((xx)))))))))
x': g)
(l )12 (Xn, X 9) ll ko (x'xx';;; (4)
where (xx = ix;; f) (x;; f) with ff being a classifier. This does satisty the following statement, showing properties similar to Propositions 3 and hold.
i then this BADGE ap- proaches a slightly modified MaxHerding: (1 [xxx; f)= (xx: - k) ko x':g) instead of ko (X,, x': g) a 0, it approaches the uncertainty-bused method where uncertainty is defined as, U (*) == ccu() (x0('': p(x'; f)l?
Proposition 9 (BADGE, Ash al. 2020)). If Vx u, p(x;
Using the parameter adaptation, hybrid methods can also smoothly interpolate between MaxHerding and uncertainty; Figure (6b) shows this improves BADGE. Although selecting data points maximizing U²(x) (x) is somewhat counter-intuitive, lowering still helps as it does not go too close to O.
4 EXPERIMENTS
In this section, we assess the robustness of the proposed UHerding against existing active learning methods for standard supervised learning (Sections 4. and 4.2) and transfer learning (Section 4.3) across several benchmark datasets: CIFAR10 (Krizhevsky) 2009), CIFAR100 (Krizhevsky et al. TinylmageNet (mnmoustafa 2017). ImageNet (Deng et al., 2009), and DomainNet (Peng et al., 2019). Section g.vegives ablation studies to see how each component of UHerding contributes.
Active learning methods We compare with several active learning methods listed below. We exclude ProbCover, its generalization MaxHerding reliably outperforms it (Bac et al. 2024).
Random
Uniformly select random B data points from 44
Confidence
Iteratively select x E arg min Pi (yy x), with pı the highest predicted probability.
Margin (Scheffer et al. 2007)
Iteratively select x² = arg mingeu (1y) - (22()) where P2 is
the second-highest predicted probability.
Entropy (ann & Shung 2014
Iteratively select x* arg max H(j(x) x x), where H(-) is
the Shannon entropy.
Weighted Entropy (Zhdanov
Select data points closest the centroids of weighted k-means using unlabeled data points with high enough margins (as in Margin selection above).
2019
BADGE (Ash et al. 2020) Select points with the l +-means++ initialization algorithm using gradient embeddings w.r.t. the weights of the last layer.
7

---

Published as a conference paper at ICLR 2025
Maxtlerding
Ullandig
Ufferding Ent.
Ulfending Cont
10
8-
(%)
6
4
2
-2
20
100
2010
300
400
500
600
700
800
900
1k
9k
10k
Low-Budget
Mid-Budget
High-Budget
Figure 3: UHerding versus MaxHerding and uncertainty, with different uncertainty measures. Mean and standard deviation of 5 runs of the difference between method and Random selection.
ALFA-Mix (Parvaneh et al.
2022) Select data points closest to the centroids of k-means only using uncertain unlabeled data points, based on feature interpolation.
ActiveFT Xie al. 2023
Select data points close to parameterized "centeroids," learned by min- imizing KL between the unlabeled set and selected set, along with diversity regularization.
Typiclust Hacohen al. a point with the highest "lypicality" using m-Nearest Neighbors.
2022) Run clustering algorithm, e.g., k-means. For each cluster, select
Coreset (Sener & Savarese
2018
Iteratively select points with the k-Center-Greedy algorithm:
arg maxxsu millx EC
X 2x
MaxHending (Bae al. 2024
Iteratively select points to maximize the generalized coverage
We always re-initialize models (cold-start). randomly or from pre-trained pa- rameters, after each round of acquisition, rather than warm-starting from the previous model (Ash & Adams 2020). We manually categorize the budget regimes into low, mid, and high for supervised learning, and low and high for transfer learning tasks. Representation- based methods win in low- budget regimes, while mncertaitty-bsse begin catch up mid-budget, and win in high-budget.
Implementation
4.1 UHERDING INTERPOLATES, AND THE UNCERTAINTY MEASURE DOESN'T MATTER
We first aim verify that UHerding effectively interpolates between MaxHerding and uncertainty measures across budget regimes. We train a randomly-initialin FAR1O using 5 random seeds, gradually increasing the size of the labeled set, as shown Figure We consider UHerding based Margin (Mar), Entropy (Ent.), and Confidence (Conf.). The y-axis of Figure represents AAc, indicating the performance difference relative to Random selection.
ResNet18 (He et al. 2016) CI-
UHerding performs slightly better comparably to MaxHerding in the low-budget regime, with a growing performance gap in the mid-budget regime, and substantial improvements in the high- budget regime. The opposite is true with uncertainty measures: UHerding substantially better with low budgets, while they eventually catch up and tie UHerding with high budgets.
The choice of uncertainty measure has little impact performance. We thus only Margin as the UHerding uncertainty measure in the future unless otherwise specified.
4.2 COMPARISON WITH STATE OF THE ART
We compare UHerding with state-of-the-art active learning methods, particularly hybrids. to assess their robustness across different budget regimes. Figure compares CIFAR100 and Tiny agenet, using 3 runs of randomly initialized ResNet18; CIFARIO results are in Appendix B
Overall trends are similar to before: representation- based methods are good with low budgets but lose the budget increases; incertainty-based and hybrid methods are largely the opposite. UHerd- ing with Margin uncertainty (UHerding Mar.) wins convincingly: no competitor ever outperforms UHerding, and for each competitor there is some budget where UHerdiig wins substantially.
8

---

Published as a conference paper at ICLR 2025
Random Margin
Entropy
BADGE ALFA-Mia -ix
Coreset Typiclust
MaxHerding UHleeding Mar.
Weighted k-Means
40
50
Acc (%)
20
10
40
200
400
600
1 S S
Low-Budget
Mid-Budget
High-Budget
(a) CIFAR100
20
10
30
Acc (%)
15
25
5
10
20
400
800
1.2k
1.6k
2K
9k
10k
Low-Budget
Mid-Budget
High-Budget
(b) TmnyImageNet
Figure 4: Comparison on CIFARI00 and TinyImageNer for supervised-learning tasks.
Stagg
BADGE ALFA Mia
Opidaa ALt
Madiodiaa
Mlinkag Mar
A Aec (%))
Acc (%6)
10-
200
400
600
At
1.4k
2.1k
2,8k
1k
48k
9.0k
10.3k
Low-Budget
High-Budget
Low-Budger
High-Budget
(a) CIFAR
(b) DomainNet
Figure 5: Comparison on CIFARI00 and DomainNet for transfer learning tasks.
4.3 COMPARISON FOR TRANSFER LEARNING TASKS
Fine-tuning foundation models to new tasks or datasets is of increasing importance. Inspired by ActiveFT Xie al. 2023), we compare UHerding to leading approaches for active transfer learning.
pre-trained on ImageNet (Deng et al. 2009 following Par- (023). We fine-tune the entire model, using DeiT Small for CIFAR- 100 and DefT' Base for DomainNet. Figure 3 compares UHerding with various active learning methods, including ActiveFT, which consistently underperforms the other methods likely due its design being optimized for single-iteration data selection. On CIFAR100, UHerding is comparable to representation- based methods in the low-budget regime but surpasses them by about 2% in the high-budget; it substantially outperforms uncertainty and hybrid methods in the low-budget regime and ties or wins with high-budgets. On DomainNet, UHerding outperforms MaxHerding by 1.5- 2% even in the low-budget. Compared to the best- test-performig hybrid method ALFA-Mix, UHerding wins by up to 13% with low budgets and performs similarly with high budgets.
We use DeiT Touvron et al. 2021)
vanch et al. (2022); Xie
is also common to fine-tune only the last few layers, especially in meta-learning Wang et al. 2019
Chen et al. 2019 Goldblum et al. (020)) and self-supervised learning (Chen et al. 2020 Caron et al. 2021). Similarly to Bae et al. (2024),
DINO (Caron al. 2021) features fixed through fine-

---

Published as a conference paper at ICLR 2025
Maga
ALZA-ba
Traida:
BADGE:
15
30
0 A.Acc (96
10-
Are (%))
40
20
30
17
20k
2/
6+
44
Low-Budget
High-Budget
Low to Mid-Budget
Mid High-Budget
(a) Transfer learning ImageNet
(b) Parameter adaptation on BADGE
Figure (Left) results on ImageNet for fine-tuning, (Right) application of parameter adaptation.
Low Tiny.
Middle
High
Method
C10
C100
Dom.
ImN.
C10
C100
Tiny,
C10
C100
Tiny.
Dom.
ImN.
Entropy
-1.8
-1.7
-0.6
-0.2
1.7
-1.6
-2.9
-1.7
2.2
-0.6
-0.7
0.7
1.2
Margin
-0.4
-0.3
-0.2
1.0
1.8
-0.1
-0.4
-0.3
2.5
1.5
BADGE
-0.5
-0.1
-0.2
1.4
2.0
0.6
-0.7
0.0
2.2
0.9
0.4
1.8
1.0
ALFA-M
0.1
0.9
-0.3
2.8
5.1
1.1
0.6
0.1
2.3
1.3
0.2
1.9
1.0
Weight.
-0.5
-0.1
-0.3
2.1
3.8
0.9
0.0
-0.2
1.8
0.8
0.3
1.7
0.8
Coreset
-2.7
-4.5
-1.4
-3,5
-6.6
-13
-11
-5.4
-10
-9.6
-5.5
-2.7
-12
ActivePT
0.0
Typiclust
3.7
3.3
1,6
3.1
4.9
4.9
1.8
2.1
-0.8
-0.1
0.3
-3.2
-9.9
MaxHerd.
5.0
4.1
2.1
6.2
10.6
6.2
2.8
1,9
0.1
-2.
-1.5
1.0
-1.2
UHerding
5.5
5.5
3.1
7.4
11.2
7.8
4.3
3.7
3.0
2.1
0.8
2.3
2.0
Table 1: Comparison of the mean improvemen//derraatioonn over Random selection on each budget regime and dataset. The first, second, third best results for each setting marked.
tuning: we train a head of three fully connected ReLU layers on ImageNet. Figure ba shows similar results, with UHerding consistently outperforming other methods across various budget regimes.
the results Sections 4.2 and 4.3 and Appendix reporting the mean improve- ment/degradation over Random for each budget regime UHerding wins across all budget regimes, while other methods have a significant range of budgets where they are worse than Random.
4.4 ABLATION STUDY
Figure graduually modifies BADGE to be similar to UHerding with Margin uncertainty on CIFAR- 100, replacing k-means++ with MaxHerding, then adding parameter adaption. Each step improves; so does the final step to UHerding, which changes the choice of uncertainty.
In Appendix C we analyze the contributions of each parameter adaptation component in UHerding. The baseline with fixed parameters performs slightly worse than MaxHerding at low- and mid- budgets, and worse than Margin at high-budgets. Adding temperature scaling results in notable improvements across all budget regimes, with further gains from incorporating radius adaptation.
CONCLUSION
In this work, we introduced uncertainty coverage, an objective that unifies low- and high-budget active learning objectives through smooth interpolation with adaptive parameter adjustments. We showed generalization guarantees for the optimization this coverage. By identifying conditions under which uncertainty coverage approaches generalized coverage and uncertainty measures, we made UHerding robust across various budget regimes. This adaptation also enhances an existing hybrid active learning method when similar parameter adjustments applied. UHerding achieves -fate-of-the-ar performance across various active learning and transfer learning tasks and, to our knowledge, is the only method that consistently performs well in both low- and high- settings.
"Tt is reported only for DomainNet (Dom.) and ImageNet (ImN.), is designed for fine-tuning.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported in part by Mitacs through the Mitacs Accelerate program, the Natural Sciences and Engineering Resource Council of Canada, the Canada CIFAR AI chairs program, and Advanced Research Computing at the University of British Columbia.
REFERENCES
Amin Aghaee, Mehrdad Ghadiri, and Mahdich Soleymani Baghshah. Active iistance-based clus- tering using k-medoids. In PAKDD, 2016.
Jordan Ash and Ryan P Adams. warm-starting neural network training. NeurIPS, 2020.
Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade. Gone fishing: Neural active learning with fisher embeddings. 2021.
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In ICLR, 2020.
Wonho Bac, Junhyug Noh, and Danica Sutherland. Generalized coverage for more robust low- budget active learning. In ECCV, 2024.
Erdem Bryik, Kenneth Wang, Nima Anari, and Dorsa Sadigh. Batch active learning using determi- nantal point processes. In NeurlPS, 2019.
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In ICCV, 2021.
Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. ICMI,, 2020.
Wei-Yu Chen, Yen-Cheng Liu, Zsolt Kira, Yu-Chiang Frank Wang, and Jia-Bin Huang. A closer look at few-shot classification. In ICLR, 2019.
Yutian Chen, Max Welling, and Alex Smola. Super-sample from kemel herding. In UAI, 2010.
Felipe Cucker and Steve Smale. On the mathematical foundations of learning. Bulletin of the American Mathematical Society, 2001.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In CVPR, 2009.
Pinar Donmez, Jaime G Carbonell, and Paul N Bennett. Dual strategy active learning. In ECML, 2007.
Paul Doucet, Benjamin Estermann, Till Aczel, and Roger Wattenhofer. Bridging diversity and un- certainty in active learning with self-supervised pre-training. In ICLR Workshop, 2024.
Alexander Freytag, Erik Rodner, and Joachim Denzler. Selecting influential examples: Active learn- ing with expected model output changes. In ECCV, 2014.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In ICML, 2017.
Micah Goldblum, Steven Reich, Liam Fowl, Renkun Ni, Valeriaa Cherepanova, and Tom Goldstein. Unraveling meta-learning: Understanding feature representations for few-shot tasks. In ICMI., 2020.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In ICML, 2017.
Yuhong Guo and Russell Greiner. Optimistic active-learning using mutual information. IJCAI, 2007.
11

---

Published as a conference paper at ICLR 2025
Guy Hacohen and Daphna Weinshall. How to select which active learning strategy is best suited for your specific problem and budget. In NeurIPS, 2024.
Guy Hacohen, Avihu Dekel, and Daphna Weinshall. Active learning on a budget: Opposite strategies suit high and low budgets. In JCML, 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR, 2016.
Christoph Käding, Erik Rodner, Alexander Freytag, and Joachim Denzler. Active and continuous exploration with deep neural networks and expected model output changes. In NIPSW, 2016.
Christoph Käding, Erik Rodner, Alexander Freytag, Oliver Mothes, Bjöm Barz, Joachim Denzler, and Carl Zeiss AG. Active learning for regression tasks with expected model output changes. In BMVC, 2018.
Leonard Kaufman and Peter Rousseeuw. Finding groups in data: an introduction to cluster anal- ysis. John Wiley & Sons, 2009.
Andreas Kirsch, Joost Van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In NeurIPS, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- (canadian institute for advanced research).
www.ttoroooo.oooooo..o www.rrontt..uuoriiii.... edw-/kriz/iiiarr html
Seong Min Kye, Kwanghee Choi, Hyeongmin Byun, and Buru Chang. Tidal: Learning training
dynamics for active learning. In ICCV, 2023.
David D Lewis and Jason Catlett. Heterogeneous uncertainty sampling for supervised learning. In Machine learning proceedings, 1994.
David D Lewis and William A Gale. A sequential algorithm for training text classifiers. In SIGIR, 1994.
Rafid Mahmood, Sanja Fidler, and Marc T Law. Low budget active learning via wasserstein distance: An integer programming approach. ICLR, 2022.
Mohammed Ali mnmoustafa. Tiny imagenet, 2017. URL https://kaggle: com/
compet: 1 wetottinniiinno wwwnnn--immmgeee magenett
Mohamad Amin Mohamadi, Wonho Bae, and Danica Sutherland. Making look-ahead active learn- ing strategies feasible with neural tangent kernels. In NeurIPS, 2022.
Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated proba- bilities using bayesian binning. In AAAI, 2015.
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions Mathematical Programming, 1978.
Hieu T Nguyen and Arnold Smeulders. Active learning using pre- vvecclustering In ICML, 2004.
Amin Parvaneh, Ehsan Abbasnejad, Damien Teney, Gholamreza Reza Haffari, Anton Van Den Hen- gel, and Javen Qinfeng Shi. Active learning by feature mixing. In CVPR, 2022.
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. ICCV, 2019.
Nicholas Roy and Andrew McCallum. Toward optimal active learning through monte carlo estima- tion of error reduction. ICML, 2001.
Tobias Scheffer, Christian Decomain, and Stefan Wrobel. Active hidden Markov models for infor- mation extraction. In ISIDA, 2001.
12

---

Published as a conference paper at ICLR 2025
Erich Schubert and Lars Lenssen. Fast k-medoids clustering in Rust and Python. Journal of Open Source Software, 2022.
Erich Schubert and Peter J Rousseeuw. Faster k-medoids clustering: improving the PAM, CLARA, and CLARANS algorithms. In Similarity Search and Applications: 12th International Confer- ence, SISAP 2019, Newark, NJ, USA, October 2-4, 2019, Proceedings 12, 2019.
Erich Schubert and Peter Rousseeuw. Fast and eager k-medoids clustering: O(k) runtime improve- ment of the PAM, CLARA, and CLARANS algorithms. Information Systems, 2021.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In ICLR, 2018.
Burr Settles. Active learning literature survey. University of Wisconsin-Madison Department of Computer Sciences, 2009.
Burr Settles and Mark Craven. An analysis of active learning strategies for sequence labeling tasks. In EMNLP, 2008.
Burr Settles, Mark Craven, and Soumya Ray. Multiple-instance active learning. 2007.
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers. & distillation through attention. In ICML, 2021.
Konstantin Voevodski. Maria-Florina Balcan, Heiko Röglin, Shang-Huu Hua Teng, and Yu Xia. Active clustering biological sequences. JMLR, 2012.
Dan Wang and Yi Shang. A new active labeling method for deep learning. IJCN,, 2014.
Yan Wang, Wei-Lun Chao, Kilian Q. Weinberger, and Laurens van der Maaten. Simpleshot: Revis- iting nearest-neighbor classification for few-shot learning. arXiv:1911.046233 2019.
Yichen Xie, Han Lu, Junchi Yan, Xiaokang Yang. Masayoshi Tomizuka, and Wei Zhan. Active finetuning: Exploiting annotation budget in the pretraining-finetunii paradigm. In CVPR, 2023.
Zhao Xu, Kai Yu, Volker Tresp. Xiaowei Xu, and Jizhi Wang. Representative sampling for text classification using support vector machines. In ECIR, 2003.
Ofer Yehuda, Avihu Dekel, Guy Hacohen, and Daphna Weinshall. Active learning through a cover- ing lens. In NeurlPS, 2022.
Fedor Zhdanov. Diverse mini-batch active learning, arXiv preprint arXiv: 2019.
Xiaojin Zhu, John Lafferty, and Zoubin Ghahramani. Combining active learning and semi- supervised learning using gaussian fields and harmonic functions. In ICML Workshop, 2003. 2003.
13

---

Published as a conference paper at ICLR 2025
A PROOFS
A.1 ESTIMATION QUALITY
Theorem 2. Let Uxx f) [0, Umal] to (x, x'ig) = (g(x)), [0, 11, (g(x): : x E EE) S
(t R2 ||t|| S RJ, and -o(t,t))ko(tte (t, S Lo |t'| Let L X be arbitrary and fixed. Assume B/N < 16R². Then, with probability at least 6 over the choice of the N iid data points in U C X used to estimate UCK,, all size-B sets S (not only subsets of () have low error:
sup SCX
UCk, (CUS) UCK, (CUS) < Umax|
B N
8h +
1 2V dlog
. R2
2
log
B
|
Proof. Rather than operating directly on S S X, we will operate on B-tuples T ( corresponding to
As these are ordered tuples, the mapping from T to S is many- to-one even if g is injective; if we prove convergence for all , it will necessarily prove convergence for all S. Define F(T)= = UC*,, (CUS) and ((T) = UC*, (CUS) for any S corresponding to that T; this is well-defined, since UC2, depends S only through {g(s) s É S).
Now, we will construct a vector space for elements T = (ti,..., tg). Vector addition and scalar multiplication
defined elementwise, and norm is defined as ||7| max([]tz]l || II), where ||t:]| is the standard Euclidean norm. This space is complete, and hence a Banach space of dimension Bd.
The uncertainty coverage F(T) is Lipschitz with respect to the Banach space norm:
(xx f)
max LE (x(()))XECUUT
Ko ())), ('E(o())XEC)LTT
max Koo (x()),t))
S [xU(x; f) max
Ric (g((), t.)) - (g(x),, E
iE[B]
S RxU(x; f) max Taz || t/1l
iE[B]
= L. (X: f)) IT- T-
The second inequality holds because the maximum function Lipschitz on R Specifically, let a1..... ON. .i.............................. d'y E R. and let î E arg maXne[N] an Then
max On max d, aú max d' S Og d/a S max On - d' S max |an - d'ul, NEN
72
ME[N]
nEN
NEN
and, symmetrically, is at least max |a, - d'y,, so |max, on - max, d'al S max, lan d'al-
As F exactly F with an empirical distribution for x, is Lo (N EN U(xx)) Lipschitz. We thus have
N s Lo ExU(x)+ N Σ U((x IIT n=1
(((T)
S 2L Umx IT IT-II--
By Proposition 5 of Cucker Smale (2001), we can cover the ball {T ||T||| < R} with at most (4R/r) Bd balls of radius 7) with respect to the metric ||T T'I.. So, to construct our covering argument, apply the (bidirectional) Hoeffding inequality the center of each of these balls, with failure probability 8/ (4R/n) Bd for each. Combining this with how much F f can change between an arbitrary point in {T || < R} and the nearest center, we have that for all r E (0, R), holds with probability least that
Bd
4R
sup F(T) - E(T) s 2L, Umaxc + U Umax
log
log
2.N
2N
8
The result follows by picking 17 = 4 B/N and using log(a) logg(?).
14

---

Published as a conference paper at ICLR 2025
A.2 PARAMETER ADAPTATION
Proposition 3. If Vx E u, (x; 1) + e where 2 O, the estimated UCoverage UCk. (S) ap-
proaches the estimated GCoverage Ck. (S), to a constant.
Proof. As (xx) + c.VX E X, the following equality holds:
lim -(
UCk,(S) lim ((x)~>c
Σ
(xx)) max to (x,, x'ES
U(x.) max kis (Xn; x') =c Ck. (S)- nml U(x.)
lim
x'ES
The last equality holds since each term with limit inside the converges to specific value.
Proposition 4. Suppose ko (x,x's g) = (b ((x))//) for a fixed g X + Ra which is injective on U and function sb IRd - [0, with (0) = 1 and for all 1 E Rd with If a - O, the estimated uncertainty coverage UCk, (S) approaches 6= Uxx;ff). up to constant.
||||| 1, lima-too (p(at)
Proof. As a + the function ki approaches to the following form: =
(x,,'') {
otherwise.
Then, have
(S) =
Σ
(x,)
max ki (x,x) x')
N
x'ES
n=1
[s|
Σ U(x.) 1[ E X, =x] x
U(x.)
N
Note that the indicator function is only x,, is equal to one of data points in S.
A.3 GREEDY ALGORITHM
Corollary 6. In the setting of Theorem let S L be the result of UHlerding for B steps to add to C. and UC" maxxcc4,$)=B UCR. (C S) the optimal coverage obtainable among U. Then
UCk, (CUS) 1 (1-1 UC (2 2 - (2-1)
1)
B N
1 8L
N R²
2
2
U maxx
2 d
log
B
Proof. First, UC*, is submodular by Lemma
10 Thus, if we let S E arg maxscu UCk. (S),
the classical result of Nemhauser et al. 1978) implies that US,,.() 2 (1 (1-1) UCR. (UC,..()) (S).
Let S* E arg max UCk, (S) the optimal size-B B subset of for UC*,, By definition, UC,,, (S) 2 UCr, (S*). Thus, calling the bound on the worst-case absolute error of the coverage estimate E, it holds with probability at least ö that
UC (S) CC (S) - = 1 (1-))
:) (S) (1- UCK, (2- E.
The following result guarantees that greedy optimization of UC2, or UC₁, achieves a (1 1/e) approximation, by Nemhauser al. 1978).
Lemma 10. For any fixed C, S + UC2, (CUS) and S + UC,, (C US) are nonnegative, sub- modular, monotone functions.
15

---

Published as a conference paper at ICLR 2025
Proof. We prove that UCoverage is non-negative monotone submodular for any set that contains the fixed set C: this implies that UCk, is as well, it is an instance of UC2, with an empirical distribution for x.
For Vx, x' X, we assumed that (xx 2 and Ko (x, x') 2 O. Thus, for any subset A C X,
UC (A) 2 O, which implies UCk, (C UUS) S) 2 O.
Next, we show monotonocity: VL C A c
X. UCR - UCk. (B).
JCk,(B) Ex (xx max li (x,,'')
x
max ko (x, max ti (x,, x') ] x'B
=Ex
(x) max
x'EA
2 (x) max Ko (x,x'). X'E
Lastly, we show submodularity: UC2, (AU (x}) UCR, (A) 2 UC,, (B) UC2, (B) for
JL AC B c X. Using monotonocity we showed, prove submodularity
UCR, (AU - UCR, (A) = Ex U(x) max
(x,
-max K (x, x'), x'EA
> Ex
U(x).
his (x,( -max K. (x, (x,,xx,)),) X'EB
UCk, (BU (x}}
UCR, (B).
A.4 CONNECTIONS TO HYBRID METHODS
Proposition 7 (Weighted k-means of Zhdanov 2019). Define an uncertainty measure U(x; f) from another uncertainty measure Uxx f) as f(x;))== (xx f) (fx; 2 vl. where v 2 0 satis- fies En= 1 f) 2 v| M, pre-defined number. Then weighted k-means with uncertainty U², changed use greedy kernel k-medoiss, is UHerding with uncertainty U and the same kernel.
Proof. With the modification of the k-means objective into a greedy kernel k-medoids objective, the objective of weighted k k-means with (x(x) as weights can be converted into:
N
x" E arg max (x) 2
v)
(xn)))
(1x(xx) - oxx') ''EU(())
min
(5)
REX
N
1
arg max XEX
U(xn)
min (l0(xn) - 6xx')l x'ECU(X)
(6)
N
n=1
arg max
Σ
U(x.)
max x'ECU(x)
lio (Xn,x')
XEX
This is equivalent to the objective of UHerding with Uxx) as the choice of uncertainty.
Proposition 8 (ALFA-Mix of Parvaneh et al. 2022). Let ((:f) f) be the predicted label of an imput under f. Define an uncertainty measure
f)x; 11 class s.t. + (1)) (x)));;
# (((()); f)]
where gi is the mean of feature representations belonging to class j and a (x) [0, 1) is the same parameter as determined by ALFA-Mix. Then ALFA-Mix, with clustering replaced by greedy kernel k-medoids, is UHerding with uncertainty U and the same kernel.
Proof. ALFA-Mix selects closest data points to the center of k-means clusters where k-means is fitted with filtered data points. It keeps a data point if it satisfies that 3 class j s.t. ((a((x) 9(x) (1 0z (x)) 93: f) # ū(g(x); f),, which we express the indicator function in Equation (3)
16

---

Published as a conference paper at ICLR 2025
Random Margin
Entropy Weighted k-Means
Coreset Typichast
MaxHerding
ALFA-MiX
UHerding Mar.
35
60
80
Ace (%)
30
50
25
40
70
20
30
60
20
40
80
100
200
300
400
500
600
700
800
900
1k
2
3
N
6
10k
Low-Budget
Mid-Budget
High-Budget
Figure 7: Comparison on CIFAR10 10 for supervised-leaming tasks.
With the replacement of k-means with greedy kernel k-medoids objective, the objective of ALFA- Mix can be converted into:
N f):
1
E arg max REX
max kis (X,: x'). x'ECU(8)
N
Proposition (BADGE, Ash et al. proaches a slightly modified MaxHerding:: (1 (0xxi f] (x': f F) ko x'; instead of ko (Xn, x'; :9)- I as, U" (x) == eonx 1Iú(x'; -(xx;; f)l2
2020). If Vx 1(x;
1T, then this BADGE ap-
0, it approaches the uncertainty-busse method where uncertainty is defined
Proof. Recall ((x) = ((x: (xx; f). As EU, p(x; i. is true that [1g(x) 1
and (g(x), q(x')) + [xx f) 0xx' f)] f R. With the assumption that Vx X, Ko (x,x::) =
1
Ko (Xn, x':9 2c (1 K
1
h(x,:x') + [[i(x>n;)) 3(x's))
(8)
K
Therefore, the following is true:
x E arg max REl
max
1((x,x)
N
XEEU(()
Σ
[[](xnn)) = 1 ko (Xn, x'ig).
arg max XEM
max X'ECU(X)
K
(10)
#=1
Ifo + 0, (x, g) = 1[x = x'). Then, maxxezu(x) /1(x,, x') + minxrecu(s) (1((x)))
[l((x')11 e 1|0(x's f)
p(x'; fl Then.
x" E arg max xell
max h(x,: x) EECUU()
(11)
==1
arg
min x'EC((R)
100'''; f) 5(x'; f)12
(12)
SEll
Therefore, BADGE approaches to arg max xeu (* as 0.
B ADDITIONAL COMPARISON WITH STATE OF THE ART
In addition to Figure where we compare state-of-the-art active learning methods on CIFARI00 and TinylmageNet datasets for supervised learning tasks, provide Figure for for additional results on CIFARIO dataset. Again, we employ a ResNet18 randomly initialized at each iteration.
Similar to the results CIFAR 100 and TinylmageNet datasets, UHerding significantly outperforms representation based methods in high-budget regimes, and uncertainty- based methods low- and mid-budget regimes, confirming the robustness of UHerding over other active learning methods.
17

---

Published as a conference paper at ICLR 2025
Marpi
Mactocin
URedlin Box
Kadin Adge.
Tenp, Saling
Beth
A.3c (%)
Acc (%6
Matted
100
200
500
<
60 9
1900
Low Budget
Budget
High Budpet
Size C
(a) Comparison with without components of parameter adaptation.
(b) Clustering methods
Figure 8: Comparison of some components in UHerding (Left) and clustering methods (Right)
C COMPONENT ANALYSIS OF UHERDING
In this ablation study, we examine the contribution of each component of UHerding to its overall generalization performance. Specifically, we incrementally add each of temperature scaling (Temp- Scaling) and adaptive radius (Radius Adap.) individually the UHerding baseline, which selects data points based solely the UHerding acquisition defined in Equation (2). We also evaluate the combined effect of both components. As in Section 4.1 we use CIFAR- 10 dataset, and present the results using AAcc relative to Random selection to clearly highlight the differences.
Although temperature scaling enhances performance over the UHerding baseline, its performance is still comparable to MaxHerding in the low-budget regime, and worse than Margin in the high- budget regime. Radius adaptation generally matches or exceeds MaxHerding across budget regimes but quickly converges Margin's performance in the high-budget regime. When both temperature scaling and radius adaptation are applied, performance surpasses both MaxHerding and Margin across all budget regimes, with saturation the high-budget regime occurring significantly more gradually than with radius adaptation alone. Please note that Margin's 's performance in the low- and mid- hid-budget regimes is not visible due to exceptionally poor results relative other methods.
D COMPARISON OF CLUSTERING METHODS
As noted in Section we compare several clustering methods applied to BADGE al. (220) to justify the replacement of k-means and k-means++ of existing active learning methods with Max- Herding. Figure 8b compares k-means, k-means++, k-medoids (iterative optimization). partition around medoids (PAM), and MaxHerding, a greedy kernel k-medoids. We train ResNet18 ran- domly initialized each iteration on CIFAR100.
Surprisingly, k-medoids performs slightly worse than h--mans, showing that searching for medoids not necessarily better than search of means. However, the gap between PAM and k-medoids shows that optimization methods do make significant changes. Although PAM works the best overall, MaxHerding comparable with much less computation Bae et al. (2024). It justifies the replacement of k-meaas and + with MaxHerding for existing active learning methods.
18


Reviews:
[{"review_id": "hPbwdtpgDJ", "reviewer": "Reviewer_hqBp", "summary": "This paper studies pool-based active learning by developing a unified approach that performs well in both low-budget and high-budget regimes. While uncertainty-based approaches typically work better with higher budgets and representation-based methods with lower budgets, the paper proposes an algorithm that adaptively interpolates between the two. This is achieved through greedily selecting data points based on a notion called uncertainty coverage, which incorporates uncertainty into a representation-based objective. Empirically, the paper shows that the algorithm achieves or exceeds state-of-the-art performance across budget regimes.", "questions": "- There is a discussion about discrete and continuous budget regimes in the comparison with SelectAL. In particular, it is mentioned that this paper cover continuous budget regimes. What do these regimes mean?\n- There isn't a formal definition of the kernel function $k$ outside Proposition 4. Do you need to assume that $k$ is in a particular form and has a \"spread\" parameter, $\\sigma$? Would the approach accommodate, e.g., polynomial kernel and sigmoid kernels? This is in reference to Definition 1, the discussion after Theorem 2, Algorithm 2, and the discussion before Proposition 4.\n- In equation (1), it would be helpful to clarify what $N$ is.\n- In Algorithm 1, what is ECE in line 2? Should $U(x_n)$ in line 5 be $U(x_n; f_{\\tau^*})$?\n- Can you elaborate on the computational complexity of Algorithm 1?\n- The notation in Proposition 3 can be confusing -- what does $U(x;f) \\rightarrow c$ exactly mean? Shouldn't $U(x;f)$ tend not to behave like constants as the model $f$ improves?\n- Regarding Section 3.4, would you argue that the framework presented in this paper generalizes some existing methods?\n- In Figure 3 (high-budget), why does the relative accuracy of UHerding drop as more labels are available?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem of navigating active learning strategies across budget regimes seems interesting and relevant to the field, as highlighted by recent work [Hacohen and Weinshall, 2023].\n\n- Balancing uncertainty and representativeness has been explored before in active learning, as discussed by the authors. The notion of uncertainty coverage introduced in this paper is built upon that of generalized coverage studied in [Bae et al., 2024] -- it is defined by weighting generalized coverage with the model's uncertainty. This idea is simple, intuitive, and seems versatile; the paper also briefly discusses connections to existing hybrid methods.\n\n- The proposed approach seamlessly interpolates between representation-based and uncertainty-based approaches, without relying on a fixed budget threshold to switch behaviors (cf., [Hacohen and Weinshall, 2023]). The practical algorithm is also supported by some theoretical evidence such as approximation guarantees.\n\n- The empirical validation of the algorithm demonstrates the interpolation, and the performance on various tasks/datasets seems promising across budget regimes.", "weaknesses": "- The theoretical results provide some insights but are primarily limited to a generalization guarantee for the empirical estimator of UCoverage and an approximation guarantee of the greedy algorithm. It would be interesting to see a deeper analysis that directly addresses the core goals in active learning, i.e., reducing error rates with as few labels as possible. For example, how does UCoverage perform as an objective in active learning in terms of *excess risk* and *label complexity* (potentially assuming oracle computation)?\n\n- There does not seem to be an empirical comparison with SelectAL and TCM.\n\n- The paper is generally well-written and easy to follow. However, there are a few ambiguities that may lead to confusion. For example, the term \"budget\" is never clearly defined, except in Algorithm 1, where $B$ is referred to as the budget. If this is the case, the discussion on parameter adaptation in Section 3.2 and parts of the experimental setup may be confusing, as the algorithm's behavior seems to depend on the current size of the labeled data rather than directly on $B$. Even if $B$ is small, $\\mathcal{L}$ still grows over time and can be large later on. This raises the question of whether the budget refers to the total number of labeled data over $T$ steps, which was not clarified. I will also outline additional questions in the following section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tVkuJ9vVTO", "reviewer": "Reviewer_jSMZ", "summary": "This paper introduces a novel active learning method called Uncertainty Herding (UHerding), which addresses challenges respect to label budget in active learning regimes. Traditional active learning methods often consider either low- or high-budget contexts but not both. This method bridges this gap by incorporating an uncertainty coverage objective, which generalizes both low- and high-budget objectives. This adaptive method achieves state-of-the-art results across various benchmarks, providing a reliable approach for tasks requiring both representation-based and uncertainty-based selection strategies.", "questions": "1. How sensitive is UHerding to changes in the adaptation parameters, particularly when applied to diverse datasets or models? Would a suboptimal parameter choice significantly affect performance?\n\n2. How well does UHerding perform in low-data or imbalanced data scenarios in practice, where pre-trained features may not fully capture distributional or distinguishable differences?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "UHerding successfully addresses both low- and high-budget scenarios in a unified approach, eliminating the need to switch frameworks and tackling the practical challenge of unclear budget boundaries. This method is also practical, as it doesn’t demand high training costs. This innovative approach is a strong contribution.\n\nThe paper provides rigorous theoretical analysis into the estimation quality and parameter adaptation of UHerding. Experiments span multiple datasets and scenarios, showing UHerding’s good performance compared to existing methods across various budget levels.", "weaknesses": "The method relies on having suitable pre-trained feature extractors and an accurate approximation of the data distribution, which might not always be feasible in real-world situations. \n\nWhile it shows strong performance in supervised tasks, its effectiveness in transfer learning could benefit from additional validation against approaches tailored to specific domains.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qknntQlkrN", "reviewer": "Reviewer_x6W9", "summary": "The authors propose a method to adapt to different budget levels in active learning. They theoretically prove that the proposed method achieves near optimal distribution level coverage. Empirically, they show that their method outperforms state of the art.", "questions": "can the authors make the legend in figure 1(a) larger and more readable?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical results provide insights into algorithm design, especially how to make proposed method robust across different budget levels.", "weaknesses": "in figure 5, there is a sudden increase in difference in accuracy from 7.2k to 8k budget. This increase applies to all methods and goes against the general trend observed in figure 5, 6, and 7. Could the authors provide some insight on why that may happen? A similar hikes happens in figure 6(a). \n\nI suspect this is due to the small amount of random seeds used. The error bars in figure 6(a) are quite high, and these hikes might be caused by an outlier point. Could the authors provide results for at least a subset of experiments with 10 or more random seeds and report the median? That may better illustrate the trend.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8qxjX48uT5", "reviewer": "Reviewer_DKgc", "summary": "This paper proposes an active learning method suitable for both low- and high-budget regimes. It defines an \"uncertainty coverage\" metric, estimated through its empirical counterpart. An uncertainty herding method is then introduced, based on the greedy optimization of this estimated uncertainty coverage objective. Numerical experiments are conducted within a transfer learning application.", "questions": "See weakness.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is largely well-written, with extensive discussions on the existing literature.\n- The numerical experiments are well-executed.", "weaknesses": "- The proposed method seems to rely more on a combination of heuristics and lacks guiding principles. Some analysis is also presented only in the asymptotic regime. In particular, Proposition 4 requires $\\sigma\\rightarrow 0$.\n- A more intriguing question is that the paper does not provide a detailed recipe for choosing the design or detecting whether the budget is high or low.\n- In terms of writing, although this paper builds on a line of literature, the exposition is far from self-contained; some notation and basic definitions are absent from Section 3.1.\n- Section 3.4 is poorly organized. Instead of simply citing lengthy theorems, it would provide more insights by including a coherent analysis and direct comparisons.\n- Figures 3 and 4: The plots use the same markers for different methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4D3hCsrHra", "reviewer": "Reviewer_Bjve", "summary": "This paper interpolates between the low-budget and the high-budget regime active learning (AL) by an objective called uncertainty coverage. The proposed algorithm Uncertainty Herding is a combination of the low-budget AL algorithm MaxHerding (Bae et al. 2024) and the classical uncertainty sampling in a way that the objective in MaxHerding is re-weighted by an uncertainty function. There are three improvements other than the objective: the temperature scaling (to weaken the effects of uncertainty functions when low-budget), the radius adaptation (to narrow down the coverage when high-budget), and the entropy regularization. The authors conduct experiments showing the superiority of the algorithm.", "questions": "1. The entropy-regularization: Is it just an engineering trick or a vital part of active learning? Would you mind conducting some further ablation studies, for example, combining entropy-regularization with other active learning algorithms (the MaxHerding and the margin-based uncertainty sampling)?\n2. The framework: This paper unifies other hybrid methods in the uncertainty coverage objective by choosing different uncertainty functions and kernels. Does this framework provide any (theoretical or empirical) insights into selecting the uncertainty functions or the kernels in practice?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The proposed algorithm is a natural interpolation between the low-budget MaxHerding and the high-budget uncertainty sampling. The authors provide a smart way (temperature scaling and radius adaptation) to decide each algorithm's proportion and also prove the equivalence in an asymptotic sense.\n2. The algorithm has reached a performance surpassing the existing benchmarks, especially the other attempts to interpolate between the low-budget and the high-budget regimes.\n3. The algorithm's computational burden is acceptable.", "weaknesses": "1. (Major) The implemented algorithm in the main experiments consists of three improvements compared to the naive Uncertainty Herding: the temperature scaling, the radius adaptation, and the entropy regularization. From my point of view, this paper's main contribution is giving a natural (and probably SOTA) interpolation between the low-budget and the high-budget AL regimes. In that sense, the first two terms seem very natural, yet the third term is unnatural and not analyzed in the paper.  On the one hand, the third term is important (and sometimes even critical) since the third term does boost the performance of the proposed algorithm. For example, in Appendix C, without entropy-regularization, the performance of Uncertainty Herding does not exceed uncertainty sampling in the high-budget regime. Intuitively, without that regularization, it would be weird that the algorithm (as an interpolation of the MaxHerding and the margin-based uncertainty sampling) outperforms both the MaxHerding and the margin-based uncertainty sampling in EVERY regime. However, the ablation study only considers adding entropy-regularization to the random sampling (passive learning). The authors make no attempts to explain or identify the effects of the entropy-regularization, which makes the logic incomplete.\n2. (Moderate) The theory part does not contain much contribution and novelty.\n3. (Moderate) There seem to be no descriptions of how the temperature scaling changes the uncertainty function. For example, the $f_{\\tau}$ function in Definition 5 is used without definition.\n4. (Minor) Figures in the main text are too small.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)