Batch Active Learning at Scale
Authors: Gui Citovsky
Giulia DeSalvo
Claudio Gentile
Lazaros Karydas
Anand Rajagopalan
Afshin Rostamizadeh
Sanjiv Kumar
Venue: NeurIPS 2021 Poster (2021)
Keywords: active learning
large scale
batch active learning

Abstract: The ability to train complex and highly effective models often requires an abundance of training data, which can easily become a bottleneck in cost, time, and computational resources. Batch active learning, which adaptively issues batched queries to a labeling oracle, is a common approach for addressing this problem. The practical benefits of batch sampling come with the downside of less adaptivity and the risk of sampling redundant examples within a batch -- a risk that grows with the batch size. In this work, we analyze an efficient active learning algorithm, which focuses on the large batch setting. In particular, we show that our sampling method, which combines notions of uncertainty and diversity, easily scales to batch sizes (100K-1M) several orders of magnitude larger than used in previous studies and provides significant improvements in model training efficiency compared to recent baselines. Finally, we provide an initial theoretical analysis, proving label complexity guarantees for a related sampling method, which we show is approximately equivalent to our sampling method in specific settings.

Batch Active Learning at Scale
Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas,
Anand Rajagopalan, Afshin Rostamizadch, Sanjiv Kumar Google Research
Secittvssy,ggulline cggnniiill peeenile,,karre ananddr s sawijsjsajoooggle.ccoo
Abstract
The ability train complex and highly effective models often requires abun- dance of training data, which can easily become a bottleneck in cost, time, and computational resources. Batch active learning, which adaptively issues batched queries to labeling oracle, is a common approach for addressing this problem. The practical benefits of batch sampling come with the downside of less adaptivity and the risk of sampling redundant examples within batch risk that grows with the batch size. In this work, we analyze an efficient active learning algorithm, which focuses on the large batch setting. In particular, we show that our sampling method, which combines notions of uncertainty and diversity, easily scales to batch sizes (100K-10) IM) several orders of magnitude larger than used in previous stud- ies and provides significant improvements in model training efficiency compared to recent baselines. Finally, we provide an initial theoretical analysis, proving label complexity guarantees for a related sampling method, which we show approximately equivalent to our sampling method in specific settings.
Introduction
Training highly effective models for complex tasks often hinges on the abundance of training data. Acquiring this data can easily become a bottleneck in cost, time, and computational resources. One major approach for addressing this problem is active learning, where labels for training examples are sampled selectively and adaptively to more efficiently train the desired model over several iterations. The adaptive nature of active learning algorithms, which allows for improved data-efficiency, comes the cost of frequent retraining of the model and calling the labeling oracle. Both of these costs can be sigmificant. For example, many modern deep networks can take days or weeks to train and require hundreds of CPU/GPU hours. the same time, training human labelers become proficient in potentially nuanced labeling tasks require significant investment from both the designers of the labeling task and the raters themselves. A sufficiently large set of queries should be queued order to justify these costs.
To address these overhead costs, previous works have developed algorithms for the batch active learning setting, where label requests are batched and model updates are made less frequently, reducing the number of active learning iterations. Of course, there a trade-off, and the practical benefits of batch sampling come with the downside of less adaptivity and the risk of sampling redundant or otherwise less effective training examples within a batch. Batch active learning methods directly combat these risks in several different ways, for example, by incorporating diversity inducing regularizers or explicitly optimizing over the choice of samples within batch to optimize some notion of information.
However, the size of datasets grows to include hundreds of thousands and even millions of labeled examples (cf. Deng et al. [2009], Krasin et al. [2017], Van Horn et al. [2018]), we expect the active learning batch sizes to grow accordingly as well. The challenge with very large batch sizes is two-fold: first, the risks associated with reduced adaptivity continue to be compounded and, second, the batch
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

sampling algorithm must scale well with the batch size and not become a computational bottleneck itself. While previous works have evaluated batch active learning algorithms with batch-sizes of thousands of points (e.g., Ash et al. [2020], Sener and Savarese [2018]), in this work, we consider the challenge of active learning with batch sizes one to two orders of magnitude larger.
In this paper, we develop, analyze, and evaluate a batch active learning algorithm called Cluster- Margin, which we show can scale batch sizes of 100K or even 1M while still providing significantly increased label efficiency. The main idea behind Cluster-Margin is to leverage Hierarchical Agglom- erative Clustering (HAC) to diversify batches of examples that the model is least confident on. A key benefit of this algorithm is that HAC is executed only once on the unlabeled pool of data as a preprocessing step for all the sampling iterations. At each sampling iteration, this algorithm then retrieves the clusters from HAC over set of least confident examples and uses round-roo robii scheme to sample over the clusters.
The contributions of this paper are as follows:
We develop a novel active learning algorithm, Cluster-Margin, tailored to large batch sizes that are orders of magnitude larger than what have been considered in the literature.
We conduct large scale experiments using a ResNet-101 model applied to multi-label Open Images Dataset consisting of almost 10M images and 60M labels over 20K classes, to demonstrate significant improvement Cluster-Margin provides over the baselines. In the best result, we find that Cluster-Margin requires only 40% of the labels needed by the next best method to achieve the same target performance.
To compare against latest published results, we follow their experimental settings and con- duct smaller scale experiments using a VGG16 model on multiclass CIFARIO, CIFARIO0, and SVHN datasets, and show Cluster-Margin algorithm's 's competitive performance.
We provide an initial theoretical analysis, proving label complexity guarantees for margin- based clustering sampler, which we then show is approximately equivalent to the Cluster- Margin algorithm in specific settings.
1.1 Related Work
The remarkable progress in Deep Neural Network (DNN) design and deployment at scale has seen a vigorous resurgence of interest in active learning- based data acquisition for training. Among the many active learning protocols available in the literature (pool-basee query-based, etc.), the batch pool-based model of active learning has received the biggest attention in connection DNN training. This is mainly due to the fact that this learning protocol corresponds to the way labels are gathered in practical large-scale data processing pipelines.
stream- based, membership
Even restricting to batch pool-based active learning, the recent literature has become quite voluminous, and we can hardly do it justice here. In what follows, we briefly mention what we believe are among the most relevant papers to our work, with special attention to scalable methods for DNN training that delivered state of the art results in recently reported experiments.
In Sener and Savarese [2018], the authors propose a CoreSet approach to enforce diversity of sampled labels on the unlabeled batch. There, the CoreSet idea was used as a way to compress the batch into a subset of representative points. No explicit notion of informativeness of the data in the batch is adopted. The authors reported an interesting experimental comparison on small-sized datasets. Yet, their Mixed Integer Programming approach to computing CoreSets becomes largely infeasible as the batch size grows and the authors suggest a 2-approximation algorithm as a solution. As we find empirically, it seems this lack of an informativeness signal, perhaps coupled with the 2-approximation, limits the effectiveness of the method in the large batch-size regime.
Among the relevant papers in uncertainty sampling for batch active learning is Kirsch et al. [2019], where the uncertainty is provided by the posterior over the model weights, and diversity over the batch is quantified by the mutual information between the batch of points and model parameters. Yet, for large batch sizes and standard acquisition functions, their method also becomes infeasible in practice (we discuss this in more detail in the Section 3)." Another relevant recent work, and one
'More recently, i.c., contemporaneously with this publication, a more efficient variant of BatchBALD has been proposed by Kirsch et al. [2021]. The authors propose a simple idea to turn the original BALD algorithm of Houlsby et al. [2011] into batch active learning algorithm via softmax function over the current uncertainties

---

Algorithm 1 Hierarchical Agglomerative Clustering (HAC) with Average-Linkage
Require: Set of clusters C, distance threshold e, minimum cluster distance d min a B).
1: if |C| = or d > then
2: return C.
3: end if
4: A, 4- Pair of distinct clusters in C which minimize d(A,B)
[Ai[B] Eoe d(a,b).
5: if d(A B) < then
6: C- (AUBUJUCC {A, BJ.
7:
end if
8: return
which we will compare to, is Ash et al. [2020], where a sampling strategy for DNNs is proposed which uses M-MEANS++ seeding on the gradients of the final layer of the network in order to query labels that balance uncertainty and diversity. One potential downside to this approach is that the dimension of the gradient vector grows with the number of classes. In Wei et al. [2015] (see also the more recent Killamsetty et al. [2020]), the authors propose a submodular sampling objective that trades-off model uncertainty with a diversity-inducing regularizer, such as a facility location objective. Using naive greedy optimization to solve such objectives does not immediately scale to extremely large batch sizes of hundreds of thousands or more (such an implementation would require a linear number of function evaluations per greedy example added to the batch). More efficient "lazier-than-lazy" stochastic approximations (e.g.. Mirzasoleiman et al. [2015]) may be able to scale to very large batch sizes as they require only linear number of function evaluations overall (modulo a log(1/ (1/e) /t) factor, where e the approximation parameter). However, this may still be impractical computing the marginal gain is expensive (for example, if it grows approximately linearly with the pool size).
Further recent works related to DNN training through batch active learning are Zhdanov [2019], Shui al. [2020], Kim et al. [2020], Ghorbani al. [2021]. Zhdanov [2019], the authors trade off informativeness and diversity by adding weights to k-means clustering. The idea is similar in spirit our proposed algorithm, though the way we sample within the clusters is very different (see Section 2 below). Shui et al. [2020] proposes a unified method for both label sampling and seenaaiivenes-ddiveiiiiee
training, and indicates an explicit model the interactive procedure in active learning as a distribution matching problem measured by the Wasserstein distance. The resulting training process gets decomposed into optimizing DNN parameters and batch query selection via alternating optimization. We note that such modifications in the training procedure are not feasible in settings where only data selection can be modified while the black-box (very frequent in practice). The work of Kim et al. [2020] is
trade-off in label selection. The authors
training routine is treated bassd methods do not fully leverage the data distribution, while based on the idea that uncertainty- data distribution- based methods often ignore the structure of the learning task. Hence the authors propose to combine them in Variational Adversarial Active Learning method from Sinha et al. [2019], the loss prediction module from Yoo and Kweon [2019], and RankCGAN from Saquil et al. [201 8). Despite the good performance reported on small datasets, these techniques are not geared towards handling large batch sizes, which is the goal of our work.
From this lengthy literature, we focus on the BADGE [Ash et al., 2020] and CoreSet algorithms [Sener and Savarese, 2018] (described in more detail in Section 3) as representative baselines to compare against since they are relatively scalable in terms of the batch size, do not require modification of the model training procedure, and have shown sate-of-the-art results several benchmarks.
2 Algorithm
In this section, we present the Cluster-Margin algorithm, whose pseudo-code is in Algorithm 2. Throughout, refer to the model being trained and denote its corresponding weights/parametee w. Given an unlabeled pool of examples X, in each sampling iteration, Cluster- Cluster-Margin selects a diverse set of examples on which the model is least confident. We compute the confidence of a model
in the pool. This idea yields a faster and simpler algorithm than BatchBALD, but it does not appear to explicitly model diversity, other than sampling without replacement from the corresponding Gibbs distribution.
3

---

Algorithm 2 The Cluster-Margin Algorithm
Require: Unlabeled pool X, neural network f. seed set size p. number of labeling iterations margin batch size km. target batch size k S km. HAC distance threshold c.
1: S < 0, the set of labeled examples.
2: Draw P X (IP) p) seed set examples uniformly at random and request their labels. Set
S <- S.PP.
3: Train f on P.
4: Compute embeddings Ex on the entire set X, using the penultimate layer of f. 0).
5: Cx + HAC(
6: for = 1,2, ...,. do
7:
S; +0.. 0.
8:
M, t The km examples in X \ S with smallest margin scores. CM. + Mapping of M, onto Cx.
9:
Sort CN, ascendingly by cluster size. Set CAa, [C1, C2. ................................ Ceemall 1l as the sorted array, and set j t 1 as the index into C... while [. < kg do
10:
11:
Select x, random example in Cj.
13:
S; + S, U (z).
14:
if < I then
j - j +1
16:
else
17:
j f- The index of the smallest unsaturated cluster C...
18:
end if
19:
end while
20: Request labels for S, and set S SUS.
21: Train f on S.
22:
end for
23:
return S.
on an example the difference between the largest two predicted class probabilities, just as is done in the so-called "margin" uncertainty sampling variant [Roth and Small, 2006), and refer to the value the margin score. The lower the margin score, the less confident the model is a given example. In order to ensure diversity among the least confident examples, we cluster them using HAC with average-linkage (Algorithm 1). The batch of examples for which labels are requested is then chosen such that each cluster is represented in the batch.
In the following, describe the Cluster-Margin algorithm in detail, which can be decomposed into an initialization step, a clustering step, and a sequence of sampling steps.
Initialization step. Cluster- Margin starts by selecting seed set P of examples uniformly at random, for which labels are requested. A neural network is trained on and each x E X is then embedded with the penultimate layer of the network.
Clustering step. HAC with average-linkage is as a preprocessing step. Specifically, Algorithm 1 is run once on the embeddings of the examples in the entire pool, X, to generate clusters C. As described Algorithm HAC with average-linkage repeatedly merges the nearest two clusters A, B, so long as the distance d(A, B) = | ΣMEABEB d(a, b) S e, where is predefined threshold. In order to achieve speedup in this step, we describe an approach in Appendix A.2, where HAC is run only on the initial seed set P, and the examples in X \ P are projected onto the clusters of P. This reduces the clustering run-time from ( log [X]) to P log [P| [ \ Pl), without any observed loss in performance in our experiments.
Sampling steps. In each labeling iteration, we employ a sampling step that selects diverse set of low confidence examples. This process first selects M, a set of unlabeled examples with lowest margin scores, with [M] = km Then, M is filtered down to diverse set of k examples, where k; is the target batch size per iteration (ke km.). Specifically, given the km lowest margin score examples, we retrieve their clusters, CM. from the clustering step and then perform the diversification process. To select diverse set of examples from CM, we first sort Cas ascendingly by cluster size. As depicted in Figure 1, we then employ round-robin sampling scheme whereby we iterate through

---

Figure 1: Random round-robin sampling from clusters.
the clusters in the sorted order, selecting one example at random from each cluster, and returning to the smallest unsaturated cluster once we have sampled from the largest cluster. This process is then repeated until K examples have been selected. We sample from the smallest clusters first as they come from the sparsest areas of the embedded distribution and contain some of the most diverse points. We then leverage round-robin sampling to maximize the number of clusters represented in our final sample.
Cluster-Margin simple implement and admits the key property of only having step once as preprocessing. As we will see, this is in contrast to recent active learning algorithms, such BADGE and CoreSet, that run a diversification algorithm each sampling iteration. HAC with average-linkage runs in time (n 2 log n.) where = |X], but lends itself to massive speedup in practice from multi-threaded implementations [Sumengen al., 2021]. At each iteration, Cluster- Margin takes time (n log r2) to sample examples, whereas BADGE and CoreSet take time O(kn), which in the large batch size setting (e.g.. k ()(r))) can be far more expensive practice.
the clustering
3 Empirical Evaluation
Here, we present thorough experimental results comparing the Cluster-Margin algorithm against several ofate-of-theeart baselines different image datasets. We consider both the large scale Open Images dataset and small scale datasets including CIFARIO, CIFARI00, SVHN. Depending on the type of dataset, consider different neural network architectures, which we describe in detail below. Finally, additional baselines and/or data sets that have been added to the initial version of this article presented in Appendix A.3. This appendix will continue be updated further evaluations completed and the most up-to-date version will be found at https//arxiivorr//bb2200.77. 14224
3.1 Baselines Considered
For all experiments, we consider a set of baselines that consists of a classical Uncertainty Sampling algorithm, as well as two recent active learning algorithms, BADGE and CoreSet, that have been shown to work well in practice [Ash et al., 2020, Sener and Savarese, 2018]. We also conducted initial comparisons to the FASS algorithm of Wei et al. [2015] (see Appendix A.3).
Uncertainty Sampling (Margin Sampling): selects A examples with the smallest model confidence (or highest uncertainty) as defined by the difference of the model's class probabilities of the first and second most probable classes. That is, letting X be the current unlabeled set, Uncertainty Sampling selects examples E X that attain mingex Prw [012]] Pr [82 xr] where Pr [0]=] denotes the probability of class label according the model weights w and where Φ1 = arg max Pr [y/ and d2 arg max Prw [y/ æx] are the first and second most probable class labels according to the model [Roth and Small, 2006].
BADGE: selects & examples by using the &-MEANS+ seeding algorithm on {yz : a E X] where Ga. is the gradient embedding of example using the current model weights w. For cross-entropy loss and letting | = denote the number of classes, the gradient Iu = [9 (1), .... (t)] is composed of I blocks. For each y [4], (y) (Prw [y|[x] - - )2, where Z the penultimate embedding layer of the model on example x and 01 = arg max y Pr, [y|æ] is the most probable class according to
the model weights w [Ash et al., 2020].
Approximate CoreSet (k--cnterr): selects & examples by solving the k-center problem on {z. X where 2n is the embedding of x derived from the penultimate layer of the model [Sener and Savarese, 2018]. In the original algorithm of Sener and Savarese 22118, the authors solve a mixed integer program based on k-center. Instead, we use the classical greedy 2-approximation where the next center is chosen as the point that maximizes the minimum distance to all previously chosen centers, which is also suggested by the authors when greater computational efficiency is required.
5

---

Images
Positives
Negatives
Train
9,011,219
37,668,266 19,856,086
Validation Test
41,620 125,436
367,263 1,110,124
228.076 689,759
Table I: Open Images Dataset v6 statistics by data split.
Open Images, Eatch Size 100K
Open Images, Batch Size IM
0.70
0.84
0.77
0.80
Fooled
0.75
0.76
0.7
Cloaaer Mat gin
QureSec
Margih
0.72
0.4
0.6
3/8
1.2
0.0
0.4
06
0.8
1.0
Number of Labeled Examples
Number Of Labeled Examples
1e7
Figure 2: Pooled average precision of various active learning methods function of the number of labeled examples, using active learning batch sizes of 100K (left figure) and 1M (right figure). The mean and standard error as computed across three trials is shown. (The standard error bars are indeed barely visible.)
Random Sampling: selects examples uniformly at random from the set X. This baseline allows us to compare the benefit an active learning algorithm has over passive learning.
3.2 Open Images Dataset Experiments
We leverage the Open Images v6 image classification dataset [Krasin et al., 2017] to evaluate Cluster- Margin and other active learning methods in the very large batch-size setting, i.e. batch-sizes of 100K and IM.
Open Images vó is multi-label dataset with 19,957 possible classes with partial annotations. That is, only subset of these classes are annotated for a particular image (where on average, there are classes annotated per image). The label for any given class is binary, i.c. positive or negative. Thus, we have positive label for image (img1) and class (dog) pair, this implies that there is a dog in the image img1. Similarly, negative label does not appear in the image, img2. Since in practice we need to decide which class to annotate for given image, all active learning methods will be sampling image-class pairs and receiving binary (positive/negative) label.
image-clase pair, (img2, dog), implies that dog
Table lists the number of images well as the number of positive and negative labels applied across images within the train, validation, and test folds. The training fold serves as the unlabeled pool which the active learning methods sample from. For a more detailed description of the dataset and distribution of labels across different data folds please visit the Open Images website.?
We train ResNet-101 101 model implemented using tf-slim with batch SGD using 64 Cloud TPU v4's each with two cores. Each core fed 48 examples per SGD iteration, resulting in an effective SGD batch of size 64 x 2 48 6144. The SGD optimizer decays the learning rate logarithmically after every x 10 examples and uses an initial learning rate of 10-4 connected hidden layer of 128 dimensions and use global pooling induce 128-dimensional feature embedding, which is needed by Marstnr-Margin as well as the BADGE and CoreSet baselines.
insert a final fully-
We use fine-tuning learning scenario in order to maximize training stability and reduce training variance: all trials are initialized with model pre-trained on the validation split using 150K batch

---

BADGE
CoreSet
Margin
Random
Cluster-Margin 100K
66%
53%
71%
52%
Cluster-Margin IM
38%
40%
37%
35%
Table 2:
The percentage of labels used by Cluster-Margin to achieve the highest pooled average precision of baselines on Open Images Dataset v6, for batch sizes of 100K and 1M.
SGD steps. Additionally, we sample seed set of 300K image-class pairs uniformly at random from the unlabeled pool and train for an additional 15k steps. After this initialization phase, the active learning methods then sample fixed number of image-class pairs (we consider both 100K and 1 M)) from the unlabeled pool at each active learning iteration. This additional sample augments the set of image-class pairs that have been collected up to that point and the model is then fine-tuned for an additional I 15k steps using this augmented training set. We run trials with different random seed set for each method, with 10 active learning iterations per trial.
Recall, Cluster-Margin clusters the unlabeled pool as an initialization step at the beginning of the active learning process. In this case, HAC is run over the pool of images using feature embeddings extracted from the pre-trained model. We run a single-machine multi-threaded implementation [Sumengen et al., 2021] and, in all cases, we set km 10k, We select such that the average cluster size of C is at least 10, allowing us to exhaust all clusters in the round-robin sampling. This allows Cluster-Margin to naturally sample images, but as discussed previously we want to sample image-class pairs. Thus, the sampling of k pairs is computed in two steps: first Cluster-Margin samples A images, then given all the potential classes with labels available in this set of k images (recall, on average there will be 6k for this dataset), we sample k image-class pairs uniformly at random.
The baseline methods also have to be modified for the multi-label setting. CoreSet follows a similar process Cluster-Margin where it first samples &o images, then it samples & image-class pairs uniformly as random. Margin Sampling samples according to margin scores per image-class pair by using a binary classification probability per individual class. Similarly, BADGE calculates gradients per image-class pairs (that is, the gradient is composed of /=2 blocks), and runs the k-MEANS++ seeding algorithm on these image-class pair gradients.
BADGE and CoreSet runtimes are (ddnk) where d is the dimension, A the batch size and n is the size of the unlabeled pool. For the Open Images dataset, n s 9M, d = 256, and k is either 100K or IM and thus, in order to run BADGE and CoreSet efficiently on this dataset, we partitioned uniformly random the unlabeled pool and ran separate instances of the algorithm in each partition with batch size /e/ m where m is the number of partitions. For the batch size 100K setting, we used 20 partitions for BADGE, while CoreSet did not require any partitioning. For batch size 1M, we use 20 and 200 partitions for CoreSet and BADGE, respectively. These parameters were chosen to ensure each active learning iteration completed in less than 10 hours, for all active learning methods.
The mean and standard error across trials of the pooled average precision (AP) metric (see Dave et al. [2021] for details) for each method is shown in Figure 2, for both the 100K and 1M batch-size settings. As expected, all active learning methods provide some improvement over uniform random sampling. Among the other baselines, in our experiment Margin sampling outperforms both the CoreSet and BADGE algorithms, apart from the final iterations of the IM batch-size setting. Finally, find that the Cluster- Margin algorithm significantly outperforms all methods in this task. In the 100K batch-size setting, the Margin algorithm is the second best method and achieves a final pooled AP of more than 0.76 after training with 1.3M examples. The Cluster-Margin algorithm achieves this same pooled AP after receiving only ~920K examples a reduction of 29%. In the 1M batch-size setting, we see even more extreme savings over the next best sampling method, with 60% reduction in labels required to achieve the same performance. The percentage of labels required by Cluster-Margin to reach the final pooled AP of other methods is summarized in Table 2.
Finally, note that Margin was run as a baseline to ablate the effect of diversifying the low-confidence examples via clustering. As can be seen in Figure 2 and Table 2, Cluster-Marght requires the labeling of only 37% (resp. 71%) of examples compared to Margin for a batch size of 1M (resp. 100K).
'It is possible that a highly efficient parallelized approximate k- A-MEANS++ and k-center implementation would allow to avoid partitioning the BADGE and CoreSet baselines.
7

---

(3/48115, Tatre
CHARR10 Butch Siww 26
Suhri, Barch
0.2
0.0
0.40
0.00
044
6.00
Duste
Randary
wWW. 17h00
1A00 17h00 19973 27 Taaann 17h00 W030
1000 12500
2500 3150
10800
20500
25006
27506 3000
17300 17530 1990 "TiE 2000 7240n 2i0e 70h0n sai
Narioe
Figure 3: Accuracy of various active learning method a function of the number of labeled examples, using active learning batch sizes of 5K. The mean and standard error as computed across 10 trials is shown.
3.3 CIFARIO, CIFARIOO, SVHN Experiments
In this section, we compare our algorithm against the aforementioned baselines on three multi-class image datasets in the small batch-size setting. Although the focus of the paper is on the large scale setting, where we expect the largest headroom lies, the goal of these experiments proposed method performs well in smaller scale settings as well. Specifically, we consider CI CIFAR 100, and SVHN, which are datasets that contain 32-by 32-by-32 color images [Krizhevsky, 2009, Netzer et al., 2011 1. For CIFARIO 10 and CIFAR 100, the task is to classify the object in the image while for SVHN, the task is to classify street view house numbers. For CIFAR100, we used the 100 fine-grained labels. See Table 3 in the appendix for more details on these datasets.
verify that the
We train VGG-16 convolutional neural network model as implemented in the tf-keras library [Simonyan and Zisserman, 2015, Chollet et al., 2015J. We use batch SGD with learning rate fixed to 0.001 and SGD's batch size set 100. We use the default pre-trained image-net net weights to initialize the model. We add two dully-connecter layers of 4096-dimension and prediction layer as the final layers of network. The embedding layer used for Cluster-Mait Margin, BADGE and CoreSet are extracted from the penultimate layer of 4096 dimensions. In case of BADGE, we partition the data to improve efficiency on CIFAR 100 (as discussed in the previous section); no partitioning was needed for CIFAR10 or SVHN. For all Cluster- Margin experiments, we set km = 1 1.25 and set such that the average cluster size of is least 1.25, allowing us to exhaust all clusters in the round-robin sampling.
Since all datasets are multi-class, each active learning method will sample images (as opposed to image-class pair as was done in the previous section). Each active learning method is initialized with seed set of size 10,000 which was sampled uniformly at random from X and at each sampling iteration, the method will select 5,000 images. The sampling procedure is then repeated for iterations. We repeat this entire experiment for ten trials and average the results.
Figure 3 shows that Cluster-Margin outperforms all baseline methods in terms of accuracy on CI- FARI0 and CIFAR 100 while both Cluster-Marghe and Margin Sampling admit similar performance on SVHN, that is above all other baselines (similar performance is seen with classification accu- racy). BADGE attains a performance close to that of Margin Sampling all datasets except on SVHN where Margin Sampling outperforms BADGE. Surprisingly, CoreSet does not go beyond the performance of Random Sampling on all datasets, which is perhaps due our using of the 2 2-approximation for solving the k-center problem. In summary, even in the smaller scale setting, we find Cluster- Margin to be competitive with or even improve upon baselines.
4 Theoretical Motivation
We now provide an initial theoretical analysis to motivate the empirical success of Cluster-Margin. To this effect, we step through a related algorithm, which we call Cluster-Margin that more amenable to theoretical analysis than Cluster-Margin, albeit less practical. We establish theoretical guarantees for the Cluster-Margin algorithm, and show these guarantees also hold for the Marginn algorithm in specific settings, which will help shed some light Cluster Margin's 's functioning.
8

---

At high level, the Cluste--MarginV Algorithm first samples uniformly along the margin of hypothesis consistent with the collected data so far. Then, selects from these points a diverse batch by leveraging a volume-based sampler that optimizes a notion of diameter of the current version space. If the volume-based sampler on the embedding space follows HAC- sampling of the Cluster-Margin Algorithm, then Cluster-Margin and Cluster-Margin V are almost equivalent, other than the fact that Cluster-Margin's uniformly samples the data in the low margin region, instead of ranking all examples by margin scores and then extracting diverse pool from them. Moreover, since the data in a deep neural embedding space tend to have a small effective dimension [Arora et al., 2019, Rahbar et al., 2019], and our active learning algorithms do in fact operate in the embedding space, we work out this connection in a low dimensional space.
The first sampling step of the Cluster- Cluster-MarginY algorithm mimics that of the standard Margin Algorithm of Balcan et al. [2007]. Just as in the analysis Balcan and Long [2013], we prove that Mouster-Margin' admits generalization guarantees under certain distributions. The Cluster-Margin V Algorithm admits label complexity bounds that improves over the Margin Algorithm by factor / that depends on the efficacy of the volume-based sampler, improvement which is magnified when the data distribution is low dimensional.
After establishing this guarantee for general B. we give a specific example bound on the value of this factor 3 of the form 3 = d/ log(k)), where d is the dimensionality of the embedding space. This result holds for particular hypothesis class and optimal volume-basee sampler, and suggest that an improvement is possible when d < log k. that is. when either the dimensionality of the embedding space is small or when the batch size le is large, which is the leitmotif of this paper. We then show that this volume-based sampler is, in fact, approximately equivalent to the Cluster-Margin algorithm under certain distributions. We complement this result by also showing that log le is an upper bound on the improvement in query complexity for any sampler.
4.1 B-efficient Volume-Based Sampling and Connection to Cluster-Margin
We operate here with simple hypothesis spaces, like hyperplanes which, in our case, should be thought of as living in the neural embedding space.
Given an initial class H of hyperplanes, we denote by V; = (w E H sign (w x) = y. V(x, y) T) the version space at iteration i, namely, the set of hyperplanes whose predictions are consistent with the labeled data, T, collected thus far. Given labeled set S. we also define the closely related quantity Vi(S) {w E V; sign(w: (w- x) y, V(z, v) E S}. Further, let d(w, w') = PrawD (sign( w x)) + sign(w' z)}. and define Di) = wEV.i1) d(w,, w'), which can be thought of as the diameter of the set of hyperplanes in Vg consistent with S.
Definition 4.1. Let S. be a set of k241 points that have been drawn uniformly at random from given set X. We say that V is 8-efficient volume-based sampler, for 3 E (0, 1), for every iteration i, (.() S (S,),, where S is the set of kc+1 points chosen by V in X.
This definition essentially states that the sample selected by V shrinks the diameter of the version space by a factor 3 more compared to that of a simple random sample.
The Cluster-Marging
Algorithm (pseudo-code in Algorithm 3 in Appendix B) at each iteration first selects consistent hyperplane úù over the labeled set T. It then selects uniformly at random a set X; of points from within the margin, so that & E X; satisfies Iw;; x| < bj. The algorithm then queries the labels of a subset S. C X, of size k I [Xil/y from X,, where y > 1 is a shrinkage factor for the the diversity enforcing subsampling. Recall that in experiments with Cluster-Margin (Algorithm 2) on Open Images, we set this factor 7 to 10. The subset s is selected sampler.
here by B-efficient
In Appendix B (Theorem B.1 therein) we show that replacing a uniform sampler within the low margin region (as is done by the standard Margin Algorithm of Balcan et al. [2007]) by 3-effficient volume-based sampler improves the label complexity by a factor (3.
For specific hypothesis class and volume sampler, we now prove a bound on B, and elucidate the connections to the Cluster-Margin algorithm under certain stylized distributions on the embedding space. All the proofs can be found in Appendix B.
Theorem 4.2. Let X C [0, 1]d with distribution D Di product of 1-dimensional distri- butions and H {le:sull lo E [0, } be the set of indicator functions rectangles with one
9

---

corner at the origin. Assume that k olvn). Let volume-based sampler V choose the points Sh = - (arg mingex || F. (jd/k)eslles = l..... k/d} where F; denotes the cumula- tive distribution function of D and e; is the ith unit coordinate vector. Then V is a B-efficient volume-buue baanee sampler with 3 log(
This theorem implies that volume based sampler operating on a -iwdeiinniional embedding space may achieve a label complexity that d/ log(k) times smaller than that of the Margin Algorithm in Balcan and Long [2013], which can be substantial in practice, especially when d is small and the batch size & large.
We connect this particular volume- basee sampler to the Gtuster-Margin algorithm of Section 2 in specific setting by considering the simple case of d 1 and uniformly distributed points. In this case, sampling according to the strategy in Theorem 4.2 is equivalent to creating l clusters of equal sizes and choosing the center point from each cluster. This parallels the sampling of Cluster-Mart Margin with distance threshold 1/k, which would create k clusters of size at most 2c and sample a random point from each cluster, i.e., such sample achieves / = O [lo])))
We note that, while this is a positive initial connection, equating volume based samplers and the Cluster-Margin algorithm more generally an important open future direction.
We end this section by providing a general lower bound for B, which shows that the 1/ log(k) term in Theorem 4.2 cannot be improved in general.
Theorem 4.3. Let X' = Rd and H be the set of hyperplanes in TR.. Let n. = |X] and k = of v.). Then there exists a distribution D on Hd such that if X is sampled iid from D, and V is any sampler choosing k points, D,(S,)= (11 log (S,)) Thus B (2(1/ log for all V.
5 Conclusion
In this paper we have introduced a large batch active learning algorithm. Cluster-Margin, for efficiently sampling very large batches of data train big machine learning models. We have shown that the Cluster-Margin algorithm is highly effective when faced with batch sizes several orders of magnitude larger than those considered in the literature. We have also shown that the proposed method works well even for small batch settings commonly adopted in recent benchmarks. In addition, have developed an initial theoretical analysis of our approach based sampling mechanism. Extending this theoretical analysis to more general settings is an important future direction.
(aluue--bsed
Acknowledgments.
We thank the anonymous NeurIPS reviewers whose comments helped us improve both the content and the presentation of this paper well as the chair for their careful handling of this paper.
References
S. Arora, S. S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
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. URL https: // oppnoeeeeeeeeeeeeeeeeeeeeeeeeeee wwwp/eeeu//iiiiiee idrryum/ddddry
Maria-Florina Balcan and Phil Long. Active and passive learning of linear separators under log- concave distributions. In COLT, 2013.
Maria-Florina Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In COLT, 2007.
François Chollet et al. Keras. https: io, 2015.
Achal Dave, Piotr Dollár, Deva Ramanan, Alexander Kirillov, and Ross Girshick. Evaluating large-vocabulary object detectors: The devil in the details. arXiv preprint arXiv: 102.:2000000066 2021.
10

---

Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 245. leee, 2009.
A. Ghorbani, J. Zou, and A. Esteva. Data shapley valuation for efficient batch active learning. In arXiv:2/04.083/2v1,, 2021.
L. Holst, On the lengths of the pieces of stick broken at random. Journal of Applied Probability, 17:623-634, 1980.
N. Houlsby, F. Huszar, Ghahramani Z., and M. Lengyel. Bayesian active learning for classification and preference learning, 2011.
Krishnateja Killamsettyy Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glis- ter: Generalization based data subset selection for efficient and robust learning. arXiv preprint arXiv:2012 10630, 2020.
K. Kim, K.I. Park. D. Kim, and S.Y. Chun. Task-aware variational adversarial active learning. In arXiv:2002.0470992, 2020.
A. Kirsch, J. van Amersfoort, and Y. Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In arXiv:I906 08100815552 2019.
Andreas Kirsch, Sebastian Farquhar, and Yarin Gal. A simple baseline for batch active learning with stochastic acquisition functions. arXiv preprint arXiv:2106. 12059, 2021.
Ivan Krasin, Tom Duerig. Neil Alldrin, Vittorio Ferrari, Sami Abu-El-Haija, Alina Kuznetsova, Hassan Rom, Jasper Uijlings, Stefan Popov, Shahab Kamali, Matteo Malloci, Jordi Pont-Tuset, Andreas Veit, Serge Belongie, Victor Gomes, Abhinav Gupta, Chen Sun, Gal Chechik, David Cai, Zheyun Feng. Dhyanesh Narayanan, and Kevin Murphy. Openimages: A public dataset for large-scale multi-label and multi-class image classification., 2017. Dataset available from html.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Tech Report, 2009.
B. Mirzasoleiman, Badanidiyuru, A. Karbasi, J. Vondrak, and A. Krause. Lazier than lazy greedy. In Proc. Conference on Artificial Intelligence (AAAI), 2015.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrea Ng. Reading digits in natural images with unsupervised feature learning. NIPS Workshop on Deep Learning and Unsupervised Feature Learning. 2011.
Arman Rahbar, Emilio Jorge, Devdatt Dubhashi, and Morteza Haghir Chehreghani. Spectral analysis of kernel and neural embeddings: Optimization and generalization. In (rXiv::905.00005:2 2019.
Dan Roth and Kevin Small. Margin-based active learning for structured output spaces. In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou, editors, Machine Learning: ECML 2006, pages 413-424, Berlin, Heidelberg. 2006. Springer Berlin Heidelberg. ISBN 978-3-540-46056-55
Y. Saquil, K.I. Kim, and P. Hall. Ranking egans: Subjective control over semantic image attributes. In 28th British Machine Vision Conference (BMVC), 2018.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018. URL https:// openreview net/forum? iisiialuH-kiRHtt
C. Shui, C. Zhou, F. Gagne, and B. Wang. Deep active learning: Unified and principled method for query and training. In Proc. AiSTATS 2020, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Proceedings of ICLR, 2015.
Sinha, S. Ebrahimi, and T. Darrell. Variational adversarial active learning. In arXiv: arXiv:/904. 00370033 2019.

---

Baris Sumengen, Anand Rajagopalan, Gui Citovsky, David Simcha, Olivier Bachem, Pradipta Mitra, Sam Blasiak, Mason Liang. and Sanjiv Kumar. Scaling hierarchical agglomerative clustering to billion-sized datasets. In arXiv:2 1653, 2021.
Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie. The inaturalist species classification and detection dataset. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 8779, 2018.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International Conference on Machine Learning, pages 1954-1963. PMLR, 2015.
D. Yoo and I.S. Kweon. Learning loss for active learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Chicheng Zhang and Yinan Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. In COLT, 2021.
Zhdanov. Diverse mini-batch active learning. In arXiv:1901.059544 2019.
12


Reviews:
[{"review_id": "j_UAA5BRei1", "reviewer": "Reviewer_m1qg", "summary": "The paper introduces a new active learning acquisition function, Cluster-Margin, which clusters the samples with the lowest confidence scores (margin scores), and selects samples round-robin from the clusters to obtain a diverse set of low-confidence points. The experiments show that it works with very large batch sizes (100k--1M). Additionally, the paper provides an initial theoretical analysis of their algorithm.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "### Originality\n\nThe suggested method seems novel. Compared to the CoreSet algorithm in active learning, which computes a cover of all unlabeled pool points, Cluster-Margin essentially approximates a cover of mainly *low-confidence* pool points. \n\n### Quality\n\nThe submission seems technically sound. The experiment results are impressive. Especially, the results on Open Images are impressive, but also the results on CIFAR-10 and CIFAR-100 show good improvements over the baselines. The Open Images results are great because a real-life dataset has other characteristics than smaller curated datasets ala CIFAR-10, etc, which shows promise for real-world applications of the proposed method.\n\n### Clarity\n\nThe paper is very well written. The introduction and related work are great. The introduction is lacking citations, though. The algorithm and experiment section are also clear and of high quality. The theory section is difficult to understand and only seems to give a high-level overview of \"Cluster-MarginV\". The appendix is clearer on that. \n\nI believe it might be worth extracting the theory section into a separate contribution. I believe the algorithm and results are sufficient on their own. The fact that the theoretical motivation comes at the very end seems telling.\n\n### Significance\n\nI assume the paper will be of significance for practitioners. An expanded theory section could be interesting overall. It would be nice to have more results on additional large datasets. On the other hand, the paper already provides results for the common three datasets (CIFAR-10, CIFAR-100, and SVHN), and then provides results for the large and high-dimensional Open Images Dataset. Within the constraints, this seems absolutely reasonable.\n\n### Summary\nStrengths:\n\n+ method novel\n+ very well written\n+ experiments convincing: great results on large real-life datasets\n\nPotential improvements\n- the introduction might deserve more citations\n- theoretical motivation needs to be more fleshed out (it feels a bit tacked on in its placement in the paper)\n\n### Questions\n1. Were there any experiments run that recompute the embeddings after every acquisition round? This could improve the performance as the quality of the embeddings ought to improve as more labelled data is used for training (esp given the large batch sizes).\n2. Could Accuracy be provided instead of mAP for the CIFAR-10, CIFAR-100 and SVHN results? It is very hard to compare results as accuracy is the usual metric, and plots are not provided in the appendix either.\n\nI would be happy to increase my score if the above questions are answered.\n\n### Typos\n\nAlgorithm 2: line 5: $HAC(E_X, \\epsilon, \\infty)$: should the last argument be 0 instead of $\\infty$? Otherwise, Algorithm 1 will early out right away in line 1.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I agree with the author's answer in 1.c) about societal impact. Generally, the paper does not introduce concerns beyond the concerns of Active Learning itself, which are not part of the paper (but prior art): acquisition functions can introduce additional bias given how they select data to be labelled and included.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "j4OFhV2g0Nr", "reviewer": "Reviewer_8Xra", "summary": "This paper proposes a large-batch active learning Clustering based algorithm, Cluster-Margin. The authors show that the algorithm is more efficient and more effective than comparable approaches (Random, Margin, CoreSet and BADGE) on several benchmark datasets (Open Images Dataset, CIFAR10, CIFAR100 and SVHN). The authors also provide initial theoretical guarantees justifying the relevance of the algorithm. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Originality: \nThe algorithm seems to be novel and differs from previous comparable approaches like CoreSet or BADGE. Related work is adequately cited. \n\nQuality: \nThe authors show empirically that their algorithm, Cluster-Margin, is both more efficient (O(nlog(n) vs O(n√(n)) than CoreSet and BADGE in practice and more effective. In particular, the algorithm clearly outperforms CoreSet, BADGE, Margin and Random on the Open Images dataset. The algorithm requires 29% less labels than the second-best model in the 100k batch-size setting and 60% less labels in the 1M batch-size setting to achieve the same result (mAP). Cluster-Margin also outperforms all other methods on CIFAR10, CIFAR100 and obtains a similar performance on SVHN. \n\nThe authors also establish a theoretical guarantee for the Cluster-MarginV algorithm and show that those results hold for the Cluster-Margin algorithm in specific settings. In particular, they show that the Cluster-MarginV algorithm has a label complexity bound which improves over the Margin algorithm by a factor beta. They also show that this improvement is possible, under specific hypotheses like an optimal volume-based sampler, when the dimensionality of the embedding space is small or when the batch size k is large. They also show that the optimal volume-based sampler is approximately equivalent to the Cluster-Margin algorithm. They finally show that log(k) is an upper bound on the improvement of query complexity for any sampler. \nThe authors are aware and mention that their theoretical results are initial and that equating volume based samplers and the Cluster-Margin algorithm is an open research question. \n\nClarity: \nThe paper is very clear and well organized. The authors detail the hyper-parameters and compute details used for the experiments. The Cluster-Margin algorithm is also explained in detail.  \n\nSignificance: \nThe results are important as the algorithm allows for more efficient and effective large-batch-size active learning compared to existing methods. The authors also provide initial theoretical guarantees to explain the improvements obtained with the Cluster-Margin algorithm. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It would be interesting to perform some experiments to assess if the results hold for other data modalities, like NLP (text) or ASR/Speech (audio) for instance. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "MyEXiCjBTbE", "reviewer": "Reviewer_YihA", "summary": "The paper proposes a large-scale batch active learning approach.  \"large-scale\" means large-scale batches, e.g., 100K-1M. The key idea is to first perform Hierarchical Agglomerative Clustering on the pool of data points. Each time, it compute the confidences of each data point (based on the difference between the largest two predicted class probabilities), and picks the ones with the lowest confidence, matches their clusters, and then samples the data points across these clusters in a round-robin fashion. The clustering is based on the second last layer's neurons (given the input). Some experiments were conducted to confirm the effectiveness of the method. ", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper proposes a very simple method to select samples for active learning. The method makes sense. However, several severe issues are here. \n\n(1) Skeptical motivation. The paper claims it aims to select very large batches for active learning, like 100K-1M. That sounds violating the principle of active learning.  AL is intended to reduce the number of labels (and labeling cost) as much as possible. They key is to smartly select the training examples, so that we can use much less samples to achieve good performance (comparable to abundant data).  If you are able to offer so many training examples, why not just run batch learning on the large dataset?  Why do you use AL?\n\n(2) Skeptical efficiency. The paper claims that their batch selection is very scalable. However, the most costly part --- the HAC step, takes a complexity of O(n^2 log(n)) , which is very expensive and not scalable at all. see line 145. Although the paper says the HAC can be accelerated in practice from multi-thread implementation. The complexity is still there, more than quadratic to the number of candidates. Although the selection step is fast, the overall efficiency is very limited, given that the pool can be orders of magnitude larger than a batch. \n\n(3) The paper claims BatchBALD (line 86) is infeasible for large batch size in practice. I think this is a wrong claim. BatchBALD is greedy heuristics, and the point is added into the batch one by one. It scales linearly in the size of the batch and data pool. The paper needs to explain why it is infeasible for large batch sizes. \n\n(4) The paper mentions BatchBALD in Intro, but does not compare with it in the experiment. It misses an important soa as the baseline.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: A majority of reviewers voted for acceptance (including the ones shown as official reviewers and an emergency reviewer that I included last minute). The only reviewer voting for rejection is reviewer YihA, which seems to be too negative without strong justifications given that most of his claims are not supported by the other reviewers. I, therefore, have decided to accept the paper.
Decision: Accept (Poster)