Querying Easily Flip-flopped Samples for Deep Active Learning
Authors: Seong Jin Cho
Gwangsu Kim
Junghyun Lee
Jinwoo Shin
Chang D. Yoo
Venue: ICLR 2024 poster (2024)
Keywords: active learning
uncertainty
closeness
disagree metric
diversity
Primary area: general machine learning (i.e., none of the above)
TL;DR: The uncertainty-based active learning algorithm that queries samples easily flip-flopped by a small perturbation of the decision boundary.

Abstract: Active learning, a paradigm within machine learning, aims to select and query unlabeled data to enhance model performance strategically. A crucial selection strategy leverages the model's predictive uncertainty, reflecting the informativeness of a data point. While the sample's distance to the decision boundary intuitively measures predictive uncertainty, its computation becomes intractable for complex decision boundaries formed in multiclass classification tasks. This paper introduces the *least disagree metric* (LDM), the smallest probability of predicted label disagreement. We propose an asymptotically consistent estimator for LDM under mild assumptions. The estimator boasts computational efficiency and straightforward implementation for deep learning models using parameter perturbation. The LDM-based active learning algorithm queries unlabeled data with the smallest LDM, achieving state-of-the-art *overall* performance across various datasets and deep architectures, as demonstrated by the experimental results.

Published as a conference paper at ICLR 2024
QUERYING EASILY FLIP-FLOPPED SAMPLES FOR DEEP ACTIVE LEARNING
Seong Jin Chol.2, Gwangsu Kim Junghyun Lee", Jinwoo Shin', Chang D. Yoo 'Department of Electrical Engineering, KAIST, "Korea Institute of Oriental Medicine, 3 Department of Statisties, Jeonbuk National University, "Kim Jaechul Graduate School of AI, KAIST {ipeng00, jh-1ee00, jinwoos, yd kai ac. s880120 jbnu. kr
ABSTRACT
Active learning, a paradigm within machine learning, aims to select and query unlabeled data to enhance model performance strategically. A crucial selection strategy leverages the model's predictive uncertainty, reflecting the informativeness of data point. While the sample's 's distance the decision boundary intuitively measures predictive uncertainty, its computation becomes intractable for complex decision boundaries formed in multiclass classification tasks. This paper intro- duces the least disagree metric (LDM), the smallest probability of predicted label disagreement. We propose asymptotically consistent estimator for LDM under mild assumptions. The estimator boasts computational efficiency and straightfor- ward implementation for deep learning models using parameter perturbation. The LDM-based active learning algorithm queries unlabeled data with the smallest L.M,, achieving state-of-the- overall performance across various datasets and deep architectures, demonstrated by the experimental results.
INTRODUCTION
Machine learning frequently necessitates the laborious annotation vast and readily available unlabeled datasets. Active learning (AL) (Cohn et al., 1996) addresses this challenge by strategi- cally selecting the most informative unlabeled samples. Within AL algorithms, uncertainty based sampling (Ash et al., 2020; Zhao al., 2021b; Woo, 2023) enjoys widespread adoption due to its simplicity and computational efficiency. This approach prioritizes selecting unlabeled samples with the greatest prediction difficulty (Settles, 2009; Yang et al., 2015; Sharma & Bilgic, 2017). The core objective of uncertainty-basse sampling lies in quantifying the uncertainty associated with each unlabeled sample for given predictor. plethora of uncertainty measures and corresponding AL algorithms have been proposed (Nguyen et al., 2022; Houlsby et al., 201 I; Jung et al., 2023): see Appendix for more comprehensive overview of the related work. However, many suffer from scalability and interpretability limitations, often relying on heuristic approximations devoid of robust theoretical foundations. This paper presents a novel approach centered on the distance between samples and the decision boundary.
Intuitively, samples closest to the decision boundary are considered most uncertain (Kremer et al., 2014; Ducoffe & Precioso, 2018) 2). Theoretically, selecting unlabeled samples with the smallest margin in binary classification with linear separators demonstrably leads to exponential performance gains compared to random sampling (Balcan et al., 2007; Kpotufe al., 2022). However, determining the sample-to-decision boundary distance is computationally infeasible in most cases, particularly for multiclass predictors based on deep neural networks. While various approximate measures have been proposed to identify such closest samples (Ducoffe & Precioso, 2018 8; Moosavi-Dezfool et al., 2016; Mickisch al., 2020), most lack substantial justification.
This paper proposes a paradigm shift in the realm of closeness measures. We introduce the least disagree metric (LDM), which quantifies a sample's closeness the decision boundary by deviating from the conventional Euclidean- based distance. Samples identified as closest based on this metric harbor the highest prediction uncertainty and represent the most informative data points. Our work presents the following key contributions:
"Corresponding author

---

Published as a conference paper at ICLR 2024
Definition of the LDM measure of sample's closeness the decision boundary.
Introduction an asymptotically consistent LDM estimator under mild assumptions and straightforward algorithm for its empirical evaluation, inspired by theoretical analysis. This algorithm leverages Gaussian perturbation centered around the hypothesis learned by stochastic gradient descent (SGD).
proposition of an LDM-based AL algorithm (LDM-S) showcasing state-of-the-ard overall performance across six benchmark image datasets and three OpenML datasets, tested over various deep architectures.
LEAST DISAGREE METRIC (LDM)
This section formally defines the concept of the least disagree metric (LDM) and proposes asymp- totically consistent estimator for its calculation. Drawing inspiration from a Bayesian perspective, we present practical algorithm for the empirical evaluation of the LDM.
2.1 DEFINITION OF LDM
Let X' and y be the instance and label spaces, respectively, with J 2 2, and H. be the hypothesis space, encompassing all possible functions X' V. Let D be the joint distribution over X' y, and Dx be the marginal distribution over instances only. The LDM is inspired by the disagree metric introduced by Hanneke (Hanneke, 2014). The disagree metric between two hypotheses h1 and h2 is defined as follows:
(1) where I Px is the probability measure X' induced by Dx. For given hypothesis g E and Zo E X, let H == {h H. h(xo) * {( be the set of hypotheses disagrecing with g in their prediction for Zu. Based on the above set and disagree metric, the LDM of sample to a given
p(h, h2) PX- [h (X) * h2(X))
hypothesis is defined as follows:
Definition 1. For given g H. and æo E X, the least disagree metric (LDM) is defined as p(h, .))..
L(g, wo) = inf
bEHo.
Throughout the paper, assume all the hypotheses belong parametric family, and h, identified by w, u IRP, respectively.
To illustrate the LDM concept, we consider two-dimensional binary classification with a set of linear classifiers defined as
X
plho. 1, 0.00000 B (-n,m)
hdo
H {h: h(x))= sign(x' (wTw), w R²²
where x is uniformly distributed on X' {a | < 1} IR.. Let he be hypothesis cor- responding to a decision boundary forming an angle 0 E (-7r, T) (in radians) with the decision boundary g. then we have that p(hg.g) = For given g and wo. let dg (0, $ be the gle between the decision boundary of g and the line passing through Eg. then Ha. {ho 0 E (-m,- ++) U (fu, :) see Figure Thus,
Origin
(ho O (-x, +x) (0o.
[00]
L(g, [g)
inf huEHtin
e (ho.g)
Figure 1: An example of LDM of æo for given in binary classification with the linear classifier. Here is uniformly distributed on X' C IR.. The he disagrees with y for To when 0 < +0 or 0g 00 thus L(g. x = inff p(h.. g) = [0ol
L(g. 2o) = in p(he. 9) [co1
Conceptually, a sample with a smaller LDM signifies that its predicted label can be more easily flip-flopped by a minimal perturbation the decision boundary. Suppose we draw a hypothesis h with its parameters sampled from a Gaussian distribution centered at the parameters of g (i.e.,
(N, Io then it is expected that Pw (h((2) A 9(x22)
L(g. x1) < L(g. x2) + P.,. [f(2)) # g(x;)] > P.
The sample with the smallest LDM is the most uncertain and, thus, most informative. The theoretical justification for this intuition is established specifically for wwo-dimensional binary classification with linear separators. Additionally, empirical verification is provided on benchmark datasets utilizing deep networks (see Appendix C.
2

---

Published as a conference paper at ICLR 2024
2.2 AN ASYMPTOTICALLY CONSISTENT ESTIMATOR OF LDM
In most cases, LDM is not computable for the following two reasons: 1) is generally intractable, especially when Dx and h both complicated, e.g., neural networks over real-world image datasets, and 2) one needs to take an infimum over H. which is usually an infinite set.
To address these issues, we propose an estimator for the LDM based on the following two approx- imations: 1) IP in the definition of p is replaced by an empirical probability based on M samples (Monte-Carlo method), and 2) H is replaced by a finite hypothesis set Hy of cardinality N. Our estimator, denoted by LN, (g. Zo), is defined as follows:
{pu (h. -
{
Σ [((()))) + o(x.) M
1
Lg.M(g. xo)
inf NEH
(3)
where H == (h Hy h E Ho.m), ). [[-] is an indicator function, and X1,..., Xas s.i.d Dx- Here, M is the number Monte Carlo samples for approximating p. and N is the number of sampled hypotheses for approximating L.
critical property of estimator is (asymptotic) consistency, i.e., in case, want the LDM estimator to converge in probability to the true LDM as M and N increase indefinitely.
We start with two assumptions on the hypothesis space H and the disagree metric pt Assumption 1. H. is Polish space with metric dx(.-.).
This assumption allows us to avoid any complications that may arise from uncountability, especially as we will consider probability measure over H: see Chapter 1.1 of der Vaart & Wellner (1996). Assumption 2. :( is B-Lipschitz for some B O, i.e, p(h,g) < Bdx (h, vh, g E H.
If p is not Lipschitz, then the disagree metric may behave arbitrarily regardless of whether the hypotheses are "close" or not. This can occur in specific (arguably not so realistic) corner cases, such as when Dx is a mixture of Dirac measures.
From hereon and forth, we fix some E D and By E X.
The following assumption intuitively states that Hy is more likely to cover regions of H. whose LDM estimator is E-close to the true LDM, as the number of sampled hypotheses N increases.
fintimmiiiiiiicniiiiiii Assumption 3 (Coverage Assumption). There exist two deterministic functions a N x R20 - Rzo
and B N + R- that satisfies N o<(N,e) = limn-soo B(N) = 0 for any e E (0, 1), and
P
inf =H Lo(h .) Ss
min du ,h) - B (N.,e) NE
21 21-B B(N), Ve E (0. 1),
(4)
where we recall that H9.20 (h E H h(x))) g(xo))
Here, we implicitly assume that there is a randomized procedure that outputs sequence of finite sets Hi S H2 S ... C H. a(N, e) is the rate describing the optimality of approximating H using Hy in that how close is the e-optimal solution is, and B(N) is the confidence level that converges to 1.
In the following theorem, whose proof is deferred to Appendix B, we show that our proposed estimator, IN,M, is asymptotically consistent:
Theorem 1. Let g E H. No E X, and 8 > 0 be arbitrary. Under Assumption 2, and 3, with M > (CNN, we have that for any E 10,
1
P [[LN, an) - L(g, mo0 < 28 a(N,)) + +c)21=
CN - B(N).
Furthermore, (nin(M,N) - x with M = w (log(CN)), we have LN, (g, xo) Es L vo)-
'The usual measurability useful properties may not hold for non-separable spaces (e.g.. Skorohod space).
For the asymptotic analyses, we write f(n) = w(g(n)) lim 9(z)
f(n)
3

---

Published as a conference paper at ICLR 2024
For our asymptotic guarantee, require M w(log(CN)), while the guarantee holds w.p. at CN 3(N). For instance, when ((N) scales as 1/N, the above implies that when N scales exponentially (in dimension some other quantity), the guarantee holds with overwhelming probability while M only needs to be at least scaling linearly, i.e., M needs not be too large.
least - 1
One important consequence is that the ordering of the empirical LDM is preserved in probability:
Corollary 1. Assume that L(g, x.) L(g, Under the same assumptions as Theorem I, the following holds: for any E > O,
lim min(M,N)-+s
P P[LN,M(9, (N, + +e]=0, =0,
where we again require that M w (log(CN)).
2.3 EMPIRICAL EVALUATION OF LDM
Motivation. LDM estimator requires Assumption 3 to hold for asymptotic consistency. This ensures that with a sufficiently large number of samples (N - oc), the constructed hypothesis hypothesis. We employ Gaussian set has a high probability of "covering" the true LDM- sampling around the target hypothesis to construct a finite collection of hypotheses HN to achieve this coverage. Appendix C.3 formally demonstrates that this approach satisfies Assumption in the context of 2D binary classification with linear classifiers.
Remark 1. It is known that SGD performs Bayesian inference (Mandt el al., 2017; Chaudhari & Soatto, 2018; Mingard el al., 2021), i.e., g can be thought of as a sample from a posterior distribution. Combined with the Bernstein-von Mises theorem (Hjort et al., 2010), which states that the posterior of a parametric model converges to a normal distribution under mild conditions, Gaussian sampling around g can be thought of sampling from a posterior distribution, in informal sense.
Algorithm Details. Algorithm provides a method for empirically evaluating the LDM of æ for given g. When constructing the hypothesis set, we utilize a set of variances {o k=1 such that Jk < 0k+1- The choice motivated by two key considerations. If o² is too small, the sampled unlikely to satisfy h(x)) A g(ar), which is required for LDM estimation. Conversely, excessively large o² can lead to h too far from when the true LDM is close to O. Both observations are based on the intuition that larger x² implies a greater p(h, g). Appendix C.2 formally proves that for 2D binary classification with linear classifiers, [p, (h. 9)] is monotonically increasing with respect to o². We also provide empirical evidence supporting this observation in more realistic scenarios. The algorithm proceeds as follows: For each k, sample h with w ~ N(v, lof). If h(x)) + g(z), update La as min ( LL, PM (h, g)}. If L. remains unchanged for s consecutive iterations, move on k 1. Continue iterating while k < K.
Small is Sufficient. Choosing an appropriate s remains an open question. While small suffices for accurate LDM estimation in the context of binary classification with the linear classifier depicted in Figure/ 1, deep architectures might require a larger 8 to ensure convergence of the estimated LDM. However, employing large increased rumtime associated with sampling a larger number of hypotheses. Fortunately, our empirical observations across various reveal that the rank order of LDM across different samples remains consistent. This quantified by a high rank-correlation coefficient close to 1. Since the L.DM-based active learning algorithm described in Section 3 leverages only the relative ordering of LDM for sample selection, a small is sufficient for practical purposes. Detailed experimental results and further diseussions regarding the impact of the s are provided Appendix F.I.
be computationally expensive due to the significantly
LDM-BASED ACTIVE LEARNING
This section introduces the LDM-based batch sampling algorithm (LDM-S) for pool-based active learning. In pool-based active learning. we given a set of unlabeled samples denoted by U. The goal is to select a batch of q informative samples for querying from a randomly sampled pool P C U of size
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 Empirical Evaluation of LDM
Algorithm Active Learning with LDM-S
Input:
Input:
w: target sample
Co. Uu Initial labeled and unlabeled samples
larget hypothesis parameterized by o
m, 9: pool and query size
M: number of samples for approximation
T: number of acquisition steps
{o k= set of variances
s: stop condition for parameter sampling
for = 0 T do Obtain v by training on Lt Randomly sample P C 24, with [P] m
La =1
for = 1 to K do c 0
Evaluate La of x: C P for by Algorithm
while < do
Compute " using Eqn. 5
Sample h with u ((v, Io
21 - {x1} where œ1 arg min EeP Le for n. = 2 to do
c c=c+ c+1
if h(x))))))))))())) # ((z) and La > Peo (h,9) 9) then
= milaa 6n-1 dece #xo)
La + PM (h,
Sample æ, E P w.p. P(arn) = En, ex Vaz
Pen
c=0
end if end while
+ Q (#m)
end for
end for return: Loe
C.+1 + (.),,,,,, U4t c u,
end for
3.1 LDM-SEEDING
A naïve approach for LDM-based active learning would be to select the y samples with the smallest LDMs (most uncertain). The effectiveness of L.DM-based active learning is shown Figure 2 of Section 4.1. However, Figure 3 of Section 4.2 demonstrates that this strategy may not yield optimal performance since selecting samples solely based on LDM can lead to significant overlap in the information content of the chosen samples. This issue, referred to sampling bias, is common challenge in incertainty-base active learning approaches (Dasgupta, 2011). Several methods have been proposed to mitigate sampling bias by incorporating diversity into the selection process. These methods include k-means++ seeding (Ash et al., 2020), submodular maximization (Wei et al., 2015), clustering (Citovsky al., 2021; Yang et al., 2021), joint mutual information (Kirsch et al., 2019).
This paper adopts a modified version of the k-means++ seeding algorithm (Arthur & Vassilvitskii, 2007) to promote batch diversity without introducing additional hyperparameters (Ash et al., 2020). Intuitively, +-means++ seeding iteratively selects centroids by prioritizing points further away from previously chosen centroids. This method naturally tends to select a diverse set of points. LDM- Seeding employs the cosine distance between the last layer features of the deep network as the distance metric. This choice is motivated by the fact that the perturbation is applied to the weights of the last layer and that feature scaling does not affect the final prediction.
LDM--eeding balances selecting samples with the smallest LDMs while achieving diversity. This is achieved through modified exponentially decaying weighting scheme inspired by the EXP3 algorithm (Auer et al., 2002). This type of weighting scheme has proven successful in various active learning (Beygelzimer et al., 2009; Ganti & Gray, 2012; Kim & Yoo, 2022). To balance the competing goals, P is partitioned into Pg and Pa where Pa contains samples with the smallest LDMs and P. P P... The total weights assigned to Pg and Pe are set to be equal. For each sample P,, let L, max=eP, Las then the weight 7n2 is calculated using the following equation:
(In Lg)
ELEP,
1/22
Ln
where i E cJ denotes the partition index and (-) = max{0.
L.DMSSeeding starts by selecting unlabeled sample with the smallest LDM from P. Subsequently, it employs the following probability distribution to choose the next distant unlabeled sample:
IP En,ep 12
* min (Ze, Zx.) ''EQ
(6)
where Q is the set of selected samples, and zn. Zg' are the features æ, x'. respectively. This probability distribution explicitly incorporates both LDDM and diversity.
5

---

Published as a conference paper at ICLR 2024
Entropy samp (Step
LDM Entropy
(Step
MNIST GCI-150 Q-220
Random
Random
90-
LDM Rancom
11 16 samples
26
(a)
Figure 2: The comparison of selecting sample(s). The black crosses and circles are labeled, and the gray dots are unlabeled samples. (a) Selected samples by LDM-based entropy- and random sampling binary classification with the linear classifier. number of labeled samples. (c) The t-SNE plot of selected batch samples in 3-class classification with deep network on MNIST dataset.
(b) The test accuracy with respect to the
3.2 LDM-S: ACTIVE LEARNING WITH DOM-SEEDING
We now introduce LDM-S in Algorithm 2, the LDM-based seeding algorithm for active learning. Let C, and U, be the set of labeled and unlabeled samples at step respectively. For each step t, the given parameter v is obtained by training on Lt, and the pool data P C C of size m is drawn uniformly at random. Then for each æ E P. T for given v and "/m are evaluated by Algorithm 1 and Eqn. 5, respectively. The set of selected unlabeled samples, 21. is initialized as {x1) where 2i arg = Lx- For Eqn. and appends it to 2.. Lastly, the algorithm queries the label y, of each E; E Qg. and the algorithm continues until = T
2, ................................ .. q. the algorithm samples In, E P with probability P(x) in
EXPERIMENTS
This section presents the empirical evaluation of the proposed LDM-based active learning algorithm. We compare its performance against various uncertainty- -aaed active learning algorithms diverse datasets: 1) three OpenML (OML) datasets (#6 (Frey & Slate, 1991), # 156 (Vanschoren et al., 2014), and #44135 (Fanty & Cole, 1990)); six benchmark image datasets (MNIST (Lecun al., 1998), CIFAR1O (Krizhevsky, 2009), SVHN (Netzer et al., 201 1), CIFAR 100 (Krizhevsky, 2009), Tiny ImageNet (Le Yang, 2015), FOOD101 (Bossard al., ()) and ImageNet (Russakovsky et al., 2015). We employ various deep learning architectures: MLP, S-CNN, K-CNN (Chollet et al., 2015), Wide-ResNet (WRN-16-8: Zagoruyko & Komodakis (2016)), and ResNet- 18 (He et al., 2016). All results represent the average performance over 5 repetitions (3 for ImageNet). Detailed descriptions of the experimental settings are provided in Appendix D. The source code is available on the authors' GitHub repository
4.1 EFFECTIVENESS OF LDM IN SELECTING (BATCHED) UNCERTAIN SAMPLES
To gain insights into the functionality of LDM, conducted a controlled active learning experiment under a scenario where the true LDM is readily measurable. We employed a two-dimensional binary classification with 7/ {h (x) Ii (x) > 0.5] where Lu (z) := 1/(1 + e (o)))),, R² the parameter of h, and æ is uniformly distributed on X' {x : ||~:|| S 1} C T... Three initial labeled samples are randomly chosen from each class. For each step, one sample is queried. LDM- based active learning (LDM) is compared with entropy-based uncertainty sampling (Entropy) and random sampling (Random). Figure 2a shows the selected samples by each algorithm. Black crosses and circles denote labeled samples, while gray dots represent unlabeled samples. Both LDM and Entropy select samples close the decision boundary. Figure 2b shows the average test accuracy over 100 repetitions for each algorithm, plotted against the number of labeled samples. LDM performs similarly to Entropy, both significantly outperforming Random. This observation aligns with the
httpp:://gi thub. wtt.:/ccm///////eeeeeeee cwwppcc//mpccga///0 000e000/1/i0
1IMM- /

---

Published as a conference paper at ICLR 2024
1on
2.25
2,50
1./5
1.50
1.00
(a)
(b)
WHIST (C 1000
MUIST (10 1et batch)
WUIST 1e0 batch)
0:40
0.35
0:30
0.5
pot O9t banch
20
30 6-th batch
(d)
(e)
(I)
Figure 3: The improved test accuracy by labeling the hth batch of size q from pool data sorted in ascending order of LDM when the number of labeled samples is 100 (a) or 300 (d), and t-SNE plots of the first and eighth batches for each case (b-c, e-f) MNIST.
theoretical understanding that entropy is strongly decreasing function of the distance to the decision boundary in binary classification. Consequently, both LDM and entropy-based algorithms effectively select the sample closest to the decision boundary, mirroring the behavior of the well-established pargin-based algorithm. Furthermore, we compared the batch samples chosen by LDM. Entropy, Coreset, and Random in a 3-class classification task using deep network on the MNIST dataset. Figure 2c shows the t-SNE plot of the selected samples. Gray and black points represent pool data and labeled samples, respectively. The results show that LDM and Entropy select samples close to the decision boundaries, similar to the two-dimensional case. Coreset, on the other hand, selects a more diverse set of samples. For further analysis, the authors conducted additional experiments: 1) investigating the impact of varying batch sizes (Appendix F.3); 2) Evaluating the effectiveness of LDM without using it for seeding (Appendix F.2); 3) Comparing the performance of LDM with other uncertainty measures in the context of seeding algorithm. (Appendix G. These additional experiments further substantiate the effectiveness of the newly introduced LDM for active learning.
4.2 NECESSITY OF PURSUING DIVERSITY IN LDM-S
Here, we investigate the potential drawbacks of solely relying on the smallest LDM values for sample selection, thus why we need to consider diversity. We query the 4 batch of size q = 20 from MNIST pool data sorted in ascending order of their LDM values and compare the improvements accuracy. Figure 3a shows that selecting samples with the smallest LDMs initially leads to the best performance, but Figure 3d shows that prioritizing the smallest LDMs may not lead to the optimal performance. To understand this difference, visualize the distribution of the selected samples using t-SNE plots (van der Maaten & Hinton, 2008) for each case. Figure 3b-3c show the t-SNE plots for the first and eighth batches, respectively, when 100 samples are labeled. Both plots display a well-spread distribution of selected samples, implying minimal overlap in information content between subsequent batches. Figure 3e-3f show the t-SNE plots for the first and eighth batches, respectively, when 300 samples are labeled. The samples exhibit significant overlap in the first batch, indicating redundant information. In contrast, the eighth batch, comprising samples with larger LDMs, demonstrates a more diverse spread. Based on these observations, we conclude that diversity within the selected samples is crucial in achieving optimal performance. Even in LDM-based selection, incorporating diversity considerations during batch selection becomes essential. Appendix C.4 delves deeper into this phenomenon through a geometrical interpretation of 2D binary classification with linear classifiers.
test
7

---

Published as a conference paper at ICLR 2024
LI3--5 S
Randl
Endropy
girgin
Coremet
ProbiC.o
DIAL
BADGE
Dolan-More curve
1.0
LDM-5
0.0
6.0
5.6
2.2
5.9
4
2.3
2.6
0.0
Entropy
0.0
3.3
0.0
0.0
4.2
1.3
1.1
0.0
0.0
Rx65
0.6
LDM-S:
Coresct
Margin
0.0
1.7
4.5
1.9
0.2
0.0
0.7
3.0
0.5
0.7
2.6
0.1
ALC=2.81 87
0.4
Margin; AUC-1,89
ProbCov
0.0
3.1
2:8
0.3
4.5
0.0
2.1
0.6
Coresct: AUC-22
ProbCov: AUC-2.95
DBAL
3.7
1.4
0.0
0.1
0.2
ENS, AUC-3.82
ENS
0.0
4.3
2.2
0.2
5.5
2.6 2.6
0.0
0.5
BADGE, AUC=3391
0.0
3.1
2.5
0.3
1.2
1.0
19
0.6
0.7
(a)
(b)
Figure 4: The performance comparison across datasets (a) Dolan-Moré plot among the algorithms across all experiments. AUC is the area under the curve. (b) The pairwise penalty matrix over all experiments. Element P., corresponds roughly to the number of times algorithm i outperforms algorithm j. Column-wise averages at the bottom show overall performance (lower is better).
4.3 COMPARING LDM-S BASELINE ALGORITIMS
We now compare the performance of the proposed LDM-S with various baseline AL algorithms.
Baseline algorithms Each bascline algorithm is denoted as follows: 'Rand': random sampling, 'En- tropy": entropy-based uncertainty sampling (Shannon, 1948), 'Margin': margin-based sampling (Roth Small, 2006), 'Coreset': core-set selection (Sener & Savarese, 2018), 'ProbCov': maximizing prob- ability coverage (Yehuda et al., 2022), 'DBAL': MC-dropout sampling with BALD (Gal et al., 2017), 'ENS': ensemble method with variation ratio (Beluch et al., 2018), 'BADGE': batch active learning by diverse gradient embeddings (Ash et al., 2020), and 'BAIT": batch active learning via information metrics (Ash et al., 2021). We use 100 forward passes for MC-dropout in DBAL and an ensemble of 5 identical but randomly initialized networks for ENS. DBAL can not be conducted on ResNet- 18, and BAIT can not be conducted with our resources on CIFARIO0, Tiny ImageNet, FOOD101, and ImageNet due to their significantly higher runtime requirements. We set 10, M to be the same size as the pool size, and d = 100k-5 for LDM-S where 8 = 0.1 and k E (1,2, ... .5))) in convenient (see Appendix F.4).
Performance comparison across datasets The performance profile (Dolan & Moré, 2002) and penalty matrix (Ash et al., 2020) are utilized for comprehensive comparisons across all datasets. The details of the performance profile and penalty matrix are described in Appendix E. Figure 4a shows the performance profile of all algorithms with respect to ó. LDM-S consistently maintains the highest R (6) across all considered 8 values. Notably, RLDM-S(0)) of other algorithms (all below 15%). Figure 4b further supports LDM-S's superiority. In the first row, LDM-S outperforms all the other algorithms, often with statistically significant margins (Recall that the largest entry of the penalty matrix is 9, the total number of datasets). Similarly, the first column shows that no other algorithm consistently outperforms LDM-S across all runs. Finally, the bottom row confirms that LDM-S achieves best performance.
35% significantly exceeding the values
Performance comparison per datatset Table presents the mean and standard deviation of perfor- mance differences (relative to Random) averaged over repetitions and steps. Positive values indicate better performance than Random, and asterisks (*) denote statistically significant improvements based on paired t-tests. We observe that LDM-S consistently performs best or is comparable to other algorithms across all datasets. In contrast, the effectiveness of other algorithms varies significantly depending on the dataset. For instance, Entropy and Coreset underperform on OpenML, MNIST, CIFAR10, and SVHN compared to LDM-S. Margin performs well on smaller datasets but deteriorates on larger ones. ENS, ProbCov, DBAL, BADGE, and BAIT generally underperform compared to LDM-S. Detailed test accuracy values for each dataset provided in Appendix G.3.
8

---

Published as a conference paper at ICLR 2024
Table The mean + standard deviation of the repetition-wise averaged performance (test accuracy) differences (%), relative to Random, over the entire steps. The positive value indicates higher performance than Random, and the asterisk (*) indicates that p 0.05 in paired sample t-test
between LDM-S and others. (bold-underlined: best performance, bold: second-best performance)
LDM-S
Entropy
Margin
Coreset
ProbCov
DBAL
ENS
BADGE
BAIT
OML#6
4.76x0.6
2.4610.70
2.124
1.14
4.
0. 0.10aa.22*
4.43a0.31
2.98,0.28*
2.37.0.30
OML#156
1.18
-1.29
0.64s0.39
-19.53e..2
-0.08
0.61=035
1.06#0.39
-7.66x1.12
OML#44135
4.36
1.84
4.11
3.55 0.27
s0.4
2.47
2.48
2.55=041
MNIST
3,33
2.36#084
3.01
-0.04e1.23*
2. 2.92=041
1. 1.68+080
2,98
3.01+0.45
3.37
CIFARIO
1.34
0.00a0.11
0,4320.27
-3.7
0.04g0.37
0,1520.31
0.58
2.90
0.6020.13*
SVHN
2.53
1.52a0.1*
1.98.0.18*
-1.6620.11
0.88
2,4620.21
2.0820222
220.22
2. 2.10..22
CIFARI00
0.98
0.3720.60
0.57a045
0.89
0. 0..400060
0.55
0.03
0.6420.48
T. ImageNet
0.55+0.16
+0.6
0.28+0.29
-0.20+o.46*
0.45.n.23
0.27+0.19
-0.15-0.3*
O. 2+0.40
FOOD101
1,27
-0.66+0.00
0.34-n.25
1.30
0.50+a.22 22*
1.18+0.55
-0.15-0.4*
0.7 100443*
ImageNet
0.96s023
+0.21
0. 14
-0.62to..00
0.30+0.22
0.71an81 0.57=0.1
Table The mean of runtime (min) for each algorithm and each dataset. We observe that LDM-S operates as fast as Entropy on almost all datasets.
LDM-S
Entropy
Margin
Coreset
ProbCov
DBAL
ENS
BADGE
BAIT
OML
7.1
6.0
5.9
6,4
5.8
5.8
28.1
6.2
628.8
OM1
4.5
4.2
3.7
4.4
4.0
4.2
17.5
4.2
60.2
OML#44135
5.2
4.0
4.6
18.2
4.4
319.8
MNIST
17.6
10.4
11.3
11.3
10.4
12.1
49.6
12.5
27.9
CIFARIO
106.0
99.6
101.0
106.1
97.5
108.0
496.0
102.2
6,436.5
SVHN
68.9
65.1
66.6
70.9
64.8
105.8
324.8
70.5
6,391.6
CIFARI00
405.9
395.2
391.4
429.7
405.5
447.8
1,952.1
445.3
ImageNet
4,609.5
4,465.9
4,466.1
4,706.8
4,621.4
4,829.2
19,356.4
5,152.5
FOOD101
4,464.8
4,339.8
4,350.3
4,475.7
4,471.0
4,726.8
18,903.3
4,703.9
Runtime comparison per datatset Table 2 presents the runtime (in minutes) for each algorithm on each dataset. Overall, compared to Entropy (considered one of the fastest), LDM-S incurs only a 6% increase in runtime on CIFARIO, SVHN, CIFAR100, Tiny ImageNet, and FOOD101. LDM-S is slightly faster than MC-BALD, Coreset, and BADGE on some datasets. The more considerable runtime increase observed on OpenML and MNIST datasets is attributed the relatively small training time compared to acquisition time due to simpler models and datasets. Due to individual training of all ensemble networks. ENS requires significantly more time (around 5x) than Entropy. BAIT exhibits runtime proportional to d²C²q. q. where d, C, and represent feature dimension, number of classes, and query size, respectively. This leads to significantly higher runtime, even for smaller datasets, making it impractical for large-scale tasks. In conclusion, LDM-S demonstrates superior or comparable performance to all considered baselines.
CONCLUSION
This paper introduces the least disagree metric (LDM), which measures uncertainty by considering the disagreement between the original and its perturbed model. Furthermore, the paper proposes hypothesis sampling method for approximating the LDM and an LDM-based active learning algorithm (LDM-S). LDM-S selects unlabeled samples with small LDM values while also incorporating batch diversity. Extensive evaluations across various datasets demonstrate that I. IDM-S consistently achieves the best performance or remains comparable to other perforrrfo active learning algorithms. These results establish LDM-S state-of-the-art method in the field.
One immediate future direction is obtaining a rigorous sample complexity guarantee for LDM-S. This will provide theoretical understanding of the number of samples required by LDM-S to achieve the desired level of accuracy. Exploring the integration of scalable and simple posterior sampling frameworks instead of the current Gaussian sampling scheme presents exciting potential for improvement. This could lead to more efficient and practical implementations LDM-S, particularly for larger datasets.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their helpful comments. We also thank Juho Lee and Chulhee Yun for their helpful discussions during the initial phase of this research. This work was partly supported by the Institute for Information communications Technology Planning & Evaluation (ITPP) grant funded by the Ministry of Science and ICT (MSIT) (No. 2021-0-0138 and 2022- 0-00184) and partly supported by the Commercialization Promotion Agency for R&D Outcomes (COMPA) grant funded by MSIT (No. 171 1198800.. The research was conducted the Korea Advanced Institute of Science and Technology (KAIST) and the Korea Institute of Oriental Medicine (KIOM) (No. N8N2221030).
REFERENCES
David Aldous. Covering a compact space by fixed-radius or growing random balls. Latin American Journal of Probability and Mathematical Statistics, 19:755-767, 2022.
David Arthur and Sergei Vassilvitskii. K-Means++: The Advantages of Careful Seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pp. 1027-1035, USA, 2007. Society for Industrial and Applied Mathematics.
Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade. Gone Fishing: Neural Active Learning with Fisher Embeddings. In Advances in Neural Information Processing Systems, volume 34, pp. 8927-8939. Curran Associates, Inc., 2021.
Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds. In International Conference on Learning Representations, 2020.
Peter Auer, Nicolo Cesa-Biana Bisaa-Bancci, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1))48-77, 2002.
Maria-Florina Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In Nader H. Bshouty and Claudio Gentile (eds.), Learning Theory COL.T 2007, pp. 35-50, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.
William H. Beluch, Tim Genewein, Andreas Nurnberger, and Jan M. Kohler. The Power of Ensembles for Active Learning in Image Classification. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9368 0888-977, 2018.
Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance Weighted Active Learning. In Proceedings of the 26th Annual International Conference Machine Learning, ICML '09, pp. 49-56, New York, NY, USA, 2009, Association for Computing Machinery.
Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. Food-101 mining discriminative compo- nents with random forests. In Computer Vision - ECCV 2014, pp. 446-461, Cham, 2014. Springer International Publishing.
G. E. P. Box and Mervin E. Muller. A Note on the Generation of Random Normal Deviates. The Annals of Mathematical Statistics, 29(2):610- 611, 1958.
E. Burnaev, P. Erofeev, and A. Papanov. Influence of resampling accuracy of imbalanced classification. Eighth International Conference on Machine Vision (ICMV 2015), volume 9875, pp. 987521. International Society for Optics and Photonics, SPIE, 2015a.
E. Burnaev, Erofeev, and D. Smolyakov. Model selection for anomaly detection. In Eighth International Conference Machine Vision (ICMV 2015), volume 9875, pp. 987525, International Society for Optics and Photonics, SPIE, 2015b.
Razvan Caramalau, Binod Bhattarai, and Tae-Kyun Kyun Kim. Sequential Graph Convolutional Network for Active Learning. In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9578-9587, 2021.
10

---

Published as a conference paper at ICLR 2024
Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference, con- verges to limit cycles for deep networks. In International Conference on Learning Representations, 2018.
François Chollet et al. Keras, https: https://keras.1e 2015.
Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Rostamizadeh, and Sanjiv Kumar. Batch Active Learning at Scale. In Advances in Neural Information Processing Systems, volume 34, pp. 11933-11944 Curran Associates, Inc., 2021.
David A. Cohn, Zoubin Ghahramani, and Michael I. Jordan. Active Learning with Statistical Models. Journal of Artificial Intelligence Research, 4(1): 145, Mar 1996.
Sanjoy Dasgupta. Two faces of active learning. Theoretical Computer Science, 412(119:1767-1781 2011. Algorithmic Learning Theory (ALT 2009).
Elizabeth D. Dolan and Jorge J. Moré. Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2):201-213, Jan 2002.
Melanie Ducoffe and Frederic Precioso. Adversarial Active Learning for Deep Networks: Margin Based Approach. arXiv preprint (.02vv/800.098// 2018.
R. M. Dudley, Real Analysis and Probubility. Cambridge Series in Advanced Mathematics. Cam- bridge University Press, 2002.
Juan Elenter, Navid Naderializadeh, and Alejandro Ribeiro. A Lagrangian Duality Approach Active Learning. In Advances in Neural Information Processing Systems, volume 35, pp. 37575-37589. Curran Associates, Inc., 2022.
Mark Fanty and Ronald Cole. Spoken Letter Recognition. In Advances in Neural Information Processing Systems, volume 3. MorgannKaufmann, 1990.
Peter Frey and David Slate. Letter recognition using Holland-style adaptive classifiers. Machine learning, 6(2): 161):161-822, 1991.
Alexander Freytag. Erik Rodner, and Joachim Denzler. Selecting influential examples: Active learning with expected model output changes. In Computer Vision ECCV 2014, pp. 562-577, Cham, 2014. Springer International Publishing.
Yarin Gal and Zoubin Ghahramani. Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning. In Proceedings The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1050-1059, New York, New York, USA. 20-22 Jun 2016. PMLR.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep Bayesian Active Learning with Image Data. In Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1183-1192. PMLR, 06-11 Aug 2017.
Ravi Ganti and Alexander Gray. UPAL: Unbiased Pool Based Active Learning. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statisties, volume 22 of Proceedings of Machine Learning Research, pp. 422 -31,, La Palma, Canary Islands, 21-23 Apr 2012. PMLR.
Bin Gu, Zhou Zhai, Cheng Deng, and Heng Huang. Efficient Active Learning by Querying Discrimi- native and Representative Samples and Fully Exploiting Unlabeled Data. IEEE Transactions on Neural Networks and Learning Systems, 32(9):4111-4122 2021.
Steve Hanneke. Theory of Disagreement-Basee Active Learning. Foundations and TrendsS in Machine Learning, 7(2-3):131-309 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving Deep into Rectifiers: Surpassing Human Performance on ImageNet Classification. In 2015 IEÉE International Conference Computer Vision (ICCV) pp. 1026-1034, 2015.

---

Published as a conference paper at ICLR 2024
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp- 770-778, 2016.
doi: 10.1109/CVPR.201.999
Nils Lid Hjort, Chris Holmes, Peter Müller, and Stephen G Walker. Bayesian Nonparametrics. Number 28 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2010.
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian Active Learning for Classification and Preference Learning. arXiv preprint arXiv:1112.5745 2011.
Ajay J. Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos. Multi-class active learning for image classification. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2372- 2379, 2009.
Seohyeon Jung, Sanghyun Kim, and Juho Lee. A simple yet powerful deep active learning with snapshots ensembles. In The Eleventh International Conference on Learning Representations, 2023.
Gwangsu Kim and Chang Yoo. Blending Query Strategy of Active Learning for Imbalanced Data. IEEE Access, 10:79526-79542, 2022.
Yoon-Yeong Kim, Kyungwoo Song, JoonHo Jang, and II-chul Moon. LADA:
Look-Aheal Data Acquisition via Augmentation for Deep Active Learning. In Advances in Neural Information Processing Systems, volume 34, pp. 22919-22930. Curran Associates, Inc., 2021.
Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Samory Kpotufe, Gan Yuan, and Yunfan Zhao. Nuances in Margin Conditions Determine Gains in Active Learning. In Proceedings The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 81 8112-8126. PMLR, 28-30 Mar 2022.
PL L Krapivsky. Random sequential covering. Journal of Statistical Mechanics: Theory and Experi- ment, 2033(3):033002, mar 2023.
Jan Kremer, Kim Steenstrup Pedersen, and Christian Igel. Active learning with support vector machines. WIREs Data Mining and Knowledge Discovery, 4(4):313-326, 2014.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. Technical report, CS231N, Stanford University, 2015.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (0:21)):27822333 1998.
David D. Lewis and William A. Gale. A Sequential Algorithm for Training Text Classifiers. In SIGIR '94, pp. 3-12, London, 1994. Springer London.
Rafid Mahmood, Sanja Fidler, and Marc T Law. Low-Budget Active Learning via Wasserstein Distance: An Integer Programming Approach. In International Conference on Learning Represen- tations. 2022.
Stephan Mandt, Matthew D. Hoffman, and David M. Blei. Stochastic Gradient Descent as Approxi- mate Bayesian Inference. Journal of Machine Learning Research, 18-1 2017.
Pascal Massart. Some applications of concentration inequalities to statistics. Annales de la Faculté des sciences de Toulouse Mathématiques, Ser. 6, 9(2):245-303 2000.
12

---

Published as a conference paper at ICLR 2024
David Mickisch, Felix Assion, Florens Greßner, Wiebke Günther, and Mariele Motta. Understand- ing the Decision Boundary of Deep Neural Networks: An Empirical Study. arXiv preprint arXiv:2002.01810, 2020.
Chris Mingard, Guillermo Valle-Pérez, Joar Skalse, and Ard A. Louis. Is SGD a Bayesian sampler? Well, almost. Journal of Machine Learning Research, 22(79):1-64, 2021.
Mohamad Amin Mohamadi, Wonho Bae, and Danica J Sutherland, Making Look-Ahead Active Learning Strategies Feasible with Neural Tangent Kernels. In Advances Neural Information Processing Systems, volume 35, Curran Associates, Inc., 2022.
Seyed-Mohsen Moosavi-Dezzoolii Alhussein Fawzi, and Pascal Frossard. DeepFool: A Simple and Accurate Method to Fool Deep Neural Networks. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2574-2582, 2016.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011.
Vu-Linh Nguyen, Mohammad Hossein Shaker, and Eyke Hüllermeier. How to measure uncertainty in uncertainty sampling for active learning. Machine Learning, 111(1)899-22, 2022.
Mathew D. Penrose. Random Euclidean coverage from within. Probability Theory and Related Fields, 185(3)7747-814, 2023.
Robert Pinsler, Jonathan Gordon, Eric Nalisnick, and José Miguel Hernández-Lobate Bayesian Batch Active Learning Sparse Subset Approximation. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
A. Reznikov and E. B. Saff. The Covering Radius of Randomly Distributed Points Manifold. International Mathematics Research Notices, (016((1))6065- 60944 12 2015.
Dan Roth and Kevin Small. Margin-basee active learning for structured output spaces. In Machine Learning: ECML 2006: 17th European Conference on Machine Learning Berlin, Germany, September 18-22, 2006 Proceedings 17, pp. 413-424. Springer, 2006.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV). 115 13):211-252, 2015. doi: 10.1007/s1 1263-015-0816-y.
Ozan Sener and Silvio Savarese. Active Learning for Convolutional Neural Networks: A Core-Set Approach. International Conference on Learning Representations, 2018.
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin Madconnnn-MMadionn Department of Computer Sciences, 2009.
C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27(3): 379-423, 1948.
Manali Sharma and Mustafa Bilgic. Evidence-based uncertainty sampling for active learning. Data Mining and Knowledge Discovery, (11(()6644202) Jan 2017.
Weishi Shi and Qi Yu. Integrating Bayesian and Discriminative Sparse Kernel Machines for Multi- class Active Learning. In Advances in Neural Information Processing Systems, volume 32, pp. 2285-2294. Curran Associates, Inc., 2019.
Samrath Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational Adversarial Active Learning. In 2019 IEFE/CVF International Conference Computer Vision (ICCV), pp. 5971-5980, 2019.
C. Spearman. "General Intelligence,"" " Objectively Determined and Measured. The American Journal of Psychology, 15(2):201-29) 1904.
13

---

Published as a conference paper at ICLR 2024
Simon Tong and Edward Chang. Support Vector Machine Active Learning for Image Retrieval. In Proceedings of the Ninth ACM International Conference on Multimedia, MULTIMEDIA '01, pp. 107-118, New York, NY, USA, 2001. Association for Computing Machinery.
Exgenii Tsymbalov, Maxim Panov, and Alexander Shapeev. Dropout-based active learning for regression. In Analysis of Images, Social Networks and Texts, pp. 247-258 Cham, 2018. Springer International Publishing.
Evgenii Tsymbalov, Sergei Makarychev, Alexander Shapeev, and Maxim Panov. Deeper Connections between Neural Networks and Gaussian Processes Speed-up Active Learning. In Proceedings of the Twenty-Eighnn Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 3599-3605. International Joint Conferences on Artificial Intelligence Organization, 2019.
Laurens van der Maaten and Geoffrey Hinton. Visualizing Data using t-SNE. Journal of Machine Learning Research, 9(8))25579 2605, 2008.
Aad van der Vaart. Asymptotic statistics, volume of Cambridge Series Statistical and Probabilistic Mathematics. Cambridge university press, 2000.
Aad van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics. Springer Series in Statistics (SSS). Springer New York, 1996.
Joaquin Vanschoren, Jan N Van Rijn, Bernd Bischl, and Luis Torgo. Openml: networked science in machine learning. ACM SIGKDD Explorations Newsletter, 15(2):49-60, 2014.
Martin J. Wainwright. High-Dimenssioal Statistics: A Non-Asymptotic Viewpoint. Number 48 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Haonan Wang, Wei Huang, Andrew Margenot, Hanghang Tong, and Jingrui He. Deep Active Learning by Leveraging Training Dynamics. In Advances in Neural Information Processing Systems, volume 35. Curran Associates, Inc., 2022.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International conference on machine learning, pp. 1954-1963. PMLR, 2015.
Jae Oh Woo. Active Learning in Bayesian Neural Networks with Balanced Entropy Learning Principle. In The Eleventh International Conference on Learning Representations, 2023.
Yazhou Yang, Xiaoqing Yin, Yang Zhao, Jun Lei, Weili Li, and Zhe Shu. Batch Mode Active Learning Based on Multi-Set Clustering. IEEE Access, 9:51452-51463, 2021.
Yi Yang, Zhigang Ma, Feiping Nie, Xiaojun Chang, and Alexander G. Hauptmann. Multi-Class Active Learning by Uncertainty Sampling with Diversity Maximization. International Journal of Computer Vision, 133 Jun 2015.
Ofer Yehuda, Avihu Dekel, Guy Hacohen, and Daphna Weinshall. Active Learning Through Covering Lens. In Advances in Neural Information Processing Systems, volume 35. Curran Associates, Inc., 2022.
Donggeun Yoo and In So Kweon. Learning Loss for Active Learning. In 2019 JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 93-102, 2019.
Sergey Zagoruyko and Nikos Komodakis. Wide Residual Networks. In Proceedings of the British Machine Vision Conference (BMVC), pp. 87. 12. BMVA Press, September 2016.
Beichen Zhang, Liang Li, Shijie Yang, Shuhui Wang, Zheng-Jun Zha, and Qingming Huang. State- Relabeling Adversarial Active Learning. In 2020 IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pp. 8753-8762, 2020.
Guang Zhao, Edward Dougherty, Byung-Jun Yoon, Francis Alexander, and Xiaoning Qian. Efficient Active Learning for Gaussian Process Classification by Error Reduction. In Advances in Neural Information Processing Systems, volume 34, pp. 9744-9776. Curran Associates, Inc., 2021a.
Guang Zhao, Edward Dougherty, Byung-Jun Yoon, Francis Alexander, and Xiaoning Qian. Uncertainty-awac Active Learning for Optimal Bayesian Classifier. In International Confer- ence on Learning Representations, 2021b.
14

---

Published as a conference paper at ICLR 2024
CONTENTS
Introduction
2
Least Disagree Metric (LDM)
2.1
Definition of LDM
2.2 An Asymptotically Consistent Estimator of LDM
2.3
Empirical Evaluation of LDM
3
LDM-based Active Learning
3.1
LDM-Seeding ......nn........................
3.2
LDM-S: Active Learning with LDM-Seeding
Experiments
4.1
Effectiveness of LDM in Selecting (Batched) Uncertain Samples
4.2
Necessity Pursuing Diversity LDM-S
4.3
Comparing LDM-S to Baseline Algorithms
8
5
Conclusion
Related Work
17
Proof of Theorem 1: LDM Estimator is Consistent
17
B.1
Supporting Lemmas and Proofs
19
B.2 Proof of Corollary
20
Theoretical Verifications of Intuitions
20
LDM as an Uncertainty Measure
20
C.2 Varying 2 in Algorithm 1
21
C,3 Assumption Holds with Gaussian Sampling
23
C.4 Effect of Diversity in LDM-S
25
D Datasets, Networks and Experimental Settings
25
D.I Datasets
25
D.2 Deep Networks
26
D.3 Experimental Settings
27
E Performance Profile and Penalty Matrix
27
E.1 Performance Profile
27
E.2 Penalty Matrix
27
Ablation Study
27
E1 Choice of Stop Condition
27
15

---

Published as a conference paper at ICLR 2024
F.2
Effectiveness of LDM
28
F3
Effect of Batch Size
29
F,4
Effect of Hyperparameters in LDM-S
30
Additional Results
30
G.1
Comparing with Other Uncertainty Methods with Seeding
................................
30
G.2
Comparison across Datasets with BAIT
G.3
Comparison per Datasets
31
16

---

Published as a conference paper at ICLR 2024
APPENDIX
A RELATED WORK
There are various active learning algorithms such as uncertainty sampling (Lewis & Gale, 1994; Sharma & Bilgic, 2017), expected model change (Freytag et al., 2014; Ash et al., 2020), model output change (Mohamadi et al., 2022), expected error reduction (Yoo & Kweon, 2019; Zhao et al., 2021a), training dynamics (Wang et al., 2022), uncertainty reduction (Zhao et al., 2021b), core-set approach (Sener & Savarese, 201 8; Mahmood et al., 2022; Yehuda et al., 2022), clustering (Yang et al., 2021; Citovsky al., 2021), Bayesian active learning (Pinsler al., 2019; Shi & Yu, 2019), discriminative sampling (Sinha et al., 2019; Zhang et al., 2020; Gu et al., 2021; Caramalau et al., 2021), constrained learning (Elenter et al., 2022), and data augmentation (Kim al., 2021).
Various forms of uncertainty measures have been studied for the incertainty-base approach. En- tropy (Shannon, 1948) based algorithms query unlabeled samples yielding the maximum entropy from the predictive distribution. These algorithms perform poorly in multiclass as the entropy is heavily influenced by probabilities less important classes (Joshi et al., 2009). Margin based algorithms (Bal- can et al., 2007) query unlabeled samples closest to the decision boundary. The sample's s closeness to the decision boundary is often not easily tractable in deep architecture (Mickisch al., 2020). Mutual information based algorithms such as DBAL (Gal al., 2017) and BatchBALD (Kirsch et al., 2019) query unlabeled samples yielding the maximum mutual information between predictions and posterior of model parameters. Both works use MC-dropout (Gal & Ghahramani, 2016) for deep networks to evaluate BALD (Houlsby et al., 2011). DBAL does not consider the correlation in the batch, and BatchBALD, which approximates batch-wise joint mutual information, is not ap- propriate for large query sizes. Disagreement based berry-by-committee (QBC) algorithms (Beluch al., 2018) query unlabeled samples yielding the maximum disagreement in labels predicted by the committee. It requires high computational cost for individual training of each committee network. Gradient based algorithm BADGE (Ash al., 2020) queries unlabeled samples that are likely to induce significant and diverse changes to the model, and Fisher Information (van der Vaart, 2000) based algorithm BAIT (Ash al., 2021) queries unlabeled samples for which the resulting MAP estimate has the lowest Bayes risk using Fisher information matrix. Both BADGE and BAIT require a high computational cost when the feature dimension or the number of classes is large.
B PROOF OF THEOREM 1: LDM ESTIMATOR IS CONSISTENT
We consider multiclass classificatton,, which we recall here from Section 2. Let X' and Y be the instance and label space with y {e: where e, the 7th standard basis vector of RCC (i.c. one-hot encoding of the label i), and H. be the hypothesis space of h X + V.
By the triangle inequality, we have that
LN.M L| LN.M IN + In L
(N,
AAz(N)
where we denote ΣN = min p(h, We deal with A A1 ()) first. By definition,
AN =
inf
Par (h,
we seHg%. p(h,g)
inf
he bEH
M (T((X)
inf hE
inf (x(Xx * xx)]] hEA
M
1=1
As (N is difference of infimums of sequence of functions, need to establish uniform convergence-tye result over a sequence of sets. This is done by invoking "general" Glivenko- Cantelli (Lemma 1) and our generic bound (Lemma 2) on the empirical Rademacher complexity on
17

---

Published as a conference paper at ICLR 2024
hypothesis class F = {f(x)) = [[(((x) # g(x)) h "N }, i.e., for any scalar 6 2 0, we have
(N)
sup h
IPM (h, g) - p(h,g)) s V
M + 6.
(- .M 8
with Dx Pr-probbbilityy at least exp
+ 8. As HN is finite, the infimums in the statement are achieved by some 91. 92 E H.N respectively. Then, due to the uniform convergence, we have that with probability at least
Now let 8 > 0 be arbitrary, and for simplicity, denote 8' =2 Clog(CN)
arsa
inf p(h, g) p(02.g) > p2r 9) 8' he xxx
inf PM (M 8
and
inf kEN
pM - pMr(a1,9) pl..g) 8' bEA
inf p(h, - 8',
and thus,
2 (og(CN)
AN, = inf PM PM (h. NEH
inf p(h, g)
S 22
+ 8.
hEA
M
Choosing M f log(CN), have that AN M) S 28 with probability at least
1
CN
We now deal with (N Recalling its definition, we have that for any h" E Ha. with p(h",g) [gg, z0) <
(2
min p(h,g) NEW
inf p(h,g)
mo
min NEH
p(h,g) 9) p(h"",00)
+ (l((h"g)) - a())
min NEH
(p(h, g) - p(h",g) +
min p(h, h²) +E hEH
B min dx h²)) + hEH
where (+) follows from Assumption 2. Taking the infimum over all possible ht on both sides, by Assumption 3, we have that (2 & ax ((N, E) + w.p. at least 1 - 3(N).
Using the union bound, we have that with M Log(CNN,
IP [L zn) L(g, xo) & 25 - a(N,)) + E| ž P [ M) + A2(N) S + a(N,e) +
B(N).
CN
For the last part (convergence in probability), start by denoting Za,N IN,M (g, an) I(g, az))
(Recall that M is a function of 6, according to our particular choice). Under the prescribed limits and arbitrarities and our assumption that (NN, B(N) 0 N + co, have that for any sufficiently small 8' > 0 sufficiently large N,
1 28 2 28'.
To be precise, given arbitrary 0, A, e 0. let 8' > 0 be such that 28 + < 7 Then it suffices
where a a (:;)) is the inverse function of a(;)) w.r.t. the first argument, and 3-1 is the inverse function of 3.
choose N max (a-1 {: + 3-1
18

---

Published as a conference paper at ICLR 2024
This implies that dxr(Z8'.. 0) I 28', where dxF (X, inf 2 0 P 81 8'} the Ky-Fan metric, which induces a metric structure on the given probability space with the convergence in probability (see Section 9.2 of (Dudley, 2002)). As 0n. A, is arbitrary and thus so is 8', this implies that |LNMM xo) - L(g, æo)l 5 0.
We believe that Assumption 3 can be relaxed with weaker assumption. This seems be connected with the notion of e-net (Wainwright, 2019) as well as recent works on random Euclidean coverage (Reznikov Saff, 2015; Krapivsky, 2023; Aldous, 2022; Penrose, 2023). Although the aforementioned works and our last assumption are common that the random set is constructed from i.i.d. samples(hypotheses)) one main difference is that for our purpose, instead of covering the entire space, one just needs to cover a certain portion at which the infinum is (approximately) attained.
Remark 2.
B.1 SUPPORTING LEMMAS AND PROOFS
Lemma (Theorem 4.2 of Wainwright (2019)). Let YI,.... ,Y, ~ P for some distribution IP over
i..dd
X. For any b-uniformly bounded function class F, any positive integer n. 1 and any scalar we have
((Y.) B[(O) (F) +
sup fET
with PP i-probability at least exp of F.
(-m0²
no² 8b
Here, (n(F) is the empirical Rademacher complexity
Recall that in our case, M, and F {f(x) 1[h(x) + g(x)] h E H.. The following lemma provides a generic bound on the empirical Rademacher complexity of F:
Lemma 2. Ra (F) < / [Cg(CN)
M
Proof. For simplicity, we denote A HM where the expectation is w.r.t X Dx i...d, and a is the M -ddimensional Rademacher variable. Also, let [M]] + [C] be the labeling function for fixed samples { i.c. I(i) arg max [o(),)), As g outputs one-hot encoding for each i, I(1) is unique and thus well-defined. Thus, have that fXX;) I[h(X,) + g(X,)] 1 hug (X.). where we denote h By definition,
(h1, h2, .c)) with h2 X {0, 1}.
RM)
E
sup jer
Σ (X,)
M
= E
sup
ai(1 - Auco huco (X:))
hEH
M
1=1
1
E
sup
Σ (x))
M iml
kEE
M
< E
sup
Σ (x,)
M i=1
hEH [E(C)
RM ((hy h E H , (CT})
2 (og(CCN)
M
where the last inequality follows from Massart's Lemma (Massart, 2000) and the fact that 79.000 is finite set of cardinality most N.
19

---

Published as a conference paper at ICLR 2024
(SCWN) (sorr.--0.05)
600
700
100
900
Drter of LD
5403
LD95
80
600
400
303
order
300
203
103
100
20
60
60
100
0
100
200
200
400
500
100
200
300
400
500
order uncertainty
uncertantty
order uncertaitty
(a)
(b)
(c)
Imtgehel
12309
4000
30003
9000
onter of LDW
2000
order of LDM
6009
2000
6203
9000
4000
1000
2000
500 1000 1500 2000 2500 3000 3500 4000 uncertality
2000
4000
8000 10000 uncortalitty
600D
12000
2300
4000
0000
0000
uncortainty
(d)
(c)
(f)
Figure 5: Examples of negative Spearman's 's rank correlation between LDM order and uncertainty order on MNIST (a), CIFARIO (b), SVHN (c), CIFAR100 (d), Tiny ImageNet (e), and FOOD101 (f)-
B.2 PROOF OF COROLLARY
With the given assumptions, we know that LM.v xx) 2 L(g, xb) for k E (i.j]. For notation simplicity we denote Lig, æx) as ((k), LM,,(g, wx) L (K) and lim min() as lim For M=w(log(CN)))
arbitrary ε > O. we have
lim N +20
LN
(
+ 8
lim P
L >
1 + A
IL
1 < A |L - L5)
E <>
N
< lim
P
[10)
+ E
E
+E
N
2
2
p L0 19) =0.
C THEORETICAL VERIFICATIONS OF INTUITIONS
Here, consider two-dimensional binary classification with set of linear classifiers, H (h- h(x) = sgn(( (x w)) where w E 2R2 is the parameter h. We assume that x is uniformly distributed on X {a ||||||| 1) c IR.. For given g H. let v be the parameter of g.
C.I LDM AS AN UNCERTAINTY MEASURE
Recall from Section 2.1 that the intuition behind a sample with a small LDM indicates that its prediction can be easily flip-flopped even by a small perturbation in the predictor. We theoretically prove this intuition
Proposition 1. Suppose that h is sampled with w ~ [ev Io Then,
L(g. x1) < L(g. x2) + Plh(z1) + g( > Plh(22) + g(Ø2)).
Figure 5 shows examples of Spearman's 's rank correlation (Spearman, 1904) between the order of LDM and uncertainty, which is defined the ratio of label predictions by small perturbation in the predictor, on MNIST, CIFARIO, SVHN, CIFAR100 Tiny ImageNet, and FOODI01 datasets. Samples with increasing LDM uncertainty are ranked from high to low. The results show that
20

---

Published as a conference paper at ICLR 2024
W
W
W. Mua 1 11a
Wi
N(b
W = We.s ; Meme
~ In,
0z.
Origin
Origin
Mg. 2) = 10, 0.//x P((()) / g(æ))
Pfwe c W
W2
(b)
Figure 6: Proof of Proposition 1.
LDM and uncertainty orders have strong negative rank correlation. Thus, a sample with a smaller LDM is closer to the decision boundary and is more uncertain.
Proof of Proposition 1. One important observation is that by the duality between and (Tong Chang, 2001), in R22 ur point and æ is represented by the hyperplane, la (w TR2 sgn(æ w) 0}. Suppose that h is sampled with ~ N(v Io and let 0, be the angle of v, 0n be the angle between le and positive x-axis, and Ma be the half-plane divided by la which does not contain v:
W = (w' E W (((x) + g(x)} as in Figure 6a. Then, L(g, x) 10,- - 0.l/T and P(((()) + g(x)] = Flw Wo.a).
Let d1, d2 be the distances between and lmy, lmg respectively, and
W1 = yua \ Ma W2 W Wa
as in Figure 6b. Suppose that d1 < d2, then 10,, - 0ol < 102z 0el since d, = ||w||| sin 10z. - 0ol
and
Plw E Wummi] P(w E Wmmaa]= = TP/w E Wi] PPww E Wa] > 0
by the following:
Wo..n Wi (Wo. n Wo.w)), W W3 (Wo.m mwom
where Wi, W2, and 1 Wv.æz are disjoint. Note that Wi and W2 one-to-one mapped by the symmetry at the origin. Still, the probabilities are different by the biased location of v. i.c., o(w;/e (u, o²) p(wzlv, for all pairs of (w1, W2) Wi x W2 that are symmetric the origin. Here @(-10, dd) is the probability density function of the bivariate normal distribution with mean and covariance I²I. Thus,
L(g,an) (gg,02) di d2 P((( g(x))) PP(((22)) g(x2))
C.2 VARYING x² IN ALGORITHM
Recall from Section 2.2 that the intuition behind using multiple a² is that it controls the trade-off between the probability of obtaining hypothesis with different prediction than that of g and the scale of Ps gh. Theoretically. we show the following for two-dimensional binary classification with linear classifiers:
Proposition 2. Suppose that h is sampled with NN,,, Io²) where w, W are parameters of h, respectively, then [phh,(,, 9)] is continuous and strictly increasing with a.
Figure 7 shows the relationship between Ps (h. g) and log for MNIST, CIFARIO, SVNH, CIFAR100, Tiny ImageNet, and FOOD101 datasets where h is sampled with A/ (o?) and P. (h, g) is the mean of Ps (h. g) for sampled hs. The P. (h. .) monotonically increasing with log in all experimental settings for general deep learning architectures.
21

---

Published as a conference paper at ICLR 2024
0.8
0.8
0.6
0.6
0.6
0.6
0.4
0.4
-10
-10
00
-00
kgg
(a)
(b)
(c)
CIFAR100 (WIRN)
Thy Image Vet (WRN)
Food101 (WRRN)
1.0
1.0
1.0
mean
mcan
mcan
0.0
D.2
0.0
10
2
0.0
0.1
10
2
lngs
(d)
(e)
(f)
Figure 7: The relationship between the disagree metric and perturbation strength for MNIST (a),
CIFARIO (b), SVHN (c), CIFARI00 (d), Tiny ImageNet (c), and FOOD101 (f) datasets. Pa (h, g) is
monotonically increasing with the perturbation strength in all experimental settings.
W
W
(f, I)
le
Blp(h, 1ii0- 0el/m]
2mu
log
80
2logui
U[0
(0 0v)
Omig 0
2m
pe. |||||
M6y M2
[]
Origin
Origin
(b)
Figure 8: Proof of Proposition 2.
Proof of Proposition 2. By the duality between and æ. in W, is point and æ is represented
by the hyperplane, lz = {w E W sgn(x w) = 0}. Let h be a sampled hypothesis with NVv,, Io=), O, be the angle of v (vi, u2) i.e., lan 0,, U2/01, 0 be the angle of (wi, w2) T,, i.e., lan = w2/wi, and Oz be the angle between Ln and positive x-axis. Here, 0, Oz E [- I 00. π + 0z] in convenience. When 0₂ or æ + Og is between O and o,. h(x) * gzx), otherwise h(x)) = g(x). Thus, p(h.g) = 0/l/T.
Using Box-Mulll transform (Box & Muller, 1958), w can be generated by
Wi U1 a / log 41 (2s Wy U2 + / log i1 sin(2
where un and Uy are independent uniform random variables on [0. 1). Then, || (ww- w/| = - u1
and (we- u2) vg)/(wn, v1) = tan (ann2)) i.e., the angle of w is 2T Here,
|||| si 0.) / -2lg in sin(2
(8)
by using the perpendicular line from e to the line passing through the origin and w (see the Figure for its geometry), and Eq. 8 is satisfied for all 0. For given in and u2 0 is continuous and the derivative of 0 with respect to is
V-2 log Ui sin" (2Tu2 - 0) do |||| sin (2T 0w)
d0
thus
da > 0, z
U2 E
(T 2x
Gg I+.l
do
< 0,
U2
E [0, 1
2
00 x Ow
2
22

---

Published as a conference paper at ICLR 2024
(b)
Figure 9: Proof of Proposition 3.
Then,
dp(h,g) sgn(0 0z) d8 do
π + 0v
do
where u2 &
{
2n
2
and u2 * Itd=, Let Thus, g) is continuous and strictly increasing with a when u2 * ly p(h, g) Fo, u1, u2) then (w(p(h, = f F(o, un I1O u, 1]. For 0 < 01 02.
2
2x
where f(u,) =
E (( (ph,, g)] (ww.N(LLo))) pph
f (F(02, uz) F(oi, u2)) [uu)) >> 0.
C.3 ASSUMPTION 3 HOLDS WITH GAUSSIAN SAMPLING
Proposition 3. Assume that the given sample Dy forms an angle 9g E (0, x/2) w.r.. the x-axis, and consider E (0,1) such that 0g + 5. Then, for binary classification with linear hypotheses and HN comprising of N ii.dd random samples from ((1,, 0), I² for some fixed o² and B(N) O (e-v))
Assumption 3 holds with a(N,=) =0
VN
Proof. We want to show that there exists a(N,-) and B(N) with oo a(N..) 1im B(N) = such that
IP
inf =(w (E( +xe) WEH"
min
B |w0" w w12 2 a(())) s B(N),,
where (ww") is the angle made between w" and the x-axis. Note that H random as well. Thus, we make use of a peeling argument as follows: conditioned on the event that N S for [N), we have that for any A sin
inf wh w (ot
I WEN -EH
min
wl12 2 A
| = = (1- (1-ppp p(1-p(6u:22 A, S
where p(0o, A, 8) is the measure of the region enclosed by the red boundary in Figure 9a with respect to ()1,)),)) I2). Also, we have that for
N [N]
P|
((00) ((5
where q(6)) is the measure the (light) red region in Figure 9b with respect to (((10)) o2
Thus, we have that
P
inf
min wEM
||00" - w
> A
0(w0 (E (96
23

---

Published as a conference paper at ICLR 2024
N
Σ
inf (E(Ho.
min
||00"
-wll ww12 2 A
| = S
PI = S)
we Hx
5=0
q(0b) ((00))((1 (L (1-(((0)))--- (1-6))))-8(1122))) A,))
5=0
= (11 ((6)) + g((6)(1 - p(00, (,)))
(1 p(0, (8)) N
I e N))(f....)v(tb),
where the last inequality follows from the simple fact that + x: S et for any x R.
Now suffices to obtain non-vacuous lower bounds of p(0u: A,E) and ((%)).
Lower bounding g(0)). By rotational symmetry of ((1, 0), 12) and the fact that rotation preserves Euclidean geometry, this is equivalent to finding the probability measure of the lower half-plane under the Gaussian distribution (((0, sin 0o), o I2), I2)),
which is as follows:
x=a + (y -innin sin 00)
g(0n)
exp
dxdy
2n
2
1
siu
y²
exp
dy
2
2x²
-00
1
sin
y²
exp
dy
2
V2TO
20
(1)
1
sin 9o
20
(sin 00)
)) y ++ 1++1 dy
- exp
2
V2TO
Jo
(sin 0s))
20
1
1
(sin 00)
0²
1 - exp
+ sin 0o
2
V2TT
20²
1
(sin 0b)
sin 0g
exp
2
V2
20
where (+) follows from the simple observation that e
L-e
1 for E [-a, 0] and >> 0.
Lower bounding p(0, A, e).
Via similar rotational symmetry arguments and geometric decompo- sition of the region enclosed by the red boundary (see Figure 9a), we have that
p p00.
A,E)
A
A2
+
A3
(see Figure 9a)
2² (y
sin 0u)
exp
drdy
2
2a²
x2 + (y sin + TE))2
cxp
drdy
2TO²
202
00
mo
(r cos cos 0 1)2 (r sin 0)2
exp
rdrd0
2T
202
86
1
A
sin Og
y²
A 4sin(Bo+mrr)
y2
exp
dy
exp
dy
2 2TO
80
20
2 2TO
sin(Bo+aT))
2
2
2r cos
+ 1
exp
rdrd0
2no²
20"
86
A
(sin 00)
A
sin (fg xE))²
exp
exp
2
202
2 2mo
20
2 +
rexp
dr
20
2 2
00
24

---

Published as a conference paper at ICLR 2024
h
large LDM
B
Utdocaded
Figure 10: The effect of LDM-based seeding. Considering only LDM, samples are selected only in or B, but samples in C or D are also selected if the seeding method is applied.
A
(sin 0o + 1)²
exp
exp
2TT
20
20
By choosing A O VN the proposition holds.
C.4 EFFECT OF DIVERSITY IN LDM-S
Here, we provide more intuition on why samples selected in the order of the smallest empirical LDM may not be the best strategy and, thus, why we need to pursue diversity via seeding, which was verified in realistic scenarios Section 4.2. Again, let us consider realizable binary classification with set of linear classifiers, i.e., there exists ht whose test error is zero (See Figure 10). Let the red circles and blue crosses be the labeled samples and g be the given hypotheses learned by the labeled samples. In this case, the LDMs of samples in groups A or B are small, and those in groups C or D are large. Thus, we do not impose diversity and choose only samples with the smallest LDM, the algorithm will always choose samples in groups A B. However, the samples in groups C or D more helpful to us in this case, i.e., they provide more information. Therefore, pursuing diversity is necessary to provide the chance query samples in C and D.
D DATASETS, NETWORKS AND EXPERIMENTAL SETTINGS
D. DATASETS
OpenML#66 (Frey & Slate, 1991) a letter image recognition dataset which 20, 000 samples in 26 classes. Each sample has 16 numeric features. In experiments, it is split into two parts: 16, 000 samples for training and 4, 000 samples for test.
ML#11 (Vanschoren al., 2014) is synthesized dataset for random RBF which has 100, 000 samples in classes. Each sample has 10 numeric features. experiments, subset is split into two parts: 40, 000 samples for training and 10, 000 samples for test.
ML4435 (Fanty & Cole, 1990) is a isolated letter speech recognition dataset which has 7, 797 samples in 26 classes. Each sample has 614 numeric features. In experiments, it is split into two parts: 6, 237 samples for training and 1, 560 samples for test.
MNIST (Lecun al., 1998) is handwritten digit dataset which has 60, 000 training samples and 10, 000 test samples in 10 classes. Each sample is a black and white image and 28 x 28 in size.
CIFAR10 and C1FAR100 (Krizhevsky, 2009) tiny image datasets which has 50, 000 training samples and 10, 000 test samples in 10 and 100 classes respectively. Each sample a color image and 32 x 32 in size.
25

---

Published as a conference paper at ICLR 2024
Table Settings for data and acquisition size. Acquisition size denotes the number of initial labeled samples query size for each step (the size of pool data) - the number of final labeled samples.
of parameters
Data size
Dataset
Model
Acquisition size
sampled
train validation test
OpenML##6
MLP
3.4K/22.0K
16,000 / / 4,000
200
+200 (2K)
4,000
OpenMI.
MLP
0.6K/18.66 6K
40,000 - 10,000
100
+ +100 (2K)
+ 2,000
OpenML#44135
MLP
3,4K/98.5K
6.237 /-/ 1.560
100
+100 (2K)
+2,000
MNIST
S-CNN
1.3K/1.2M
55,000 / 5,000 10,000
20
+20 (2.000)
+ +1,020
CIFARIO
K-CNN
5.IK/2.2M
45,000 / 5,000 10,000
200
+400 (4,000)
+ +9,800
SVHN
K-CNN
5.1K/2.2M
68,257 / 5,000 26,032
200
+400 (4,000)
9,800
CIFAR100
WRN- 16-8
51.3K/11.0M
45,000 5,000 10,000
5,000
+2,000 (10,000)
25,000
Tiny ImageNet
WRN- 16-8
409.8K/1 1.4M
90,000 10,000 10,000
10,000
+5,000 (20,000)
+ 50,000
FOOD101
WRN- 16-8
206.9K/1 1.2M
60,600 15,150 25,250
6,000
+3,000 (15,000)
30,000
ImageNet
ResNet-11
513K/11.7M
1.153,047 1 128.120/ 50,000
128,120
+64,060 (256,240) 384,360
Table 4: Settings for training.
Batch
Learning Rate Schedule
Dataset
Model
Epochs
Optimizer
Learning Rate
size
xccay (epoch schedule]
OpenML#66
MLP
100
Adam
0.001
OpenML#1555
MLP
100
Adam
0.001
MenML#44133
MLP
100
64
Adam
0.001
MNIST
S-CNN
50
32
Adam
0.001
CIFARIO
K-CNN
150
64
RMSPPop
0.0001
SVHN
K-CNN
150
R.M.Prop
0.0001
CIFARIO0 100
WRN-16-8
100
128
Nesterov
0.05
x0.2 [60, 80]
Tiny ImageNet
WRN-16 16-8
200
128
Nesterov
0.1
x0.2 [60, 120, 160]
FOODI01
PR-N16-88
200
128
Nesterov
0.1
x0.2 [60, 120, 160] x0.2 [60, 80]
ImageNet
ResNet-18
100
128
Nesterov
0.001
SVHN (Netzer al., 2011) is real-world digit dataset which has 73, 257 training samples and 26, 032 test samples in 10 classes. Each sample is a color image and 32 x 32 size.
Tiny ImageNet (Le & Yang, 2015) is subset of the ILSVRC (Russakovsky et al., 2015) dataset which has 100, 000 samples in 200 classes. Each sample is a color image and 64 x 64 in size. In experiments, Tiny ImageNet is split into two parts: 90, 000 samples for training and 10, 000 samples for test.
FOOD101 (Bossard al., 2014) is fine-grained food image dataset which has 75, 750 training samples and 25, 250 test samples in 101 classes. Each sample is a color image resized to 75 x 75.
ImageNet (Russakovsky et al., 2015) is image dataset organized according the WordNet hierar- chy, which has 1, 281, 167 training samples and 50, 000 validation samples (we use the validation samples as test samples) in 1, 000 classes.
D.2 DEEP NETWORKS
MLP consists of [128 dense dropout (0.3) 128 dense dropout (0.3) class dense softmax] layers, and it is used for OpenML datasets.
S-CNN (Chollet et al., 2015) consists of [3x3x32 conv 3x3x 64 conv 2 2 maxpool dropout (0.25) 128 dense dropout (0.5) - class dense softmax] layers, and is used for MNIST.
K-CNN (Chollet et al., 2015) consists of [two 3x3x32 conv 2x2 maxpool dropout (0.25) two 3x3x64 64 conv 2x2 maxpool dropout (0.25) - 512 dense - dropout (0.5) - # class dense- softmax] layers, and is used for CIFAR10 and SVHN.
WRN-16-8 (Zagoruyko Komodakis, 2016) is a wide residual network that has 16 convolutional layers and widening factor 8, and it is used for CIFAR100, Tiny ImageNet, and FOOD101.
ResNet-18 (He et al., 2016) is a residual network that is a 72-layer architecture with 18 deep layers, and it is used for ImageNet.
26

---

Published as a conference paper at ICLR 2024
D.3 EXPERIMENTAL SETTINGS
The experimental settings for active learning regarding dataset, architecture, number of parameters, data size, and acquisition size are summarized in Table 3. Training settings regarding number of epochs, batch size, optimizer, learning rate, and learning rate schedule are summarized in Table 4. The model parameters are initialized with He normal initialization (He et al., 2015) for all experimental settings. For all experiments, the initial labeled samples for each repetition are randomly sampled according to the distribution of the training set.
E PERFORMANCE PROFILE AND PENALTY MATRIX
E. PERFORMANCE PROFILE
The performance profile, known as the Dolan-Moré plot, has been widely considered in benchmarking
active learning (Tsymbalov et al., 2018; 2019), optimization profiles (Dolan & Moré, 2002), and even general deep learning tasks (Burnaev et al., 2015a;b). To introduce the Dolan-Moré plot, let
D.r.f acc a. be the test accuracy of algorithm A at step E [Tb], for dataset D and repetition [R].
D.r.f D.r. Here, Tn is the number steps for dataset D, and and A D,r,t max A' (acc N² (ace D.rst) - acc
the total number of repetitions. Then, we define the performance profile as
En
I(A D.rt _ō)
Σ RA = D D
RTD
where n is the number of datasets. Intuitively, RA(6) is the fraction of cases where the performance gap between algorithm A and the best competitor is less than 6. Specifically, when 0, (0) is the fraction of cases on which algorithm A performs the best.
E.2 PENALTY MATRIX
The penalty matrix P = (Piz) is evaluated as done Ash et al. (2020): For each dataset, step, and each pair of algorithms (A,, A₁), we have test accuracies {ace 1r=1 and face ) re- spectively. We compute the f-score t V5p/ō, where jt - (ace) acc)) and -= ==ViEi - acc 2.). The two-sided paired sample (-test is performed for the null that there is no performance difference between algorithms: A; is said beat A₁ when t 2.776 (the critical point of p-value being 0.05), and vice-versa when < 22776.. Then, when A, beats Aj. we accumulate a penalty" of I P.j where Tn is the number of steps for dataset D, and vice-versa. Summing across the datasets gives us the final penalty matrix.
F ABLATION STUDY
F.1
CHOICE OF STOP CONDITION S
Figure la shows the empirically evaluated LDM by Algorithm in binary classification with the linear classifier as described in Figure 1. In the experiment, the true LDM of the sample is set to 0.01. The evaluated LDM is close to the true LDM when s = 10 and reaches the true LDM when > 20 with gap of roughly 10-4. This suggests that even with a moderate s, Algorithm 1 can approximate the true LDM with sufficiently low error.
Figure 1lb shows the empirically evaluated LDMs of MNIST samples for four-layered CNN where M is set to the total number samples MNIST, which is 60000. We denote æ; as the 7th sample ordered by the final evaluated LDM. Observe that the evaluated LDMMs are monotonically decreasing as 8 increases, and they seem to converge while maintaining the rank order. In practice, obtaining values close to the true LDM requires large s, which is computationally prohibitive the algorithm requires a considerable runtime to sample many hypotheses. For example, when s = 50000, our algorithm samples ~50 hypotheses and takes roughly 18 hours to run and evaluate LDM. Therefore,
"This choice of penalty ensures that each dataset contributes equally the resulting penalty matrix.
27

---

Published as a conference paper at ICLR 2024
true
(SCINN
(SCNN:
0.09
208
1e 16530
0012
3 3.000
3 6:07
0/00
3 0:00
0003
0.90
3
0.596
5
0003
0.02
0.544
30'
20'
12*
stop condittion
Stop Bar
stop condition
(a)
(b)
(c)
MNIST (SCNN)
MNIST (SCNN)
16.
Oun kig tine (00
327
30*
10
224
Stop
2000 50
(d)
Figure 11: Empirically evaluated LDMs by Algorithm with respect to the stop condition 8. (a) Here, we consider the woo-dimensional binary classification with the lincar classifier (see Figure 1). The evaluated LDM is close to the true LDM even when s = 10 and reaches the true LDM when s 2 20. (b) Evaluated LDMs of MNIST samples with four-layered CNN. Observe that the evaluated LDM monotonically decreases as increases, and the rank order is well maintained. (c) In the same setting, the rank correlation coefficient of the evaluated LDMs at various to that at 50000. Note that already at = 10, the rank correlation coefficient is 0.998, suggesting that s = 10 suffices. (d-e) For evaluating LDM, the number of sampled hypotheses and runtime are almost linearly proportional to the stop condition.
based upon the observation that the rank order is preserved throughout the values of s, we focus on the rank order of the evaluated LDMs rather than their actual values.
Figure 1l shows the rank correlation coefficient of the evaluated LDMs of range of s's to that at 50000. Even when already 0.998. We observed that the evaluated LDMs' properties regarding the stop condition s also hold for other datasets, i.e., the preservation of rank order holds in general.
10, the rank correlation coefficient between 10 and 8 = 50000 is
Figure lld and 1le show the number of sampled hypotheses and runtime with respect to the stop condition when LDM is evaluated. Both are almost linearly proportional to the stop condition and thus, we should set the stop condition to be as small as possible to reduce the running time in LDM evaluation.
F.2 EFFECTIVENESS OF LDM
To isolate the effectiveness of LDM, we consider three other variants of LDM-S. 'LDM-smallest select batches with the smallest LDMs without taking diversity into account, 'Seeding (cos)' and 'Seeding (f2)' are the unweighted k-means++ seeding methods using cosine and &, distance, respec- tively. Note that the last two do not use LDM in any way. We have excluded batch diversity to clarify the effectiveness of LDM further.
Figure 12 shows the test accuracy with respect to the number of labeled samples on MNIST, CIFARI0 10. and CIFAR 100 datasets. Indeed, we observe significant performance improvement when using LDM and further improvement when batch diversity is considered. Additional experiments are conducted to compare the k-means++ seeding with FASS (Wei et al., 2015) or Cluster- (Citovsky et al., 2021), which can be a batch diversity method for LDM. Although FASS helps LDM slightly, it falls short of LDM-S. Cluster-Margh also does not help LDM and, surprisingly, degrades the performance. We believe this is because Mluster-Margin strongly pursues batch diversity, diminishing the effect of LDM as uncertainty measure. Specifically, Cluster-Margin considers samples of varying L.DM
28

---

Published as a conference paper at ICLR 2024
1001 00000000 (N11
20
X
14
LOM5 Geeddng (CR4)
LEM-5
LDN
Geeding (c0o
ICOS]
Saoling
LDMIC Morgig
LDM Margin
LON C.Faggnn
02
200
800
600
300
3030
4820
5000
60c0
2003
DECO
BEE6 10000
1200
1000
30003 18000 20036
22092
28000
sumplees
ciibbreed camples
F2libbeed samplee
(a)
(b)
(c)
Figure 12: The effect of diverse sampling in LDM-S on MNIST (a), CIFARIO (b), and CIFARI00 (c) datasets. L.DM-mmallest selecting batch with the smallest LDM, 'Seeding (cos)': unweighted seeding using cosine distance, 'Seeding (E2):: unweighted seeding using Ez-distance, 'LDM+FASS': the combination of LDM and FASS, 'L.DMC-MMargnn' : the combination of LDM and Cluster-Margin. LDM-S leads to significant performance improvement compared to those without batch diversity, with FASS, or with Cluster-Margin.
(y-1)
(1-10)
lym40)
100
90
0000 0000000 1962
00
LDNS
DRAL
70
LDR1-
DBAL
SHIR
fetmoy
DV
NET Poztay
DATT
ProtCCs
30
73
ELU
1D
200
10
20
423
D
50
12
UMI
113
DE
17
AN
42
0
50
303 AD
10
AN LD
samples
Uitdled
(a)
(b)
(c)
Figure 13: Performance comparison when the batch sizes are 1 (a), 10 (b), and 40 (c) on MNIST.
CIFAR1O (KCNNI (g)
SVII (KC3/10 (gm)
CIFAR1D (WRN) (g=SK)
72
ProcCav
LDMI
BADCE
RACOE
DANM 11928 J000 22305 baskee
2AW
27392 23033
(900 1230 2000 A750U 20003 2230 EXO
20500 29280
10000 12300
17500
25600 27300
abeled
(a)
(b)
(c)
Figure 14: Performance comparison when the batch size is 5K on CIFARIO (a), SVHN (b), and CIFAR100 (c).
scores from the beginning (a large portion of them are thus not so helpful). In contrast, our algorithm significantly weights the samples with small LDM, biasing our samples towards more uncertain samples (and thus more helpful).
F.3 EFFECT OF BATCH SIZE
To verify the effectiveness of LDM-S for batch mode, we compare the active learning performance with respect to various batch sizes. Figure 13 shows the test accuracy when the batch sizes are I, 10, and 40 on the MNIST dataset. Figure 14 shows the test accuracy when the batch size is 5K on CIFAR1O, SVHM, and CIFAR100 datasets. Overall, LDM-S performs well compared to other algorithms, even with small and large batch sizes. Therefore. the proposed algorithm is robust to batch size, while other baseline algorithms often are not. For example, BADGE performs well with batch sizes 10 or 40 but is poor with batch size one on MNIST. Note that we have added additional
29

---

Published as a conference paper at ICLR 2024
NNIST (SCNN) (r. 108--1
1021 2000000 (N41
20
20
1uml BOL- ACOLTMN (N)
-2
31:30
1000
30-30000
2011.00
22
200
800
600
900
3033
200
605
660
803
1800
200
450
600
66.0 1000
sumplees
complex
labelcc camples
(a)
(b)
(c)
Figure 15: Performance vs hyperparameters. The accuracy with respect stop condition (a), the number of Monte Carlo samples for approximating (b), and sigmas' interval (c).
MNIST (SCNN)
CIFAR1O (KCAN)
CIFARL00 (WAN]
30
-44
Sast MOOG PICH
of ceeding
ENC-sending
200
400
660
900
3030
4030
5000
6000
2003
8000
5606
10600
LOW (0AM)
2003 J8E3S
2003E 22005
(a)
(b)
(c)
Figure 16: The performance comparison of LDM-S with the standard uncertainty methods to which weighted seeding is applied on MNIST (a), CIFARIO (b), and CIFARI00 (c). Even weighted seeding is applied to the standard uncertainty methods, LDM-S performs better.
results for BatchBALD in Figure 13 and Cluster-Margin (C-Margin) in Figure 14. For both settings, we'v ve matched the setting as described in their original papers.
F.4 EFFECT OF HYPERPARAMETER IN LDM-S
There are three hyperparameters in the proposed algorithm: stop condition 8, the number of Monte Carlo samples M, and the set of variances -==
The stop condition s is required for LDM evaluation. We set s = 10, considering the rank correlation coefficient and computing time. Figure 15a shows the accuracy with respect to E {1, 5, 10, 100, 1000), and there is no significant performance difference.
The number of Monte Carlo samples M is set for approximating p. The proposed algorithm aims to distinguish LDMs of pool data. Thus, we set M to be the same as the pool size. Figure 15b shows the test accuracy with respect to M E (10, 100, 1000, 10000), and there no significant performance difference except where M is extremely small, e.g., M 10.
The set of variances { k=1 is set for hypothesis sampling. Figure 7 in Appendix C.2 shows the relationship between the disagree metric and a². To properly approximate L.MM, we need to sample hypotheses with wide range of p. and thus, we need a wide range o², To efficiently cover a wide range of o", we make the exponent equally spaced such as σ 10 where 3 > 0 and set the have 10 -5-5 to 1. Figure 15c shows the test accuracy with respect to B E {0.01, 0.05, 0.1, 0.5, 1}. and there is no significant performance difference.
G ADDITIONAL RESULTS
G.1 COMPARING WITH OTHER UNCERTAINTY METHODS WITH SEEDING
To clarify whether LDM-S's gains over the standard uncertainty methods are due to weighted seeding or to LDM's superiority, LDM-S's performance is compared with those methods to which weighted
30

---

Published as a conference paper at ICLR 2024
LDM-S
Rand Entropy
Margin
Coresot
ProbCov
DEAL
ENG
BADGE
BATT
Dolan-Mort More curve
LDM-
0.0
5.2
4.0
0.7
5.8
3.9
4.0
1.2
2.2
3.1
Rand
0.0
0.0
0.0
0.1
2.7
0.0
14
0.1
0.0
0.9
5
Entropy
0.0
4.2
1.
0.0
LDM-S: AUC=4.47
Margin
0.0
0.44...7
0.0
0.0
2.6
3.0
0.7
16
2.5
Rd(0)
Rand; AUC=2.04
AUC=2.84
Coresct
0.9
0.7
0.0
Margin; AUC=3.98
Coreset: AUC=1.05
ProbCov
0.0
2.7
0.1
4.5
0.0.0.22111
0.4
ProbCov; AUC=2.92
DBAL
0.0
2.7
1.1
8.6
11200001110
DBAL: AUC=2.47
ENS; AUC=4.09
ENS
1.90.11
2.
BADGE; AUC=3,99
BAIT: AUC=3.26
BADGE
0.0
4.5
5.5
2.6 0.1 0.0
BAIT
0.6
2.0
5.2
2.8
0.2
0.2 0.0
1
5
3.2
1.7
4.7
1.7
0.3
1.7
(a)
(h)
Figure 17: Comparison with BAIT across OpenML #6, #156, #44135, MNIST, CIFARIO, and SVHN datasets. (a) Dolan-Moré plot. (b) The penalty matrix.
seeding is applied. Figure 16 shows the test accuracy with respect to the number of labeled samples on MNIST, CIFARIO, and CIFARI00 datasets. Overall, even when weighted seeding is applied to the standard uncertainty methods, LDM-S still performs better on all datasets. Therefore, the performance gains of LDM-S can be attributed LDM's superiority the standard uncertainty measures.
G.2 COMPARISON across DATASETS WITH BAIT
The performance profile and penalty matrix between LDM-S and BAIT are examined on OpenMI. #6, #156, #44135, MNIST, CIFAR1O, and SVHN datasets where the experiments for BAIT conducted. Figure 17a shows the performance profile w.rt. d. LDM-S retains the highest (& over all considered 0's, which means that our LDM-S outperforms the other algorithms, including BAIT. Figure 17b shows the penalty matrix. It is also clear that LDM-S generally outperforms all other algorithms, including BAIT.
G.3 COMPARISON per DATASETS
Table 5 shows the mean + std of the test accuracies (%) w.r.t. the number of labeled samples for OpenML #6, #156, #44135 with MLP; MNIST with SCNN; CIFARIO and SVHN with K-CNN; CIFAR 100, Tiny ImageNet, FOOD101 with WRN-16-88 and ImageNet with ResNet-18. Overall, LDM-S either consistently performs best or is at par with other algorithms for datasets, while the performance of the algorithms except LDM-S varies depending datasets.
31

---

Published as a conference paper at ICLR 2024
Table 5: The mean + std of the test accuracies (%) w.r.t the number of labeled samples. (bold=underlined: best performance, bold: second -bstt performance
61.43 0.01
73.55 0.00
78.52 0.01
81 81.84 + 0.00
84.39 $4.39 0.01
86.73 0.01
88 44 0.00
89.76 0.00
90.57 90.57 0.00
91.28 4: 0.00
67.62 1 0.03
76.04 +: 0.02
77.68 - 0.01
78 0.02
78.89 + 0.01
79.29 0.01
80.45 0.01
80.70 0.01
81 11.85 4 0.02
84.17 0.02
78.82 0.01
89.50 0.01
0.00
0.01
+ 0.01
0.00
95.43 +.00 0.00
95.64 + 0.01
95.84 + 0.00
95.65 + 0.00
93.49
BATT
92.29
94.41
94.87
61.65 0.01
75.13 0.01
82.60 0.00
84.81 0.00
87.04 0.00
88. 31 0.00
89.18 0.00
90.21 0.00
91.35 + 0.00
71.35 + 0.02
83,74 + 0.02
86. 68.68 0.01
.97 0.00
88 94 0.00
89.5 89.59 #.00
89.99 0.00
90.28 0.00
90.49 0.00
90.73 +
78.33 0.01
88 65.60.6 0.00
92.06 0.01
93.42 0.00
94.28 0.01
95.12 0.00
13.53 0.00
95 83 0.01
95.98 0.00
96.26 0,00
BADGE
79.8 79.85
60.96 + 0.02
75.53 0.01
81.30 + 0.01
84.24 0.01
86.82 + 0.00
88.74 0.01
90.10 + 0.01
90.96 0.00
91.70 0.00
92.62 + 0,00
67.97 1 0.02
82. $2.19 + 0.02
86.38 + 0.01
88.17 0.00
89.21 + 0.00
89.88 + 0.00
90.23 + 0.00
90.48 + 0.00
90.75 0.00
91.01 11.11+00 0.00
78. 16.6 0.02
88 + 0.00
92. 92.18 + 0.00
0.01 93.70 0.01
94.82 2 0.01
95.29 0.01
95.53 +..3+ 0.01
95.58 + 0.00
95.72 0.01
0.01
96.13 0.00
ENS
58. = 0.02
70.59 + 0.01
75. 15.98 0.01
79.01 + 0.00
81.73 4 0.00
84.20 0.01
86. 86.00 00 0.01
87.43 # 0.01
88. 88.83 + 0.00
89 89.69 69 + 0.00
64. 1..10 0.04
70.78 + 0.01
72.06 - 0.02
72.82 0.02
72.55 + 0.03
72.87 1 0.02
73. 73.06 0.01
0.02
73.92 0.03
76.56 0.02
86.5 + 0.01
90.63 0 0.00
92.65 92.65 0.00
93.78 0.00
94.57 0.01
95.26 4 0.00
95.4 55.48 1 0.00
95.63 + 0.00
96.21 0.00
DBAL
72. 88
73.
61.00 = 0.01
73.10 0.00
77.71 + 0.01
80.15 80.15 0.01
82.21 # 0.01
84.01 # 0.01
85.04 0.00
85 85.95 95.95 + 0.00
86. 86.90 = 0.01
87.72 # 0.00
70.02 + 0.01
82.68 + 0.01
85 55.65 + 0.00
86. 79 0.00
87.56 + 0.01
88.51 + 0.00
89.03 = 0.00
89. 99.464 0.00
89. 69.69.2 + 0,00
90.05 4 0.00
81.70 4 0,01
91.59 + 0.01
93.51 1 0.00
94.69 0.00
95.02 0.01
0.01
95.22 95.2240.00 0.00
95.57 95.57 0.00
95.73 + 0.00
95.79 + 0.00
95. ,6,9622 0.01
ProbCov
Continued on next page
61.23 0.02
73.66 + 0.01
78. 74.64 0.01
81.26 +.0.1
83.17 83.17 0.01
85.00 0.01
86.22 0.00
87.22 0.00
87.85 0.01
88.49 88.49 0.01
61.15 61.15 0.03
6 0.03
0.04
40 0.05
63.59 0:05
67. #
69. 14.14 0.02
70.02 70.02 0.04
70.03 0.05
70.92 0.05
73.92 0.00
84,92 0.01
89 89.48 0.01
91.29 0.01
92.47 0.00
93.03 0.00
93.61 0.00
94. 98.18 0.01
94.41 0.00
94.59 0.00
Coreset
63.92
65.46
65.40
61 11.22 = 0.03
74 94 1 0.01
80.57 = 0.00
83.91 + 0.01
86.41 = 0.00
88 88.5944 59 0.01
89. 76 0.00
90.83 = 0.00
91 11.50= 0.00
92.36 - 0.00
67.95 - 0.03
81 L8 - 0.02
86.75 = 0.01
88. 14 0.00
83. 83.8366 2 0.00
89 83 = 0.00
90 = 0.00
90.67 1 0.00
90.85 0.00
91.09 # 0.00
81 31.33 0.01
92.10 0.00
94.12 0.00
95.30 = 0.00
96.03 = 0.00
96. 96.28 28 0.00
96.38 + 0.00
96.44 + 0.01
96.38 # 0.00
96.21 0.00
Margin
56.92 + 0.01
66.38 + 0.01
70.62 # 0.02
73.61 - 0.02
77 + 0.02
81.80 0.01
85.12 0.01
87.37 0.00
88.57 = 0.00
89.54 + 0.00
65.23 0.02
76.42 # 0.03
83.11 0.01
85.95 0.01
87.65 # 0.01
83.13 = 0.00
89.88 = 0.09
90. 14 0,00
0.00
90.62 0.00
0.01
0.02
91.17 0.01
93.26 0.00
94.41 + 0,00
95.13 4 0.00
95.62 4 0.00
95.93 # 0.00
95.84 = 0.01
96.40 1 0,00
Entropy
90.37
75.67
86.18
86.
60.64 0.01
72.51 0.00
77.49 0.00
80.20 0.00
82.06 0.00
83.62 0.01
84.77 0.01
85. 95.96552 0.01
86.77 0.00
88. 00 0.01
70.30 + 0.02
83.27 0.01
0.01
0.00
87.63 0.01
88.31 0.00
88.78 88.78 0.00
89.11 0.00
89 0.00
89.67 0.00
77.44 17.44 0.02
86.21 0.01
89.18 89.18 0.01
91.05 0.01
91.90 0.00
92.35 0.00
92.81 0.00
93.29 93.29 0.00
93.42 +.001
0.01
93.73 0,01
0.01
86 20
89.67
87
62.42 0.01
76.29 0.01
$1.62 0.01
34.74 0.00
87 .05 + 0.00
89. .2.12 0.00
0.00
$1.0622 0.00
91 0.80 0.00
92.53 0.00
09.78 0.02
83. 33.08 + 0.02
87 ..30 - 0.01
0.00
89 .3.3 0.00
= 0.00
90.43 0.00
90.70 0.00
90.95 0.00
0.00
82.28 0.01
92,65 0.01
94.51 = 0.00
95.34 0.01
95.86 0.00
96.13 0.00
96.27 = 0.00
96.51 + 0.00
96.60 + 0.00
96.62 2 0.00
LDM-S
90.35
90. 00.08
91.19
#44144
156
88.
Open
Open
400
800
1,200
1,600
2,000
2,400
2,800
3,200
3,600
4,000
200
400
600
800
1,000
1,200
1,400
1,600
1,800
2,000
Open
200
400
600
800
1,000
1,200
1,400
1,600
1,800
2,000
32

---

Published as a conference paper at ICLR 2024
87.07 1 0.01
92.99 - 0.01
94.93 + 0.00
96.09 + 0.00
96.64 + 0.,00
97.11 + 0.00
97.28 1 0.00
97.49 0.00
97.65 + 0.00
9 0.00
49.48 0.00
56.35 + 0.01
60.39 0.01
63.00 1: 0.00
65.32 0.00
66.82 #.01
67.99 + 0.00
69.42 0.01
77.91 4 0.00
83.13 0.00
85.54 1.544.0.44 0.00
87.49 0.00
88.61 + 0.01
89.29 : 0.00
90.07 + 0.00
90.52 + 0.00
BAIT
97.97
BADGE
$5.43 - 0.02
92.53 0.01
94.68 0.00
95. 95.64 0.01
96.33 #.00
96.82 0.00
97.02 0.00
97.46 0.00
97.61 #.00
97.78 0.00
0.01
+ 0.01
60.54 0.01
63.93 +
0.01
65. 5.30 0.00
67.11 0.01
68.42 0.00
69.08 0.00
78.31 +.00
83.49 - 0.00
85.68 0.00
87.32 87.32 0.01
88. 58 0.00
89 20,20 + 0.00
89.90 .0 0.00
90. 10 10.10=0.000 0.00
50.23
56.74
85.34 + 0.01
91.70 + 0.01
94_30 0,00
96.46 + 0.00
96. 96.94 1 0.00
97.36 - 0,00
97.56 0,00
97.63 + 0.00
97.75 1 0.00
49.93 0.01
56.39 + 0.01
0.01 60.34 0.01
63.32 + 0.00
64.99 0.01
66.78 + 0.01
68. + 0.01
0.01
69.23 0.01
0.01
77.49 + 0.00
83.23 + 0.01
85.85 1 0.01
87.23 0.00
88. 0.00
89.31 # 0.01
90.04 + 0.00
90.32 0.00
ENS
95.82 +
78.59 + 0.01
88. 88.43 43 + 0.01
93. 33.03 +3.03 0.00
95. 15.80 0.00
96. 80.0041 + 0.00
96.95 0.00
97.31 0.00
97.51 9 0.00
97.77 0.00
55.53 + 0.01
59. 4 0.01
62.31 0.00
64 0D 0.01
66. 16.12.00.00 0.01
67.94 97.94 77.44 0.01
0 0.01
78.42 0..00..0 0.01
83.27 + 0.01
86.00 0.00
87.49 0.00
88.91 + 0.00
89.61 + 0.00
90.34 + 0.00
90.77 + 0.00
DBAL
68. 08.82
95. 55.22
49.51
Table 5 Continued from previous page
86.61 + 0.01
92.4 92.44 + 0.01
94.30 .0 + 0.00
95.4 + 0.00
96. 96.13 13.13 0.00
96. 96.63 - 0.00
96. 66.98 1 0.00
97.00 7,006 17.0640.0 0,00
97 97.44 0.00
97.63 # 0.00
19.664 0.01
56.09 0001
59.99 + 0.00
62.73 1 0.01
64.32 38 0.01
66 28.28 0.1
67.60 = 0.00
68.45 # 0.00
0.01
82.55 + 0.01
84.59 0.00
85,92 0.00
86.89 09.8944 # 0.00
87.57 + 0.00
88.22 + 0.00
88. 80 + 0.00
ProbCov
77.56
56.09
Continued on neXL page
79 19.29 + 0.03
87.37 = 0.02
90. 90 = 0.02
92.84 0.02
93.70 +.001
94.77 0.01
95.21 0.01
95.38 0.01
95.97 0.00
95.84 0.01
47.44 0.01
0.01
56. 56.30 0.01
58. 0.00
61.08 0.01
62.84 0011
63.50 0.01
64.44 64.44 0.01
0.00
80.62 0.01
81.95 0.01
0.00
84.21 0:00
84.73 8 0.00
85.25 85.25 0.00
86, 83 13 # 0.00
Coreset
52.95
75.84
83.
84. 84.862 - 0.01
92.17 = 0.01
94.67 64.67 = 0.00
95. 85.87 0.00
96. 96.34 0:00
0.00
9 0.00
97.15 0.00
97 97.46 0.00
97.68 9 0.00
97. 97.84- = 0.00
56.51 - 0.01
60.49 + 0.00
62.81 1 0.01
64.97 0.00
66.75 2 0.01
67.87 = 0.01
13.13 0.01
77 77.94 .4.94. - 0.01
83.61 - 0.01
85 - 0.01
87. 0.00
88. 88.11 11.11 : 0.00
89.03 .3 = 0.00
89.62 = 0.00
90.45 = 0.00
Margin
99.35 +
80.67 + 0.04
90.83 # 0.01
93.95 + 0.00
95.3 # 0.00
96.00 - 0.00
96.78 - 0.00
97.12 0,00
97.41 # 0.00
97.69 # 0.00
97.88 # 0.00
48.96 0.01
55.35 # 0.01
59.68 + 0.01
62.60 0.00
64 64.42 1 0.00
66 66.29 # 0.00
67.77 # 0.01
68.62 0.00
76.25 + 0.01
82.33 0.00
85.33 0.00
86.78 4 0.00
38.09 # 0.00
88.84 # 0.00
89.65 = 0.00
90. 16 0,00
Entropy
81.32 11.32 0.02
88. 88.08 0.01
90. 99 0.01
92.45 0.01
93.51 0.001
0.01
94.22 0.00
94.78 0.00
95. 0.00
95. 44 0.00
95. .8 0.00
49. 0.01
56.04 0.01
59.99 0.00
62.69 0.01
64.56 0.01
65.87 0.00
67.50 0.01
68.51 0.01
77.22 0.01
81.55 0.01
83.61 0.00
85.05 0.00
0.00
86.59 0.00
87.28 0.00 0.00
87.72 0.00
Rand
85.
87.0 37.08 = 0.01
92.92 0.00
0.00
96.01 0.00
5 0.00
96.96 0.00
97.33 0.00
0.00
97.77 0.00
97.95 = 0.00
50.30 0.00
57.01 0.01
61 1..30 0.01
64.09 + 0.00
65. 5..7925 0.00
67 .7.28 + 0.01
68.83 = 0.00
70.10 0.00
79.02 19.02.4 0.01
83.76 0.00
86. .6.08:2 0.00
0.00
88. 6- = 0.00
89.56 56 0.00
90.04 = 0.00
90.61 0.00
LDM-S
94.8822
97.58
87
CIFAR10
MNIST
120
220
320
420
520
620
720
820
920
1,020
1,400
2,600
3,800
5,000
6,200
7,400
8,600
9,800
SVHN
L.00
2,600
3,800
5,000
6,200
7,400
8,600
9,800
33

---

Published as a conference paper at ICLR 2024
BAIT
30.89 + 0.00
36.69 + 0.01
40 .4.34 0.01
46.20 0.01
48. 46 0.00
49. .0,20-2 0.01
50.54 0.01
52.06 0.01
55.63 # 0.01
23.70 0.01
27.65 0.00
31.21 0.00
34.20 0.00
36.88 0.01
38. 91 0001
40.70 = 0.01
42.01 = 0.01
25.55 25.55 0
29.83 # 0.01
34.32 3 0.01
37. 878 0.01
41.69 #.01
45.17 0.01
48.3 48.39 0.01
50.93 50.93+0.00 0.01
41.90 + 0.01
46.52 + 0,01
0.01
52.95 + 0.01
BADGE
43.44 33
49. 888
31.09 + 0.01
36.42 + 0.00
40.04 0,00
42.80 0.01
45.53 1 0.01
47.58 4: 0.01
48.52 0.01
50.10 0.01
51.74 0.01
55.03 + 0.01
23.23 0.01
27.29 + 0.01
30.82 0.01 0.01
33.73 - 0.00
36.11 + 0.01
38.3 + 0.01
40.73 + 0.01
42.90 + 0.01
25.54 0.00
29.56 + 0.01
33.71 1 0.01
36,82 0.01
40.66 + 0.01
43.93 + 0.01
47.49 0.00 0.00
50.12 0.01
41.92 0.00 0.00
46.49 1 0.01
49.72 0.01
52.46 0.00
ENS
80.80 + 0.01
36.32 + 0.01
40.24 + 0.01
43.3 43.32 0.01
41 16.10.0..0 0.01
48. 48.23 + 0.01
48. 48.99 99 0.01
50.60 0.01
52.29 - 0.00
55.72 0.01
27.70 0.01
31 31.30 0.01
34.27 1 0.01
36. 88 0.00
39 39.08 + 0.01
40.92 + 0.02
42.59 + 0.02
26.06 4 0.01
30.44 + 0.01
35.12 0.01
38 48 0.00
42. 46 16.16+00. 0.01
45. 45.20 + 0.01
48. 48.69 69 + 0.01
51.52 0.01
DBAL
23.71
Table 5 Continued from previous page
31.76 + 0.01
37.68 + 0.01
41.43 + 0.01
44.02 + 0.01
46 46.55 - 0.01
48 48.24 - 0.01
48 82.82410 0.01
50.34 + 0.00
52.02 # 0.00
55. 55.70 0.01
24.06 + 0,00
28 28.22 + 0.01
31.64 + 0.01
34.54 + 0,01
36.79 + 0.01
39 39.02 + 0.02
40.73 # 0.00
42.70 0.01
25.91 + 0.00
30.40 + 0.00
34.70 + 0.01
38. 38.00 00 0.01
41.60 # 0.01
44.58 + 0.01
47.67 = 0.00
49.72 0.01
41.90 0.01
46.33 1 0.00
49 33 + 0.01
51.86 0.00
ProbCov
31.46 0.01
37.60 = 0.01
41.33 = 0.01
44.15 0.00
46.58 = 0.01
48.69 + 0.01
49.28 0.01
50.71 0.01
51.93 0.00
55.15 53.15 0.01
23.87 0.01
27.67 0.01
38 0.00
33.85 0.01
36. 38 0.01
38.36 38.36 0011
39.97 0.01
41. 41.16 0.02
26.49 - 0.01
31.03 = 0.00
35.40 0.01
38.62 0.01
42.37 0.01
45.24 = 0.01
48.70 = 0.01
51.22 = 0.00
41.27 0.00
45.41 + 0.00
48 38 0.01
50.96 0.00
Coreset
31.18 + 0.01
36.83 # 0.02
40.33 = 0.01
46. 10 0.00
0.00
48. 48.36 36.6 = 0.00
48 96 1 0.01
50 0.01
52.04 22.04: 2 0.01
55.52 0.00
27 27.39 0.01
30.90 0.00
33.72 1 0.00
36.78 0.00
39.51 = 0.01
41 $1.50 = 0.00
43.01 = 0.01
25.63 + 0.01
29.77 1 0.01
34.31 + 0.01
37.68 0.01
41 41.53 + 0.01
= 0.01
47.75 0.01
50.20 = 0.00
41 11.62 = 0.01
46.01 1 0.01
49 26 0.01
16 0.01
Margin
43.51
44 48
52. $2
23
30.74 + 0.01
36.30 + 0.00
39.91 + 0.01
43.16 0.01
45.77 = 0.01
47.86 + 0.01
48.66 - 0,00
50.49 0.01
52.10 0.01
55.73 # 0.01
23.13 0.00
26.72 = 0.00
30.30 0.01
33.38 + 0.01
36.16 0.00
38.34 # 0.00
40.04 # 0.01
41 41.40 0.01
25 25.42 4 0.00
29.10 0.00
33.01 + 0.01
36.18 + 0.01
39.71 # 0.01
43.24 = 0.01
46.64 = 0.01
49.67 = 0.01
41.25 + 0.00
45.58 + 0,01
0.01 48 8686622
52.18 # 0.00
Entropy
31.28 0.01
0.01
40 0.02
43.13 0.00
45.77 0.00
0.00
47.75 0.01
0.01
0.01
0.01
51.29 0.01
54.51 0.01
23.72 0.01
27.65 0.00
31.22 31.22 0.00
34,23 0.01
36.77 0.01
38. 38.59 0.01
40.25 0.02
41.73 4 0.01
0.01
29.89 0.01
34.19 14.19 0.00
37.15 37.05 0.01
40.74 0.00
43.81 0.01
47.37 0.01
50.24 $0.24 0.00
41.45 0.01
45. 45.90 0.00
49. 49.08 0.01
52.11 0.00
Rand
36.94
48.35
25 36.86
49.
31 11.85 2 0.00
37.61 + 0.00
40 88.8822 0.01
43 0.01
46.59 + 0.01
48.81 + 0.01
0.01
0.00
52.48 0.00
56.00 = 0.00
23.97 0.00
27.76 0.00
31.51 0.01
34.39 0.01
37.43 0.01
39.39 0.01
41.32 0.01
42.65 0.01
26.32 0.00
30.83 0.01
+ 0.01
0.01
42.26 0.01
45.46 0.01
48.88 0.00
51.40 0.00
0.00
0.00
50.14 0.00
53.53 0.00
LDM-S
49.41
50.94
35 25.0822
41 1.99
46.62
Tiny ImageNet
38
CIFARIO
7,000
9,000
11,000
13,000
15,000
17,000
19,000
11,000
23,000
25,00M ,00000
15,000
20,000
25,000
30,000
35,000
40,000
45,00 50,000
50,000
FOODIO,
9,000
12,000
15,000
18 000
21.000
24,000
27,000
30,000
ImageNet
192,188 10
256,240
320.300
384,360
2
34


Reviews:
[{"review_id": "qME13xB8Tx", "reviewer": "Reviewer_2mvn", "summary": "This paper presents LDM-S, an active learning method based on selecting samples close to the decision boundary. The paper starts by formulating a Least Disagree Metric (LDM) function, and then proceeds to implement it in a Monte Carlo fashion. Necessary assumptions and theorems are proven as needed. Over 5 repeats, the method is compared with other active learning methods and a t-test is used to check significance.", "questions": "* Why does $\\mathcal{H}$ need to be a Polish space as opposed to a more general metric space?\n* In Algorithm 2, when you compute $L_x$ via Algorithm 1, could you clarify the parameters passed? My understanding is that you pass it a hypothesis parameterized by $v$, number of samples $m$, and a \"small\" $s$ (as said in Sec. 2.3), but I'm unclear what $\\{ \\sigma^2_k \\}$ you pass.", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* At least in some parts of the paper, the flow is very good, and theorems and conclusions naturally lead to the next part.\n* The evidence for diversity in LDM-based active learning, as discussed in Appendix E.3, is extraordinary. Through an intuitive first example and then a real-world example (MNIST), the motivation is very clear. If possible, this should definitely be in the main paper to give readers better intuitions.\n* Ablation studies are presented whenever necessary to justify choices made, for example, for modifying the k-means++ seeding algorithm.", "weaknesses": "* Minor typo: Page 1, last paragraph: flips-flopped --> flip-flopped\n* Section 2.2 is rather rushed in its presentation, and details are not expanded on. For example, it is unclear why $\\mathcal{H}$ needs to be a Polish space (i.e., why second countability is necessary, for instance). In Theorem 1, $f$ is undefined. In Assumption 3, it seems that the phrase, \"that is monotone decreasing in the first argument\" refers to $\\alpha$, but that is not fully clear.\n* Similarly, some other details are presented with no clear rationale. For example, in (6), why is p(x) squared?\n* In Figure 2a, LDM sometimes samples on or very close to the decision boundary. Please change the color of the LDM crosses so they are more apparent.", "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": "9ie8vBV7QI", "reviewer": "Reviewer_o58y", "summary": "Framed in the field of active learning, this paper presents LDM (least disagree metric), a novel concept to quantify the distance between an instance and the decision boundary of a classifier. Along with the theoretical definition of LDM, the authors provide an asimptotically consistent estimator of LDM as well as a practical algorithm to calculate it. Based on this notion of LDM, they define a new acquisition procedure in active learning, by favoring low values of LDMs and enforcing diversity. Empirical evaluation shows that the proposed approach is competitive or superior against other state-of-the-art active learning methods in various datasets and with different architectures.", "questions": "Other questions/comments: \n\n* The effect of each hyperparameter is studied independently. Nothing is said about how they\naffect each other. Does the choice of one hyperparameter (number of MC samples, batch size, LDM stop condition\nand σ interval) affect each other?\n\n* Which metric/score is used to quantify performance in section 4.2? Accuracy is mentioned in\nthe appendix, but it is not entirely clear to me.\n\n* x should be present in the input in algorithm 1, right?\n\n* Perhaps, Assumption 3 is over-complicated: $\\sup_{\\epsilon\\in(0,1)} \\lim_N α(N, \\epsilon)= 0$ amounts to saying\nthat $\\lim_N α(N, \\epsilon)$ exists and is 0 when $\\epsilon\\in (0, 1)$.\n\n* I think $f$ in Theorem 1 should be $\\alpha$?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The quality of the exposition is high in general. The concepts and ideas are presented by combining an specific and accurate definition along with an intuition on their meaning. It is easy to follow the flow of the paper, and sections are well organized in a natural manner. \n\n* The experimental evaluation is a comprehensive one, including a wide range of baselines, datasets and architectures. Results are analyzed in a rigorous way, including statistical tests and popular active learning metrics such as the performance profile (Dolan-More plots). \n\n* The proposed metric LDM is clearly explained, and intuition is provided on how it reflects the distance to the decision boundary. It is well motivated and theoretically sounded. The example provided after Definition 1 is clarifying and helps understanding LDM definition.\n\n* LDM estimator, denoted as $L_{N,M}$, has a theoretical underpinning. Under some assumptions, $L_{N,M}$ is shown to converge in probability to the true value L when M scales logarithmically with respect to N.\n\n* 2D binary classification case is thoroughly investigated. Proposition 1 and Proposition 2 in the appendix theoretically confirm the intuition behind the choices made in this work.\n\n* Additional interesting experiments are included in the appendix. In particular: \n    * An effort to study the hyperparameters effect (number of MC samples, batch size, LDM stop condition and σ interval) is made.\n    * To favour diversity, the LDM estimator is corrected using a popular weighting strategy\nin active learning. The importance of this correction is addressed in the ablation study.", "weaknesses": "* I think there exists an important gap between the theoretical description of LDM (its definition in Section 2.1 and its estimator in Section 2.2) and how it is empirically evaluated (Section 2.3). In Section 2.3, the \"motivation\" paragraph includes several sentences to justify the procedure that the authors are going to follow to empirically evaluate LDM, but these sentences are just somewhat \"generic\"/\"loose\", and there is no guarantee that hypothesis in Section 2.2 are satisfied. Taking this into account, I wonder whether Section 2.2 is a core component of the contribution, or could be moved to the appendix, leaving room in the main text for other information that may be more central to the contribution (e.g. a more detailed description of the experiments or further empirical evaluations, which are currently in the appendix). \n\n* Even if Section 2.2 is moved to the appendix, I think that assumptions 1, 2 and 3 should be further motivated. The reader who is unfamiliar with mathematical concepts could get lost: what is a Polish space, and why is it necessary? Why is it necessary that ρ is Lipschitz? How restrictive is assumption 3? There are no references to other works where these assumptions are made. If they are common, these references should be provided. If not, authors should motivate and discuss them.\n\n* I also wonder whether the idea of \"sampling close to the decision boundary\" is the best way to go in active learning. Samples close to the decision boundary may not be informative if all the uncertainty that they present is of _aleatoric_ nature (inherent to the data, i.e. it cannot be reduced by further sampling training data). I think that more subtle distinctions on the types of uncertainty to be considered in active learning should be analyzed. My intuition is that this might be related to the finding that using LDM alone did not work properly, and a (somewhat ad-hoc) procedure to encourage diversity had to be introduced. \n\n* I think that more empirical evaluations should be moved to the main text (specially if theoretical details are moved to appendix, as suggested in the first point above). Right now, the experimental setting is not clearly described in the main text (it is deferred to Appendix C), and several ablation studies that could be interesting are \"lost\" in the appendix. \n\n* In some occasions, the statements made by the authors may lead to confusion. For example, in section 2.3, it is said that “...in Appendix B.2, we show that $E_w[ρ_M(h, g)]$ is monotone increasing in $σ^2$.”. One could think that this is shown in general. However, the proof only applies to the 2D binary classification case.\n\n* Related to the first point above, some aspects of theory are disconnected from the implementation:\n    * To implement $L_{N,M}$ the authors propose to sample near the learned hypothesis using standard parameter perturbation techniques. As authors state, this sampling scheme would need to satisfy Assumption 3. However, it is not explained why this specific form\nof sampling assures that the hypothesis spaces $\\mathcal{H}_n$ satisfy Assumption 3.\n    * In the 2D binary classification experiment, the performance of LDM-S, entropy, and random based sampling procedures are investigated. As authors state, true LDM is measurable in the 2D binary classification scenario. Thus, a study could be carried out on the error made when approximating L using $L_{N,M}$. Verification of bounds and rates of\nconvergence could be carried out.", "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": "zYR9Dbs8AQ", "reviewer": "Reviewer_ixMJ", "summary": "This paper proposes to use LDM estimator as heuristics to query samples for active learning. The estimator is proven to be asymptotically consistent under mild assumptions. Two approaches based on LDM, i.e., naive approach and LDM-S, have been considered for batch active learning.", "questions": "(1) Could the authors provide numerical or illustrative examples to show that LDM-based algorithm can be more effective in deep active learning? The authors provided the asymptotical analysis of the estimator but no analysis is provided for the relatedness of LDM to the final performance. In this case, it is better to provide some illustrative examples to show the effectiveness of LDM-based algorithms. \n\n(2) I am very interested to see the performance of active learning models with MC-dropout. MC-dropout is more efficient compared ensemble method.\n\n(3) Could the authors explain why they do not use more advanced posterior sampling method like [1] and [2]\n\nreferences:\n\n[1] Zhang, Ruqi, Chunyuan Li, Jianyi Zhang, Changyou Chen, and Andrew Gordon Wilson. \"Cyclical stochastic gradient MCMC for Bayesian deep learning.\" arXiv preprint arXiv:1902.03932 (2019).\n\n[2] Chen, Tianqi, Emily Fox, and Carlos Guestrin. \"Stochastic gradient hamiltonian monte carlo.\" In International conference on machine learning, pp. 1683-1691. PMLR, 2014.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(1) The paper maintains a high-quality presentation. The measure, proof of asymptotical consistency, and algorithms are clearly presented.\n(2) Extensive experiments on 3 openml datasets and 6 benchmark image datasets.", "weaknesses": "(1) Many baseline models are not considered in the paper's experiment, e.g., SAAL, Cluster-Margin, Similar, and [4]. \n\n(2) Computational cost analysis is lacking, including LDM estimation cost and LDM-S. What is the relationship to batch size, ensemble size, M, etc? The computational cost seems to be comparable to BADGE which has squared complexity to batch size. \n\n(3) The authors provide no analysis of the relatedness of LDM to active learner performance in the paper setting.\n\n(4) Careful discussion of limitations is lacking in the paper. There are many deep active learning algorithms coming out each year, each with its own pros and cons. A careful discussion of advantages and limitations will be very helpful to the community. One possible drawback is the need to use ensembles which takes more cost compared to methods that only use one model like BADGE and CoreSet.\n\n(5) The seeding strategy seems detached from the novel estimator. Many strategies, e.g., [1], [2], and [4], have been published to extend to batches. It is better to compare these strategies based on LDM and show if the performance improvement is consistent.\n\nreferences:\n\n[1] Kim, Yoon-Yeong, Youngjae Cho, JoonHo Jang, Byeonghu Na, Yeongmin Kim, Kyungwoo Song, Wanmo Kang, and Il-chul Moon. \"SAAL: Sharpness-Aware Active Learning.\" (2023).\n\n[2] Citovsky, Gui, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Rostamizadeh, and Sanjiv Kumar. \"Batch active learning at scale.\" Advances in Neural Information Processing Systems 34 (2021): 11933-11944.\n\n[3] Kothawade, Suraj, Nathan Beck, Krishnateja Killamsetty, and Rishabh Iyer. \"Similar: Submodular information measures based active learning in realistic scenarios.\" Advances in Neural Information Processing Systems 34 (2021): 18685-18697.\n\n[4] Kirsch, Andreas, Sebastian Farquhar, Parmida Atighehchian, Andrew Jesson, Frédéric Branchaud-Charron, and Yarin Gal. \"Stochastic Batch Acquisition: A Simple Baseline for Deep Active Learning.\" Transactions on Machine Learning Research (2023).", "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": "H0Lq4NPE5w", "reviewer": "Reviewer_L6Gr", "summary": "This paper proposes a new active learning technique based on novel selection strategy of unlabeled examples. Its main contributions are the following:\n\n— A new measure of closeness to the decision boundary the authors call the 'least disagree metric' (LDM). This is a metric inspired by the disagree metric of [1],  to play a role akin to \"margin-score\" or \"entropy\" in the standard active-learning algorithms like \"margin\" etc. As the authors mention, conceptually, a sample with a small LDM indicates that its prediction can be easily flip-flopped even by a small perturbation in the predictor. \n\n— An estimator of LDM that is provably asymptotically consistent under mild assumptions, and a simple Bayesian-perspective-inspired algorithm to empirically evaluate such an estimator. (LDM is intractable to compute in most cases so the authors propose.)\n\n— An LDM-based active learning algorithm (LDM-S) that, besides using LDM as the \"scoring function\" for selecting unlabeled examples\",  it also makes sure that there's \"diversity\" in the selected batch of unlabeled examples to be labeled. In particular, diversity is ensured via a modification of the k-means++ seeding algorithm and  without introducing additional hyperparameters. Finally, The authors compare their algorithm with several SOTA active learning techniques and show that it typically performs better.\n\n[1]  Theory of Disagreement-Based Active Learning. Foundations and Trends® in Machine Learning, 7(2-3):131–309, 2014, Steve Hanneke.", "questions": "Could the authors provide the mean running time of each algorithm considered for the Imagenet dataset?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "— Well-written paper\n\n— Novel, principled approach to active-learning.\n\n— A method of incorporating diversity in the sample selection without adding hyperparameters.\n\n— Extensive experimental evaluation.", "weaknesses": "— The proposed approach provides somewhat mild benefits compared to already existing approaches (although it is consistently the best or the second best approach in each scenario, and the best according to metrics that consider the average performance among all datasets.)\n\n—The datasets considered in this paper are somewhat small-scale, and so it's not clear to me whether the proposed approach is suitable for large-scale applications. For example, in Table 2 where the authors present the running time per dataset, Imagenet — which is the largest dataset considered in this paper, is missing.", "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)