Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds
Authors: Jordan T. Ash
Chicheng Zhang
Akshay Krishnamurthy
John Langford
Alekh Agarwal
Venue:  (2020)
Keywords: deep learning
active learning
batch active learning

Abstract: We design a new algorithm for batch active learning with deep neural network models. Our algorithm, Batch Active learning by Diverse Gradient Embeddings (BADGE), samples groups of points that are disparate and high-magnitude when represented in a hallucinated gradient space, a strategy designed to incorporate both predictive uncertainty and sample diversity into every selected batch. Crucially, BADGE trades off between diversity and uncertainty without requiring any hand-tuned hyperparameters. While other approaches sometimes succeed for particular batch sizes or architectures, BADGE consistently performs as well or better, making it a useful option for real world active learning problems.

Published as a conference paper ICLR 2020
DEEP BATCH ACTIVE LEARNING BY DIVERSE, UNCERTAIN GRADIENT LOWER BOUNDS
Jordan T. Ash
Chicheng Zhang University of Arizona
Akshay Krishnamurthy Microsoft Research NYC
Princeton University
John Langford Microsoft Research NYC
Alekh Agarwal
Microsoft Research Redmond
ABSTRACT
We design algorithm for batch active learning with deep neural network models. Our algorithm, Batch Active learning by Diverse Gradient Embeddings (BADGE), samples groups of points that are disparate and high magnitude when represented in hallueinated gradient space, a strategy designed to incorporate both predictive uncertainty and sample diversity into every selected batch. Crucially, BADGE trades off between uncertainty and diversity without requiring any hand-tumed hyperparameters. While other approaches sometimes succeed for particular batch sizes or architectures, BADGE consistently performs as well or better, making it a useful option for real world active learning problems.
1 INTRODUCTION
In recent years, deep neural networks have produced state-of-the-arr results on a variety of important super- vised learning tasks. However, many of these successes have been limited to domains where large amounts of labeled data are available. A promising approach for minimizing labeling effort is active learning, a learning protocol where labels can be requested by the algorithm in sequential, feedback-driven fashion. Active learning algorithms aim to identify and label only maximally-informe classifier can be trained with minimal labeling effort. As such, robust active learning algorithm for deep neural networks may considerably expand the domains in which these models are applicable.
samples, so that a high-performing
How should we design a practical, networks? Theory for active learning suggests version- ceroon-ssppe-ssseeeee approach (Cohn et al., 1994] Balcan at 2006). which explicitly or implicitly maintains set of plausible models, and queries examples for which these models make different predictions. But when using highly expressive models like neural networks, these algorithms degenerate to querying every example. Further, the computational overhead of training deep neural networks precludes approaches that update the model to best fit data after each label query, as is often done (exactly or approximately) for linear methods (Beygelzimer et al., 2010: Desa-Bianchi et al. 2009). Unfortunately, the theory provides little guidance for these models.
label-efficien active learning algorithm for deep neural
One option is to use the network's 's uncertainty to inform a query strategy, for example by labeling samples for which the model is least confident. In a batch setting, however, this creates pathological scenario where data in the batch are nearly identical, a clear inefficiency. Remedying this issue, we could select samples maximize batch diversity, but this might choose points that provide little new information the model.
For these reasons, methods that exploit just uncertainty or diversity do not consistently work well across model architectures, batch sizes, or datasets. An algorithm that performs well when using ResNet, for

---

Published as a conference paper at ICLR 2020
example, might perform poorly when using a multilayer perceptron. A diversity-based approach might work well when the batch size is very large, but poorly when the batch size is small. Further, what even constitutes a "large" or "small" batch size is largely a function of the statistical properties of the data in question. These weaknesses pose major problem for real, practical batch active learning situations, where data are unfamiliar and potentially unstructured. There no way to know which active learning algorithm best to use.
Moreover, in real active learning scenario, every change of hyperparameters typically causes the algorithm label examples not chosen under other hyperparameters, provoking substantial labeling inefficiency. That is, hyperparameter sweeps in active learning can be label expensive. As result, active learning algorithms need to "just work", given fixed hyperparameters, to a greater extent than is typical for supervised learning.
Based on these observations, we design approach which creates diverse batches of examples about which the current model is uncertain. We measure uncertainty as the gradient magnitude with respect parameters in the final (output) layer, which is computed using the most likely label according to the model. To capture diversity, we collect a batch of examples where these gradients span a diverse set of directions. More specifically, build up the batch of query points based these hallucinated gradients using the k-MEANS++ initialization (Arthur and Vassilvitskii (007), which simultancously captures both the magnitude of candidate gradient and its distance from previously included points in the batch. We name the resulting approach Batch Active learning by Diverse Gradient Embeddings (BADGE).
We show that BADGE is robust architecture choice, batch size, and dataset. generally performing as well as or better than the best baseline across our experiments, which vary all of the aforementioned environmental conditions. We begin by introducing our notation and setting, followed by a description of the BADGE algorithm in Section 3 and experiments in Section We defer our discussion of related work to Section
2 NOTATION AND SETTING
Define = K). Denote by X' the instance space and by Y' the label space. In this work we consider multiclass classification, so y = [K] Denote by D the distribution from which examples are drawn, by Dx the unlabeled data distribution, and by Dyjæ the conditional distribution over labels given examples. We consider the pool-based active learning setup, where the learner receives an unlabeled dataset U sampled according to Dx and can request labels sampled according to Dy x for any
U. We use En to denote expectation under the data distribution D. Given a classifier h X which maps examples to labels, and a labeled example (x, y), we denote the 0/1 error of h on (æ, y) fm (h(x), y) = T(h(r) F v)- The performance of a classifier h is measured by its expected 0/1 error, i.e. ED for (h(z). v)] Pr(a.))~-D (x) # y). The goal of pool-based active learning is find a classifier with a small expected 0/1 error using few label queries as possible. Given set S of labeled examples (a,, v), where each x E S is picked from U, followed by a label query, we use Eg as the sample averages over S.
+ y,
In this paper, we consider classifiers h parameterized by underlying neural networks f of fixed architecture, with the weights in the network denoted by 0. We abbreviate the classifier with parameters 0 as he since the architectures are fixed in any given context, and classifiers take the form ho(x) = argmax [x; y where fa; 9) E IRK is a probability vector of scores assigned to candidate labels, given the example x and parameters 0. We optimize the parameters by minimizing the cross- entsopy loss Es Es(EcE() (f 9). v)] over the
labeled examples, where (cE(P. v) Σ Ily i) In 1/p. In 1/P.-
2

---

Published as a conference paper ICLR 2020
Algorithm 1 BADGE: Batch Active learning by Diverse Gradient Embeddings
Require:
Neural network [2;; (), unlabeled pool of examples U, initial number of examples M, number of iterations T, number examples
batch B.
1: Labeled dataset S t .M examples drawn uniformly at random from U' together with queried labels.
2: Train an initial model 01 on S by minimizing Es (fcc(f((x 0),]]
3: for f = 1, ........ T: do
4: For all examples x in U SS:
1. Compute its hypothetical label ((x) - ho, (2)).
2.
Compute gradient embedding fr 3Mm
lCE( (f 0), (o=))) where Jom refers to param-
eters of the final (output) layer.
5: Compute St, random subset of S,S using the k-MEANS+ seeding algorithm on {g. : E U/U/A (S} and query for their labels.
6: S 5 SSSSU U..
7: Train model 0.41 on S by minimizing (s)fc
8: end for
9: return Final model Or+1-
3 ALGORITHM
BADGE, described in Algorithm [ starts by drawing initial set of M examples uniformly at random from and asking for their labels. It then proceeds iteratively, performing two main computations at each step t: a gradient embedding computation and sampling computation. Specifically, at each step 1, for every in the pool U, we compute the label ((z) preferred by the current model, and the gradient 9z of the loss on (æ, (x)) with respect the parameters of the last layer of the network. Given these gradient embedding vectors [gx E U}. BADGE selects set of points by sampling via the k-MEANS+ initialization scheme (Arthur and Vassilvitskil 2007). The algorithm queries the labels of these examples, retrains the model, and repeats.
We now describe the main computations - the embedding and sampling steps - in more detail.
The gradient embedding. Since deep neural networks are optimized using gradient-based methods, we capture uncertainty about an example through the lens of gradients. In particular, we consider the model uncertain about an example if knowing the label induces a large gradient of the loss with respect to the model parameters and hence a large update to the model. difficulty with this reasoning that we need to know the label to compute the gradient. As a proxy, we compute the gradient as if the model's current prediction on the example the true label. We show in Proposition that, assuming a common structure satisfied by most natural neural networks, the gradient norm with respect to the last layer using this label provides a lower bound on the gradient norm induced by any other label. In addition, under that assumption, the length of this hypothetical gradient vector captures the uncertainty of the model on the example: if the model is highly certain about the example's 's label, then the example's 's gradient embedding will have a small norm, and vice versa for samples where the model is uncertain (see example below). Thus, the gradient embedding conveys information both about the model's uncertainty and potential update direction upon receiving a label at an example.
The sampling step. We want the newly-acquired labeled samples to induce large and diverse changes to the model. To this end, want the selection procedure to favor both sample magnitude and batch diversity. Specifically, we want to avoid the pathology of, for example, selecting a batch of k similar samples where even just single label could alleviate our uncertainty on all remaining (k 1) samples.
A natural way of making this selection without introducing additional hyperparameters is to sample from a k D-eteerminnttl Point Process (k-DPP; (Kulesza and Taskar 2011). That is, select batch of k points
3

---

Published as a conference paper ICLR 2020
K-DPP
k-means++
OpenMLitS MLP. Batch size: 100
SVHN, ResNel, Batch size: 1000
x10" SVHN. ResNel, Betch size: 1000
0.90
0.80
Acaurrc
0.80
Acane9
0.0
Time
0.70
0040
0.30
0.99
0.40
2000
4000
0003 8000 1000000000000000000 #Labels querled
10000
20003
30003
40030
10000
20000
30000
40000
#Labela querled
#Labels quaried
Figure 1: Left and center: Learning curves for K-MEANS++ and k-DPP sampling with gradient embeddings for different scenarios. The performance of the two sampling approaches nearly perfectly overlaps. Right: A run time comparison (seconds) corresponding to the middle scenario. Each line is the average over five independent experiments. Standard errors are shown by shaded regions.
with probability proportional to the determinant of their Gram matrix. Recently, Derezinski and Warmuth (2018) showed that in experimental design for least square linear regression settings, learning from samples drawn from a k-DPP can have much smaller mean square prediction enror than learning from iid samples. In this process, when the batch size is very low, the selection will naturally favor points with a large length, which corresponds to uncertainty in our space. When the batch size is large, the sampler focuses more on diversity because linear independence, which is more difficult to achieve for large k, is required to make the Gram determinant non-zero.
Unfortunately, sampling from a k-DPP is not trivial. Many sampling algorithms (Kang 2013 Anari et al. 2016) rely on MCMC, where mixing time poses significant computational hurdle. The state-of-the-ar algorithm of Derezinsk (2018) has a high-order polynomial running time in the batch size and the embedding dimension. To overcome this computational hurdle, we suggest instead sampling using the k-MEANS++ seeding algorithm (Arthur and Vassilvitskii, 2007). originally made to produce good initialization for k-means clustering. k-MEANS++ seeding selects centroids by iteratively sampling points in proportion to their squared distances from the nearest centroid that has already been chosen, which, like a k-DPP, tends to select a diverse batch of high- -agnntuge samples. For completeness, we give a formal description the k- +-MEANS++ seeding algorithm in Appendix
Example: multiclass classification with softmax activations. Consider a neural network f where the last nonlinearity is softmax, i.e. (2); = e* </E/ efr. Specifically, is parametrized by 0 (W, V), where lour W (W1, (W....., Wx) kxd are the weights of the last layer, and V consists of weights of all previous layers. This means that f(; 0) = o(W z(x; V)), where is the nonlinear function that maps an input x to the output of the network's penultimate layer. Let us fix unlabeled sample æ and define P: = (z; 0); With this notation, we have
(cE(f(2:0)..) In Σ (mnater))
Wy 2(x; V).
Define 3h = aw (CE(E (a;; 0).y) for a label y and yz = u as the gradient embedding in our algorithm, where 9 argmax,e[K] Pt. Then the i-th block of gu (i.c. the gradients corresponding to label i) is
(gz)s = a
aw, (ce(f(x;)) = (p. - I(ğ = <x); V).
(1)
Based this expression, make the following observations:
4

---

Published as a conference paper ICLR 2020
1. Each block of gu is a scaling of <a; V), which the output of the penultimate layer of the network. In this respect, INr captures x's representation information similar to that of Sener and Savarese (2018).
2. Proposition 1 below shows that the norm of 9æ: is lower bound on the norm of the loss gradient induced by the example with true label y with respect to the weights in the last layer, that |g - | ll. This suggests that the norm of 9> conservatively estimates the example's influence on the current model.
3. If the current model is highly confident about æ, i.e. vector p is skewed towards a standard basis vector ej. then = J. and vector (p; [ū +)) has small length. Therefore, Ir has small length as well. Such high-confidence examples tend to have gradient embeddings of small magnitude, which are unlikely to be repeatedly selected by + at iteration
Proposition 1. For all y E (I,...,K, J, let -% =
0 JW (f:( v). Then
K
Σ
pi +1 2pv [=; v)I?.
2
Consequently, I = argmin |1
Proof. Observe that by Equation ①
1 Σ (p: T(y = (2)
Σ
p +1 -pp [1 1)12
The second claim follows from the fact that y = ar argmax yE[K) Py-
This simple sampler tends to produce diverse batches similar to k-DPP. As shown in Figure 1 switching between the two samplers does not affect the active learner's 's statistical performance but greatly improves its computational performance. Appendix | compares run time and test accuracy for both k-MEANS+ and k-DPP based sampling based on the gradient embeddings of the unlabeled examples.
Figure 2 illlustaaees the batch diversity and average gradient magnitude per selected batch for variety of sampling strategies. As expected, both k-DPPs and k-MEANS++ tend to select samples that are diverse (as measured by the magnitude of their Gram determinant) and high magnitude. Other samplers, such as furthest-first traversal for k--Cener clustering (FF-R-CENTER), do not seem to have this property. The FF-R-CENTER algorithm is the sampling choice of the CORESET approach to active learning, which describe in the proceeding section (Sener and Savarese 2018). Appendix F discusses diversity with respect uncertainty-based approaches.
Appendix B provides further justification for why BADGE yields better updates than vanilla uncertainty sampling in the special case of binary logistic regression (K 2 and <(x; V) I).
4
EXPERIMENTS
We evaluate the performance of BADGE against several algorithms from the literature. In our experiments, we seek to answer the following question: How robust are the learning algorithms to choices of neural network architecture, batch size, and dataset?
To ensure comprehensive comparison among all algorithms, we evaluate them in batch-mode active learning setup with A = 100 being the number of initial random labeled examples and batch size B varying from (100, 1000, 10000). The following is a list of the baseline algorithms evaluated; the first performs representative sampling, the next three are uncertainty based, the fifth is a hybrid of representative and uncertainty-base based approaches, and the last traditional supervised learning.
5

---

Published as a conference paper ICLR 2020
k-means++
Rand
k-center
OpenML I1S, MLP. Batch
SVHNN ResNet, Betch size: 1000
Open ML #6, MLP. Beach size: 100
Log delem of batch
Average fa norm in batch
250
-5002
reter
16 th
Wibaaaahyan wan
-1500
-2000
12
-750
-2:003
-1000
-30000
1250
2000
4020
8200 10500 12000 14000 #Labels queried
10500
20000
1000
63500
50000
2000 4000 GoOo 850o 10000 12000 1400 NLabels queried
#Labels queried
Figure A comparison of batch selection algorithms using our gradient embedding. Left and center: Plots showing the log determinant of the Gram matrix of the selected batch of gradient embeddings as learning progresses. Right: The average embedding magnitude (a measurement of predictive uncertainty) in the selected batch. The FF-K-CENTE
sampler finds points that are not as diverse or high-magnitude as other samplers. Notice also that k-MEANS++ tends to actually select samples that are both more diverse and higher-magnitude than k-DPP, potential pathology of the k-DPP's degree of stochastisity. Standard errors are shown by shaded regions.
1. CORESET: A diversity-based approach using coreset selection. The embedding of each example is computed by the network's penultimate layer and the samples at each round are selected using greedy furthest-fing first traversal conditioned on all labeled examples (Sener and Savarese (2018).
2. CONF (Confidence Sampling): An uncertainty-based active learning algorithm that selects examples with smallest predicted class probability, max f (a; 0), (c.g. Wang and Shang 2014
3. MARG (Margin Sampling): An uncertainty-baat active learning algorithm that selects the bottom B examples sorted according to the example's multiclass margin, defined as f(z 0)g- 1f fz:
0) w/ where
I and y are the indices of the largest and second largest entries of f(;; 0) (Roth and Small 2006).
4. ENTROPY: An uncertainty-basee
active learning algorithm that selects the top examples according to the entropy of the example's predictive class probability distribution, defined ()) where (p) Σ P; In l/p. (Wang and Shang 2014).
5. ALBL (Active Learning by Learning): A bandit-style meta-active learning algorithm that selects between CORESET and CONF every round (Hsu and Lin 2015).
6. RAND: The naive baseline of randomly selecting & examples query at each round.
We consider three neural network architectures: a two-layer Perceptron with ReLU activations (MLP), 18-layer convolutional ResNet (He al.] (016)), and 11-layer VGG network (Simonyan and Zisserman 2014). We evaluate our algorithms using three image datasets, SVHN (Netzer et al.) 2011). CIFARIO Krizhevsky 2009) and MNIST (LeCun al. 1998) and four non-image datasets from the OpenML repository (#6, #155, #156, and #184). We study each situation with active learning algorithms, including BADGE, making for 231 total experiments.
For the image datasets. the embedding dimensionality in the MLP is 256. For the OpenML datasets, the embedding dimensionality the MILP 1024, as more capacity helps the model fit training data. We fit
Because MNIST is dataset that is extremely easy classify, we only use MLPs, rather than convolutional networks, to better study the differences between active learning algorithms.
"The ML datasets are from openml org and selected two criteria: first, they have at Icast 10000 samples; second, neural networks have significantly smaller test error when compared to linear models.
6

---

Published as conference paper ICLR 2020
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
SVHN, ResNet, Betch size: 100
OpenMLan16, MLP. Betch size: 1000
CIFAR10, VGG, Batch size: 10000
0.50
0.50
Accuracy
0.70
0.85
0.70
0.00
0.50
0.75
0.80
030
0.10
0.85
15000 20000
2500 #Labels querled
5000
6000
20000 20000 85000 #Labels querled
#Labels querled
(a)
(b)
(c)
Figure 3: Active learning test accuracy versus the number of total labeled samples for a range of conditions. Standard errors are shown by shaded regions.
models using cross-entrope loss and the Adam variant of SGD until training accuracy exceeds 99%. We use a learning rate 0.001 for image data and of 0.0001 for non-image data. We avoid warm starting and retrain models from scratch every time new samples are queried (Ash and Adams 2019). All experiments are repeated five times. No learning rate schedules or data augmentation are used. Baselines use implementations from the libact library (Yang et al. 2017). All models are trained in PyTorch (Paszke et al. 2017).
Learning curves. Here we show examples of learning curves that highlight some of the phenomena we observe related to the fragility of active learning algorithms with respect to batch size, architecture, and dataset.
Often, we see that in early rounds of training, it better to do diversity sampling, and later in training, better to do uncertainty sampling. This kind of event is demonstrated in Figure 3a which shows CORESET outperforming confidence-based methods at first, but then doing worse than these methods later on.
In this figure, BADGE performs as well as diversity sampling when that strategy does best, and as well uncertainty sampling once those methods start outpacing CORESET. This suggests that BADGE is good choice regardless of labeling budget.
Marg Entropy
BADGE
0.0
9.18
10.97
12.56
3.88
13.16
10:04
12
6.81
Separately, we notice that diversity sampling only seems to work well when either the model has good architectural priors (inductive biases) built in, when the data easy to learn. Otherwise, penultimate layer representations are not meaning- ful, and diverse sampling can be deleterious. For this reason, CORESET often performs worse than random on sufficiently complex data when using a convolutional network (Figure 3b). That is, the diversity induced by unconditional random sampling can often yield batch that better represents the data. Even when batch size large and model has helpful inductive biases, the uncertainty information BADGE can give an advantage over pure diversity approaches (Figure 3c). Comprehensive plots of this kind, spanning architecture, dataset, and batch size are in Appendix
Coreset
1.65
2.02
0.0
6.55
3.08
8.13
6.56
Conf
0.54
2.78
7.61
0.33
5.96
6.08
Marg
10.87
Entropy
0.31
1.79
6.05
1.25
0.35
0.0
5.12
Rand
0.84
5.63
7.61
8.67
2.98
10.65
0.0
0.66
4.08
6.9
5.93
1.56
8.01
6.01
Figure 4: A pairwise penalty matrix over all experiments. Element P.,, corresponds roughly the number of times algorithm outperforms algorithm j. Column-wiss averages at the bottom show overall performance (lower is better).
7

---

Published as a conference paper ICLR 2020
Pairwise comparisons. We next show a comprehensive pairwise comparison of algorithms over all datasets (D), batch sizes (B), model architectures (A), and label budgets (L). From the learning curves, it can be ob- served that when label budgets are large enough, all algorithms eventually reach similar performance, making the comparison between them uninteresting in the large sample limit. For this reason, for each combination of (D, B, A), we select a set of labeling budgets L where learning is still progressing. We experimented with three different batch sizes and eleven aataset-architettue pairs, making the total number of (D, B, A) combinations x 11 = 33. Specifically, we compute no, the smallest number of labels where RAND'S ' accuracy reaches 99% of its final accuracy, and choose label budget L from {M + 2 B E [[Log (mo - / The calculation of scores in the penalty matrix P follows the following protocol: For each (D, B, A, L) combination and each pair of algorithms (i,j), we have 5 test errors (one for each repeated run), {e).....e?) et and .e).....ee) respectively. We compute the f-score as voR/S, where
1.0
A = 5
(el +)),
Σ
(c
6 - 1
Cumulative frequency
0.6
We use the two-sided (-test to compare pairs of algo- rithms: algorithm i is said to beat algorithm j in this setting if t > 2.776 (the critical point of p-value be- ing 0.05), and similarly algorithm j beats algorithm i < -27776. For each (D, B, A) combination, suppose there are D.A. different values of L. Then, for each L, if algorithm i beats algorithm j. accumulate penalty of 1/nD.B.A A. to Pt.j: otherwise, if algorithm j beats al- gorithm i, we accumulate penalty of L/n,,B.A to Pj The choice of the penalty value 1/np,BB. is to ensure that every (D, B, A) combination is assigned equal influence in the aggregated matrix. Therefore, the largest entry of P is at most 33, the total number of (D, B, A) combinations.
0.4
0.2
0.0
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
1.1
1.2
Normalized error
BADGE
Coreset
Marg Entropy
Rand
ALBL
Conf
Figure 5: The cumulative distribution function of normalized errors for all acquisition functions.
Intuitively, each row i indicates the number of settings in which algorithm beats other algorithms and each column j indicates the number of settings in which algorithm j beaten by another algorithm.
The penalty matrix in Figure 4 summarizes all experiments, showing that BADGE generally outperforms baselines. Matrices grouped by batch size and architecture Appendix D show similar trend.
Cumulative distribution functions of normalized errors. For each (D, B, A, L) combination, we com- pute the average error for each algorithm as é = - To ensure that the errors of these algorithms compute the normalized error of every algorithm i, defined as
the same scale in all settings, ne; = =ē; e where r is the index of the R RAND algorithm. By definition, the normalized errors of the RAND algorithm are identically in all settings. Like with penalty matrices, for each (D, B, A) combination, we only consider subset of L values from the set M 2 B: E [[log((no M)/B)ll} We assign weight proportional to 1 1/nD, A A to each (D, B, A, L) combination, where there are D.B.AA different I values for this combination of (D, B, A). We then plot the cumulative distribution functions (CDFs) the normalized errors of all algorithms: for value of the value is the total weight of settings where the algorithm has normalized error at most x; in general, an algorithm that has a higher CDF value has better performance.
We plot the generated CDFs in Figures 22 and 23 We can see from Figure 5 that BADGE has the best overall performance. In addition, from Figures and 23 in Appendix E., we can conclude that when batch size is small (100 1000) or when an MLP is used, both BADGE and MARG perform best. However, in the regime when the batch size is large (10000), MARG'S performance degrades, while BADGE, ALBL and CORESET are the best performing approaches.
8

---

Published as a conference paper ICLR 2020
5 RELATED WORK
Active learning is a been well-studied problem (Settles 2010, Dasgupta 2011: Hanneke 2014). There are two major strategies for active learning representative sampling and uncertainty sampling.
Representative sampling algorithms select batches of unlabeled examples that are representative of the unlabeled set to ask for labels. It is based on the intuition that the sets of representative examples chosen, once labeled, can act as surrogate for the full dataset. Consequently, performing loss minimization on the surrogate suffices to ensure low error with respect to the full dataset. In the context of deep learning, Sener and Savarese (2018); Geifman and Yaniv (017)) select representative examples based on core-set construction, fundamental problem in computational geometry. Inspired by generative adversarial learning, Gissin and Shalev-Shwartz (2019) select samples that are maximally indistinguishable from the pool of unlabeled examples.
On the other hand, uncertainty sampling is based on a different principle-to select new samples that maximally reduce the uncertainty the algorithm has on the target classifier. In the context of linear classifi- cation, [Tong and Koller (200T); [Schohn and Cohn (2000): Tuu et al.) (2005) propose uncertainty sampling methods that query examples that lie closest to the current decision boundary. Some uncertainty sampling
approaches have theoretical guarantees on statistical consistency (Hanneke) 2014; Balcan et al. 2006). Such
methods have also been recently generalized deep learning. For instance, Gal et al. (2017) use Dropout as an approximation of the posterior of the model parameters, and develop information basedd uncertainty reduction criteria; inspired by recent advances on adversarial examples generation, Ducoffe and Precioso (2018) use the distance between example and one of its adversarial examples as an approximation of its distance to the current decision boundary, and uses it as the criterion of label queries. An ensemble of classifiers could also be used to effectively estimate uncertainty (Beluch et al.) 20188).
There are several existing approaches that support a hybrid of representative sampling and uncertainty sam- pling. For example, [aram et al. (2004); Hsu and Lin (2015) present meta-active learning algorithms that can combine the advantages of different active learning algorithms. Inspired by expected loss minimization, Huang et al.) (210)) develop label query criteria that balances between the representativeness and informa- tiveness of examples. Another method for this is Active Learning by Learning (Hsu and Lin| 2015). which select whether to exercise diversity based algorithm training as a sequential decision process.
uncertainty based algorithm at each round of
There is also large body of literature on batch mode active learning, where the learner asked to select a batch of samples within each round (Guo and Schuurmans 2008 Wang and Ye 2015 Chen and Krause Wei et al., 2015 Kirsch et al. 2019). In these works, batch selection often formulated as an optimization problem with objectives based on (upper bounds of) average log- ligeeeke,,oodd, average squared loss, etc.
A different query criterion based on expected gradient length (EGL) has been proposed in the as well (Settles ct al. 2008). In recent work, Huang et al. (2016) show that the EGL criterion is related to the T T'optumality criterion in experimental design. They further demonstrate that the samples selected by EGL are very different from those by entropy- -based uncertainty criterion. ZZhan et al.] (2017a) use the EGL criterion in active sentence and document classification with CNNs. These approaches differ most substantially from BADGE in that they do not take into account the diversity of the examples queried within each batch.
There is wide array of theoretical articles that focus on the related problem of adaptive subsampling for fully-labeled datasets in regression settings (Han et al. [016 Wang al. 2018 Ting and Brochu 2018). Empirical studies of batch stochastic gradient descent also employ adaptive sampling to "emphasize" hard or representative examples (Zhang al. [011b]] Chang al. 2017). These works aim at reducing computation costs or finding a better local optimal solution, as opposed to reducing label costs. Nevertheless, our work is inspired by their sampling criteria, which also emphasize samples that induce large updates to the model.
9

---

Published as a conference paper ICLR 2020
As mentioned earlier, our sampling criterion has resemblance sampling from k-determinantal point processes (Kulesza and Taskar, 2011). Note that in multiclass classification settings, our gradient-based embedding of an example can viewed as the outer product of the original embedding in the penultimate layer and probability score vector that encodes the uncertainty information on this example (see Section 3). this view, the penultimate layer embedding characterizes the diversity of each example, whereas the probability score vector characterizes the quality of each example. The k-DPP is also natural probabilistic tool for sampling that trades off between quality and diversity (See Kulesza et al., [012] Section 3.1). We remark that concurrent to work, BByyk et al. (2019) develops k-DPP based active learning algorithms based on this principle by explicitly designing diversity and uncertainty measures.
6 DISCUSSION
We have established that BADGE is empirically an effective deep active learning algorithm across different architectures and batch sizes, performing similar to or better than other active learning algorithms. A funda- mental remaining question is: "Why?" While deep learning is notoriously difficult to analyze theoretically, there are several intuitively appealing properties of BADGE:
1. The definition of uncertainty lower bound the gradient magnitude of the last layer) guarantees some update of parameters.
2. It optimizes for diversity as well as uncertainty, eliminating a failure mode of choosing many identical uncertain examples in batch, and does so without requiring any hyperparameters.
3. The randomization associated with the k-MEANS++ initialization sampler implics that, even for adversarially constructed datasets, it eventually converges to a good solution.
The combination of these propertics appears to generate the robustness that we observe empirically.
REFERENCES
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 1994.
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In International Conference Machine Learning. 2006.
Alina Beygelzimer, Daniel J Hsu, John Langford, and Tong Zhang. Agnostic active learning without constraints. In Neural Information Processing Systems, 2010.
Nicolo Cesa-Bianchi, Claudio Gentile, and Francesco Orabona. Robust bounds for classification via selective sampling. In International Conference on Machine Learning, 2009.
David Arthur and Sergei Vassilvitskii. k-meanst+: The advantages of careful seeding. In ACM-SIAM
symposium on Discrete algorithms, 2007.
Alex Kulesza and Ben Taskar. k-dpps: Fixed-size determinantal point processes. In International Conference on Machine Learning, 2011.
Michat Dereziński and Manfred K Warmuth. Reverse iterative volume sampling for linear regression. The Journal of Machine Learning Research, 19(1), 2018.
Byungkon Kang. Fast determinantal point process sampling with application to clustering. In Neural Information Processing Systems, 2013.
10

---

Published as conference paper ICLR 2020
Nima Anari, Shayan Oveis Gharan, and Alireza Rezaci. Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes. In Conference on Learning Theory, 2016.
Michal Dereziński. Fast determinantal point processes via distortion-free intermediate sampling. arXiv preprint, 2018.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: core-set approach. In International Conference on Learning Representations, 2018.
Dan Wang and Yi Shang. A new active labeling method for deep learning. In 2014 International joint conference on neural networks, 2014.
Dan Roth and Kevin Small. Margin-basce active learning for structured output spaces. In European Conference on Machine Learning, 2006.
Wei-Ning Hsu and Hsuan- Tien Lin. Active learning by learning. In Association for the advancement of artificial intelligence, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint, 2014.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. IEEE, 1998.
Jordan T Ash and Ryan P Adams. On the difficulty of warm-starting neural network training. arXiv preprint, 2019.
Yao-Yuan Yang, Shao-Chuan Lee, Yu-An Chung, Tung-En Wu, Si-An Chen, and Hsuan-Tice - Lin. libact: Pool-based active learning python. arXiv preprint, 2017.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary Vito Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Burr Settles. Active learning literature survey. University of Wisconsin, Madison, 2010.
Sanjoy Dasgupta. Two faces of active learning. Theoretical computer science, 2011.
Steve Hanneke. Theory of disagreement-basee active learning. Foundations and Trends in Machine Learning, 2014.
Yonatan Geifman and Ran El-ia.. Deep active learning over the long tail. arXiv preprint, 2017.
Daniel Gissin and Shai Shalev-Shwartz. Discriminative active learning. arXiv preprint, 2019.
Simon Tong and Daphne Koller. Support vector machine active learning with applications text classification. Journal of machine learning research, 2001.
Greg Schohn and David Cohn. Less is more: Active learning with support vector machines. In International Conference Machine Learning, 2000.
11

---

Published as conference paper ICLR 2020
Gokhan Tur, Dilek Hakkani- and Robert Schapire. Combining active and semi-supervised learning for spoken language understanding. Speech Communication, 2005.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In International Conference on Machine Learning, 2017.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. arXiv preprint, 2018.
William H Beluch, Tim Genewein, Andreas Nürbberger, and Jan M Köhler. The power of ensembles for active learning in image classification. In IEEE Conference on Computer Vision and Pattern Recognition, 2018.
Yoram Baram, Ran El Yaniv, and Kobi Luz. Online choice of active learning algorithms. Journal of Machine Learning Research, 2004.
Sheng-Jun Huang, Rong Jin, and Zhi-Hua Zhou. Active learning by querying informative and representative examples. In Neural Information Processing Systems, 2010.
Yuhong Guo and Dale Schuurmans. Discriminative batch mode active learning. In Neural Information Processing Systems, 2008
Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode active learning. Transactions on Knowledge Discovery from Data, 2015.
Yuxin Chen and Andreas Krause. Near-optimal batch mode active learning and adaptive submodular optimization. In International Conference on Machine Learning.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International Conference on Machine Learning, 2015.
Andreas Kirsch, Joost Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In Neural Information Processing Systems 32, 2019.
Burr Settles, Mark Craven, and Soumya Ray. Multiple-instance active learning. In Neural Information Processing Systems, 2008
Jiaji Huang, Rewon Child, and Vinay Rao. Active learning for speech recognition: the power of gradients. arXiv preprint, 2016.
Ye Zhang, Matthew Lease, and Byron C Wallace. Active discriminative text representation learning. In AAAI Conference on Artificial Intelligence, 2017a.
Lei Han, Kean Ming Tan, Ting Yang, and Tong Zhang. Local uncertainty sampling for large-scale multi-class logistic regression. arXiv preprint, 2016.
HaiYing Wang, Rong Zhu, and Ping Ma. Optimal subsampling for large sample logistic regression. Journal the American Statistical Association, 2018.
Daniel Ting and Eric Brochu. Optimal subsampling with influence functions. In Neural Information Processing Systems, 2018.
Cheng Zhang, Hedvig Kjellstrom, and Stephan Mandt. Determinantal point processes for mini-batch diversification. Uncertainty in Artificial Intelligence, 2017b.
12

---

Published as conference paper ICLR 2020
Haw-Shiuan Chang, Erik Learned-Milled and Andrew McCallum. Active bias: Training more accurate neural networks by emphasizing high variance samples. In Neural Information Processing Systems, 2017.
Alex Kulesza, Ben Taskar, et al. Determinantal point processes for machine learning. Foundations and Trends in Machine Learning, 2012.
Erdem BIyık, Kenneth Wang, Nima Anari, and Dorsa Sadigh. Batch active learning using determinantal point processes, arXiv preprint, 2019.
Stephen Mussmann and Percy $ Liang. Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss. In Neural Information Processing Systems, 2018.
A THE K-MEANS+ SEEDING ALGORITHM
Here we briefly review the k-MEANS++ seeding algorithm by (Arthur and Vassilvitskii 2007). ). Its basic idea is to perform sequential sampling of & centers, where each new center is sampled from the ground set with probability proportional to the squared distance to its nearest center. It is shown in (Arthur and Vassilvitskii 2007) that the set of centers returned is guaranteed approximate the k-means objective function in expectation, thus ensuring diversity.
Algorithm 2 The +-MEANS++ seeding algorithm (Arthur and Vassilvitskii 2007)
Require: Ground set G C IRd, target size k.
Ensure: Center set C' of size C {ci}, where is sampled uniformly at random from G. for t = 2,....k do
Define Dz(z) mineec._, || cl12-
Ct + Sample from G with probability Eveo Da(a)
(z))
C++ C U
end for return C₁.
B BADGE FOR BINARY LOGISTIC REGRESSION
We consider instantiating BADGE for binary logistic regression, where y = (-1,+11 +1). Given linear classifier w, we define the predictive probability of w on x as (wlyz 0) = ayyw z)), where (2) Ite- is the sigmoid funciton.
Recall that (xx) is the hallucinated label:
+1, Pa (+1/2, 0) > 1/2.
5(x) -1, Pw (+1 1z, 0) < 1/22.
The binary logistic loss of classifier w on example (x, v) is defined as: E(w, (x, v)) = In(1 exp(- yw x²))
Now, given model wo and example x, we define 9. 2t fww, (x, 1) (1 Pw (0] 0)) (0))(----)) x)) as the loss à gradient induced by the example with hallucinated label, and 9. = au f(w, (x, = (1 (1-p..(y)l: ())- the loss gradient induced by the example with true label.
13

---

Published as conference paper ICLR 2020
OpenMLI66, MLP. Batch size: 100
OpenMLA6 MLP, Batch size: 1000
OpenMLaB MLP, Batch size: 10000
Accuracy
0.80
0.30
0.50
0.70
0.70
0.60
0.50
0.50
0.50
0.50
0.40
2000
4000
5020
8000
102001 14000 16000
2000
4000
8000
8030 r0930
12000 14007 16003
2503
4000
5000
8000
1000
#Labels queried
#Labelis queried
#Labels queried
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 6: Full learning curves for OpenML #6 with MLP.
OpenMLL1155
OpenMUI MLP,
OpenML
1.00
1.00
0.85
0.35
0.05
Accuracy
0.85
0.85
0.55
0.80
0.80
0.70
0.70
0.70
0.5
0.00
10000
30000 queried
40000
50000
30000
@aabels
queried
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 7: Full learning curves for OpenML. #155 with MLP.
Suppose that BADGE only selects examples from region S.,. = {x w 0}. then as pw
Pw. (z,, 0) 2. we have that for all x in Sw. d. 85 Ia for some 8, [11. This implies that, sampling from a DPP induced by 9= is equivalent to sampling from DPP induced by JN 's. is noted Mussmann and Liang 2018) that uncertainty sampling (i.e. sampling from D(s..) implicitly performs preconditioned stochastic gradient descent on the expected (-1 loss. In addition, it has been shown that DPP sampling over gradients may reduce the variance of the mini-bated stochastic gradient updates (Zhang et al.) 2017b): this suggests that BADGE, when restricted its sampling over low-maggin regions (Sw), improves over uncertainty sampling by collecting examples that together induce lower-variance updates the gradient direction of expected (-1 loss.
ALL LEARNING CURVES
We plot all learning curves (test accuracy as function of the number of labeled example queried) in Figures 6 [2 addition, we zoom into regions the learning curves that discriminates the performance of all
algorithms in Figures 13 to 19
D PAIRWISE COMPARISONS OF ALGORITHMS
In addition Figure 4 in the main text, also provide penalty matrices (Figures 20 and 21 where the results are aggregated by conditioning on a fixed batch size (100, 1000 and 10000) or on a fixed neural network model (MLP, ResNet and VGG). For each penalty matrix, the parenthesized number in its title is the
14

---

Published as conference paper ICLR 2020
0155ML MLP. Batch size: 100
OpenML#156, MLP. Batch size: 1000
OpenML#156, MLP, Batch size: 10000
0.00
0.30
0.80
Accutsoy
0.85
0.85
0.80
0.50
0.75
0.75
0.75
0.70
0.70
0.70
0.85
0.86
10030
20000
30000
40200
30000
10000
20000
30000
40000
5000 10030 10000 20000
20000 30000 30000 40003 #Labels quarled
#Labels quarted
#Labels querted
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 8: Full learning curves for OpenML #156 with MLP.
OpenMLH184, MLP, Batch size: 100
OpenML#184, MLP. Betch 1000
OpenML#184, MUP, Betch size: 10000
0.80
0.80
0.80
Roburacy
0.70
0.50
0.50
0.50
0.40
0.40
0.40
0.50
0.30
5000
10000
15000
20000
2900 9000 7500 1000012500
126001 00001700020000
2500
5000 7500
12500 19000 17600 20000 #Labels querled
10000
#Labels querled
#Labels quelled
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 9: Full learning curves for OpenML #184 with MLP.
15

---

Published as conference paper ICLR 2020
SVHN, Batch
SVHN, MUP.
SVHN, MLP. Betch size: 10000
Rocuracy
50
0.40
40
0.30
30
0.20
0.20
20000
querled
querled
#Labele quoried
SVHN, ResNet, SeeNe, Batch size: 100
SVHN, ResNet, Batch size: 1000
SVHN, ResNet, Betch size: 10000
0.80
0.80
0.50
Accura
0.60
0.80
0.80
0.50
0.50
0.50
0.40
0.0
0.30
0.30
0.10
0.10
HLabels queried
@Labels queried
A1. iLabell queried
SVHN, VGG. Batch size: 100
SVHN, VGG. Betch size: 1000
SVHN VGG, Batch size: 10000
0.80
0.30
0.90
0.80
0.80
0.50
0.50
0.30
0.40
0.40
0.40
0.30
0.0
0.20
8000
10000
16303
20000
25:03
13000
20000
30000
4:0000
5000 10000 16000
20000 90000 35000 40003 #Labell querled
20000
#Labele querled
#Labels querled
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 10: Full learning curves for SVHN with MLP, ResNet and VGG.
MNIST MLP, Batch size: 100
MNIST MLP, Batch size: 1000
MNIST. MLP. Batch size: 10000
0.85
0.90
0.95
Alcuracy
0.80
0.90
0.85
0.85
0.75
0.75
0.70
0.70
0.68
10000
30000
40000
50000
10000
20020
30000
40000
50000
10000
20000
30000
40000
50000
#1 abals querled
#Labels querled
#1. al.abels queried
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 11: Full learning curves for MNIST with MLP.
16

---

Published as conference paper ICLR 2020
CIFAR10, MUP,
100
CIFAR10, Batch
CIFAR10, Betch
0.80
Aocuracy
0.45
0.46
0.46
0.35
0.35
0.50
0.30
0.25
0.29
10020
10000
20000 25000
#Labels querled
@Lablls querled
C/FAR10, ReeNel, Batch size: 100
CIFAR10, ResNet, Batch size: 1000
CIFAR10 ResNel, Batch size: 10000
0.60
Accuraly
0.60
0.50
0.40
0.40
0.40
0.30
0.30
0.0
0.00
0.00
0.10
0.10
0.10
#Labels queried
#Labels queried
iLabels queried
CIFAR1D, VGG. Betch aize: 100
CIFAR10, VGG, Betch size: 1000
CIFAR10, VGG, Batch size: 10000
0.80
0.80
Accuracy
0.70
0.70
0.80
0.60
0.50
0.50
0.40
0.40
0.40
020
0.00
0.10
0.10
0.10
6000
10000
15000
20000
26000
30000
13000
20000
30000
4:0000
6000
10030 16000
20000 90000 35000 40003 #Labell querled
20000
#Labele querled
#Labels querled
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 12: Full learning curves for CIFARIO with MIP, ResNet and VGG.
OpenML#6 MLP Batch size: 100
OpenMLaB MLP. Batch size: 1000
OpenMLa6 MLP Batch size: 10000
0.90
Aocuracy
0.80
0.80
0.60
0.70
0.60
0.50
0.50
0.50
0.50
0.40
2000
4.00
0000
80000
10000
2000
4000
10000
12000
2003
4000
8000
1000
#Labels querled
#Labels querted
#1. al.ablls queried
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 13: Zoomed-in learning curves for OpenMI. #6 with MLP.
17

---

Published as conference paper ICLR 2020
SperMLH155, MLP, Batch size: 100
OpenMLi115,, MLP. Betch size: 1000
OpenMLA155, MLP, Belch size: 10000
0.95
0.80
Apourad
0.90
0.85
0.85
0.80
0.30
0.50
0.75
0.70
0.70
0.8
0.65
0.70
0.65
0.80
1000
2000
3000
4000
5000
8000
7000
1000
2000
3000
4000
5000 5000
7000 5000 9000
10000
20000
30000
40000
50000
WLabels queried
WLabell queried
ALabels queried
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 14: Zoomed-in in learning curves for OpenML #155 with MLP.
01 MLP, Batch 100
OpenMLA115 MLP. Batch size 1000
OpenML#156, MLP, Batch size: 10000
Accuracy
0.85
0.86
0.80
0.80
0.75
0.65
0.85
2500
NLabels queried
#Labels querled
#Labblls queried
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 15: Zoomed-in learning curves for OpenMI. #156 with MIP.
OperML.H884 84, MLP. Batch size: 100
OpenMLH184, MLP. Batch size: 1000
OpenMLH184, MLP, Balch size: 10000
0.80
0.80
Acoursoy
0.70
0.60
0.60
0.0
0.50
0.50
0.60
0.30
0.30
3030
10000
15000
20000
5000
10000
15000
20000
2500 5000 7500 10000 12500 15003 17500 20030 #Labels queried
#Labels queried
#Labels queried
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 16: Zoomed-in learning curves for OpenML #184 with MLP.
18

---

Published as conference paper ICLR 2020
SVHN, Batch
SVHN, MUP,
MUP, Batch 10000
0.80
Rocuracy
0.40
0.30
0.20
0.20
7500 10303
20003
10020
30030 queried
#Lebels queried
querled
SVHN, ResNet, SVHN,ReeNel, Batch size: 100
SVHN, ResNel, Batch size: 1000
SVHN, ResNet, Betch size: 10000
0.80
0.80
0.50
Accural
0.60
0.60
0.80
0.50
0.50
0.50
0.40
0.0
0.30
0.30
0.10
0.10
0.10
#Labels queried
#Labels queried
A1. iLabell queried
SVHN, VGG. Batch size: 100
SVHN, VGG. Betch size: 1000
SVHN VGG, Batch size: 10000
0.80
0.30
0.90
0.80
0.70
0.60
0.50
0.50
0.50
0.40
0.40
0.40
0.30
0.0
0.20
8000
10000
18300
23000
25000
30000
5030
10020
15000
20000
25000
5000
10000 16000
20000 20000 90000 35000 40003 #Labell querled
#Labele querled
#Labels querled
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 17: Zoomed-in learning curves for SVHN with MLP, ResNet and VGG.
MNIST MLP, Batch size: 100
MNIST MLP, Batch size: 1000
MNIST. MLP. Batch size: 10000
0.85
0.90
0.95
Aocuracy
0.80
0.50
0.85
0.85
0.75
0.75
0.70
0.70
5000 7500 100001 2500 100017500000022500
0.68
5000
7500
10000 12500 15000 1753020000
10000
20000
30000
40000
50000
#Labels querled
#Labels querted
#1. al.abels queried
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 18: Zoomed-in learning curves for MNIST with MLP.
19

---

Published as conference paper ICLR 2020
CIFAR10, MUP,
100
CIFAR10,
0.50
Apcuracy
0.45
0.45
0.45
0.40
0.40
0.35
0.35
0.35
0.30
0.30
0.5
0.29
40000
5000
10000 15000
20000 25000
queried
queried
queried
CIFAR10, ResNet, Batch size: 100
CIFAR10, ResNet, Batch sire: 1000
CIFAR10, ResNel, Batch 10000
0.60
Accuracy
0.60
0.45
0.50
0.40
0.40
0.85
0.30
0.30
0.30
0.0
0.20
0.0
0.10
0.10
#Labels querled
#Labels queried
#Labels queried
CIFAR10, VGG. Batch size: 100
CIFAR10, VGG. VGG Batch size: 1000
CIFAR10, VGG Batch size: 10000
0.80
0.80
Aocurscy
0.70
0.50
0.50
0.50
0.40
0.40
0.40
0.20
0.00
0.10
0.10
0.10
10000
20030
30000
40000
5000
1000 (50002000022000 3000015000-00000
5000
10030 15001
20003 26000 50000 35000 40003 iLLabels queried
#Labels queried
#Labell queried
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 19: Zoomed-in learning curves for CIFARIO with MLP, ResNer and VGG.
20

---

Published as conference paper ICLR 2020
Batch size: 100/13)
Batch Size: 1000/111
Batch size: 10000/11)
64002
AJR.
Curnret
Dvrf
Mang Sronpy
BADCE
ALBL
Cerond
Carl
Entrayy
14002
AUB.
Ovr
Drowpyy Fand
A.EL
02
3.0
2.75
14
6:31
1.40
ALDL
31
6-2
14
162
9.0
2.12
AJ8.
0.
3.0
613
0.33
6-3
1.5
1:25
Canau:
2.0
Accuracy
Corf
6:21
RA7
502
00
233
332
100
0
2.72
0.33
5.
5.35
1:3
Marg
30
5/7
02
224
255
4.25
Marg
2.0
20
3.5
1.0
6:31
60
3.2
33
2.5
0.33
0.58
2.25
0.2
1.0
Raed
223
303
2
32
Awy1
2.2
3.05
3.05
Rand
1.27
2.7
2.37
1.25
Figure 20: Pairwise penalty matrices of the algorithms, grouped by different batch sizes. The parenthesized number in the title is the total number of (D, B, A) combinations aggregated, which is also an upper bound on all its entries. Element j corresponds roughly to the number of times algorithm beats algorithm j. Column- wise averages at the bottom show aggregate performance (lower is better). From left to right: batch size = 100, 1000, 10000.
MIP(23] Oed
ResNet(6)
VGG Ord
Drowpy
ALSL Cantad Canf
Map Erbeay
AJD.
Marg Dioapy
BADCE
0:
A:11
2.71
10
3
1D4
3.22
1.6
BADCE
0:14
30
3:24
1.6
A44
AUDL
1.4
AJ8
1.4
Consot
3:7
1.4
5:52
6:5
3.5
5:25
2
0:37
22
3:4
Accuracy
Cayf
232
00
324
0
38
0
1.0
6:52
2022
5:55
20-44
6.2
400
1.2
0.24
22
0.4
0.8
6:11
5.2
6.57
Entrvy
356
650
38
3.
60
6.2
0.4
6:92
3.26
0.75
0.51
0.43
0.6
0.2
00
8:37
3:9
4.22
0:37
6.11
451
3:59
0:12
1.83
23
13
0ST
Figure 21: Pairwise penalty matrices of the algorithms, grouped by different neural network models. The parenthesized number in the title is the total number of (D, B, combinations aggregated, which is also an upper bound on all its entries. Element (i.j) corresponds roughly the number of times algorithm beats algorithm j. Column-wiss wise averages at the bottom show aggregate performance (lower better). From left to right: MLP, ResNet and VGG.
total number of (D, B, A) combinations aggregated; as discussed in Section this is also upper bound on all its entries. can be seen that uncertainty-basee methods (c.g. MARG) perform well only in small batch size regimes (100) when using MLP models; representative sampling based methods (e.g. CORESET) only perform well in large batch size regimes (10000) or when using ResNet or VGG models. In contrast, BADGE's performance is competitive across all batch sizes and neural network models.
21

---

Published as conference paper ICLR 2020
Batch size: 100
Batch size: 1000
Batch aze:: 10000
1.0
1.0
1.0
0.3
0.8
0.8
Cumulativs
0.4
92
02
0.0
0.0
0.3
0.4
0.5
0.5
0.7
0.8
0.9
1.0
1.
12
033
0.4
0.5
0.8
0.7
08
0.9
1.0
1.5
12
0.3
04
0.5
08
0.7
0.5
0.8
1.0
14
12
Normalized error
Normalizd error
Normalzed emror
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 22: CDFs of normalized errors of the algorithms, group by different batch sizes. Higher CDF indicates better performance. From left right: batch size 100, 1000, 10000.
MIP
ResNet
VGG
0.8
0.6
0.6
Cumulatve
0.4
0.4
0.4
02
0.5
Noralized
Normalizdd
Normalized
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 23: CDFs of normalized errors of the algorithms, group by different neural network models. Higher CDF indicates better performance. From left to right: MLP, ResNet and VGG.
CDFs OF NORMALIZED ERRORS OF DIFFERENT ALGORITTMS
In addition to Figure 5 that aggregates over all settings, we show here the CDFs of normalized errors by conditioning on fixed batch sizes (100, 1000 and 10000) in Figure 22 and show the CDFs of normalized enrors by conditioning on fixed neural network models (MLP, ResNet and VGG) in Figure 23
F BATCH UNCERTAINTY AND DIVERSITY
Figure 24 gives comparison of sampling methods with gradient embedding in two settings (OpenML # 6, MLP, batchsize and SVHN, ResNet, batchsize 1000), terms of uncertainty and diversity examples selected within batches. These two properties measured by average l2 norm and determinant of the Gram matrix of gradient embedding, respectively. It can be seen that, k-MEANS++ (BADGE) induces good batch diversity in both settings. CONF generally selects examples with high uncertainty, but in some iterations of OpenML #6, the batch diversity is relatively low, as evidenced by the corresponding log Gram determinant being oc. These areas indicated by gaps in the learning curve for CONF. Situations where there
22

---

Published as conference paper ICLR 2020
OpenML #6, MLP. Batch size: 100
SVHN, ResNet, Batch size: 1000
Log delerminant of batch
Log delerminant of batch
0
250
-5000
-10000
-250
-15000
-500
-750
-25000
-1000
-30000
-120
-35000
4000 BOOD 8000 10000 12000 14000
10000
30000 #Labels queried
20000
50000
#Labels queried
OpenML #6, MLP, Batch size: 100
SVHN, ResNet, Batch size: 1000
Average fa norm in batch
50
Average f2 norm in batch
10
40
30
20-
10
2000
4000
6000
8000 10000 12000 14000
10000
20000
30000 40000
50000
#Labels queried
#Labels queried
(c)
(d)
k-DPP
k-means++
Rand
FF k-center
Conf
Figure 24: A comparison of batch selection algorithms in gradient space. Plots a and b show the log determinants of the Gram matrices of gradient embeddings within batches as learning progresses. Plots and d show the average embedding magnitude (a measurement of predictive uncertainty) in the selected batch. The k-centers sampler finds points that are not as diverse or high high-magnitude also that k- +-MEANS++ tends to actually select samples that are both more diverse and a k-DPP, potential pathology of the k-DPP's degree of stochastisity. Among all algorithms, CONF has the largest average norm of gradient embeddings within batch; however, in OpenML. #6, and the first few interations of SVHN, some batches have a log Gram determinant of oo (shown as gaps the eurve), which shows that CONF sometimes selects batches that are inferior in diversity.
other samplers. Notice
than
many gaps in the CONF plot seem to correspond to situations which CONF performs poorly in terms of accuracy (see Figure 13 for the corresponding learning curve). Both k-DPP and FF-K-CENTER (an algorithm that approximately minimizes k-center objective) select batches that have lower diversity than k-MEANS++ (BADGE).
G COMPARISON OF k-MEANS++ AND DPP IN BATCH SELECTION
In Figures 25
31
give running time and test accuracy comparisons between k-MEANS++ and k-DPP
for selecting examples based on gradient embedding in batch mode active learning. We implement the k-DPP sampling using the MCMC algorithm from (Kang 2013). which has time complexity of O(T (122 + kd))
23

---

Published as conference paper ICLR 2020
Opan16LNG MJP. Datch s20 185
413 OpentLatt VLJ: sze: 100
Openk/Lat ML. Batth s8e: 1002
xtd Operatuat Mr.P. Darzh stee: 1200
3.00
2013 0030 mgo D0001200
2000 4530 o0r1 JoW 1E300001110 9003
2000 1002
(20 00001 HE:0
400 0000 ane 180001000 1000102
K-DPP
k-means++
Figure 25: Learning curves and running times for OpenML #6 with MLP.
Doerbd #155 M. Batchacre 100
axbbrentt #155. Batch 100
wiss, Batch abrw: 1003
EpCrrettll 2l1s, MP Batth abre: 1030
5.355
Thee
50.0
0.77
0.06
1000
4000
1983
2903
3000
0.08
1900
2000
1993
10000
3993
1000
querfs
K-DPP
k-means++
Figure 26: Learning curves and running times for OpenML #155 with MLP.
and space complexity of O(k² kd), where is the number of sampling steps. We set as [5k kn in our experiment. The comparisons for batch size 10000 are not shown here as the implementation of k-DPP sampling out of memory.
It can be seen from the figures that, although k-DPP and k-MEANS++ are based on different sampling criteria, the classification accuracies of their induced active learning algorithm similar. In addition, when large batch sizes are required (e.g. k = 1000), the running times of k-DPP sampling are generally much higher than those of k- 6-MEANS++.
OpenktLA115 M.P. Batchazze 100
A100 MLP. Baten aas: 100
Ope- M.5-5 MLD. Batch slow: 1000
x1 11penttaatt HEP Batch sine: 1930
12000
300
400%
13003
2000
30000
400K
10000
200%
3011
.000
19000
200%
3000
4000
K-DPP
k-means++
Figure 27: Learning curves and rumning times for OpenML #156 with MLP.
24

---

Published as conference paper ICLR 2020
OpenktLATBR MLP, Batchaize: 100
DrDerrtLAA1 MLP: Batch 100
OperM..9194, MLP. SSath stoe: 1000
EppenMLutts,, MEP Baach sice: 1930
12.3 1000 aan 1220 500 1909
2007
62 XED 1300 155 1400
2001 KE3 TEE 1600
0001 000 3R0 7209 1963
k-DPP
k-means++
Figure 28: Learning curves and running times for OpenML #184 with MLP.
2221%, MLP, Eaetch stow:
SWHN, MEF: Batth
SUII M.P. Batch 1000)
531N MLP. Bater 1000
0.28
1983
1993
2:22
2022
T00m 1999
2010
2008
5001
1999
1999
2009
2800
300
19500
1932 753
#Labwiqqueedd
SV/N, RoaNel, Batch 220: 100
SV-HN, Reshel, aze 100
SVNN ReaNei Batch slou: 1000
unt" SVHN Roshist Batch sloo: 1900
023
20B
205
009
13:50
2300
2000
6.05
368
2000
200)
1283
quarted 0000
k-DPP
k-means++
Figure 29: Learning curves and running times for SVHN with MLP and ResNet.
VIIIST MUP, Batch nio:
xnd
MNIST, M.P. Baxth stoo 100
NM4T. M... Balch oze: 1000
u1a' MNST MLP. Botch 922:: 1000
32000
b.20o'
302
009
100
6Libes quetldd
1222
2001
1983
pLoboss queled
2080
K-DPP
k-means++
Figure 30: Learning curves and running times for MNIST with MLP
25

---

Published as conference paper ICLR 2020
CF AlL1O MUP. Bashaae:
CITARIO MUP. Barchh
CFAA110 MEP.. Betcr GIAR210 M.P. Baich 1030
0.45
Telo
0.8
0.5
12200
23:00
6000
1983
2993
33500
12:0
3993
2993
1092
252
70000
2009
#Labeiqqueedd
CIFAR10, Roshet Roshhe. Batch seu. 100
xnd CIFAR10, Realet, Batch sax 100
CIFAR10 Reshir, Sanch sloo: 1002
unr/CFFAR10 ReaNet Batcn slou: 1000
0.00
0.10
TOO
250
2000
800
13:02
38:00
15:55
2000
200)
1283
1000
/Latels
quarted
k-DPP
k-means++
Figure 31: Learning curves and running times for CIFARIO with MLP and ResNet.
26


Reviews:
[{"review_id": "HJgcG9o2FB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new method for active learning, which picks the samples to be labeled by sampling the elements of the dataset with highest gradient norm, under some constraint of diversity. The aforementioned gradient is computed w.r.t. the predicted label (rather than the true label, that is unknown) and diversity is achieved by sampling via the k-MEANS++ algorithm.\nThe paper is well written and while the experiments look thorough, the motivation to support the proposed method seem too weak and unconvincing as does the discussion of the results, which is why I am leaning toward rejection. \nI am willing to amend my vote if the authors provide stronger (not empirical) motivations on why using the gradient norm w.r.t. the predicted label is a better metric than those in the literature, and  More comments below.\n \nDetailed feedback:\n\n1) The paper lacks a proper motivation as to why using the norm of the gradient is a better metric than the many others already present in the literature. In particular, I cannot think of any case where it would be best to use that than the entropy of the network’s output distribution, even though the empirical results seem to suggest otherwise. Specifically, while I believe that in many cases it will be similarly good, if we consider the case when the network is able to rule out most of the classes but is unsure on a small fraction of them, the entropy will better reflect this uncertainty than the norm of the gradient of the predicted class. \n\nGenerally speaking, I believe that the use of the norm of the gradient of the predicted class should be much better motivated, being the core idea of the paper. Stating that it is cheap to compute and empirically performs as well as k-DPP in two experiments is not convincing enough in my opinion.\n2) I wonder how much of the performance of BADGE is due to k-MEANS++ and how much to the choice of using the gradient norm. Please perform an ablation study where you can e.g., replace the gradient norm with the entropy, or replace k-MEANS++ with random sampling, and discuss the results. \n3) How is the embedding “ground set” space determined for k-MEANS++? How are the centroids determined? In which space? It is unclear to me how k-MEANS++ is used in the context of the norm of the gradients. Please improve the explanation in the main text.\n4) Please add a curve for k-DPP to the plots in the main text, rather than having separate plots for it in the appendix. Also, it would be interesting to compare against Derezinski, 2018 as well, if that’s the current state of the art (which is what I infer from your text, but I might be wrong).\n5) The paper builds on the claim that the gradient norm w.r.t. the prediction is a lower bound for the gradient norm induced by any other label, yet Proposition 1 that proves it is in Appendix B. This prove is central to the proposed idea and should be in the main text.\n6) The authors claim that to capture diversity they collect a batch of examples where the gradients span a diverse set of directions, but it’s unclear to me that k-means++ actually accomplishes that. Where is the *direction* of the gradient taken into account in the algorithm?\n7) The “discussion” section is really a “conclusion” one, and indeed a proper in-depth discussion of the experiments is missing. Please expand the comments on the experimental results. \n8) The metric to compute the “pairwise comparison” looks quite convoluted. Is it common in the literature? If so, please add a reference. If not, can you motivate the use of this specific formula?\n9) The random baseline seems to be very competitive. Why is that? Please provide your intuition. Could this be indicative that the baselines have not been tuned properly?\n10) Introduction: the sentence “[deep neural networks] successes have been limited to domains where large amounts of labeled data are available” is incorrect. Indeed, neural networks have been used successfully in many domains where labelled data is scarce, such as the medical images domain for example. Please remove the sentence.\n11) Introduction: please add a sentence to explain what a version-space-based approach is.\n\n12) Is Figure 2 the average over multiple runs or a single run?\n\n13) Notation: please do not use g for the gradient (g^y_x) and for the intermediate activations (g(x; V)).\n\n14) The lower margin seem too wide. Please make sure you respect the formatting style of the conference.\n\n\nMinor:\n- Notation: if you must shorten g^{\\hat{y}}_{x} please do so with \\hat{g}_{x} and equivalently shorten g^{y}_{x} as g_{x}\n- Notation: in the pairwise comparison, please don’t reuse i to denote an algorithm (it is used a few lines before to compute the labeling budget)\n- Please add reference to Appendix A when k-MEANS++ is first referred to in page 2.\n- Page 3,  when Proposition 1 is mentioned add reference to the location where it’s defined.\n\n\nTypos:\n- Page 2: expenive -> expensive\n- Page 5: Learning curves. “Here we show ..” -> Remove “here”\n- Figure 3: pariwise -> pairwise\n- Page 7: Apppendx E\n\n\n----------------------\nUpdated review:\n\nI thank the authors for for taking the time to address all my comments, and clarifying some of the misunderstandings I had. I am happy to revise my score accordingly.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJeqfZW0YB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Batch active:\nThis paper proposes a novel approach to active learning in batches. Assuming a neural-network architecture, they compute the gradients of each unlabeled example using the last layer of the network (and assuming the label given by the network) and then choose an appropriately diverse subset of these using the initialization step of kmeans++. The authors provide intuitive motivation for this procedure, along with extensive empirical comparisons. \n\nOverall I thought the paper was well written and proposed a new practical method for active learning. There were a few concerns and places where the paper could be clearer.\n\n1. The authors keep emphasizing a connection to k-dpp for the sampling procedure emphasizing diversity. They provide a compelling argument for the kmeans++ but in Figure 1 it is unclear why k-DPP is the right comparison point. For example, you could imagine building a set cover of the data using balls at various radii and then choosing their centers.\n2. The paper emphasizes choosing samples in a way to eliminate pathological batches. Considering this is a main motivation, none of the figures really demonstrate that this is what BADGE is doing compared to the uncertainty sampling-based methods tested against. Perhaps the determinant of the gram matrix of the batch could be reported for both algorithms?  \n3. While reading the paper, the set of architectures used was hard to find. Maybe I just missed it, but it would be useful to have this information. In particular, in Figure 3, there are absolute counts, but I wasn’t sure how many (D,B,A,L) combinations there were. \n4. Finally, recent work in Computer Vision has shown that uncertainty sampling with ensemble-based methods in active learning tends to work well. I understand that it is hard to compare to the myriads of active learning algorithms out there, but they deserve a mention. See [1] below.\n\nOverall I think this paper is a good empirical effort that I recommend for acceptance.\n\n[1] Beluch, William H., Tim Genewein, Andreas Nürnberger, and Jan M. Köhler. \"The power of ensembles for active learning in image classification.\" In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9368-9377. 2018.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1loQbi2YB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces an algorithm for active learning in deep neural networks named  BADGE. It consists basically of two steps: (1) computing how uncertain the model is about the examples in the dataset (by looking at the gradients of the loss with respect to the parameters of the last layer of the network), and (2) sampling the examples that would maximize the diversity through k-means++. The empirical results show that BADGE is able to get the best of two worlds (sampling to maximize diversity/to minimize uncertainty), consistently outperforming other approaches in a wide-rage of classification tasks.\n\nThis is a very well-written paper that seems to make a meaningful contribution to the field with a very good justification for the proposed method and with convincing empirical results. Active learning is not my main area of expertise so I can’t judge how novel the proposed idea is, but from an outsider’s perspective, this is a great paper. It is clear, it does a good job explaining the problem, the different approaches people have used to tackle the problem, and how it fits in this literature. Below I have a couple of (minor) comments and questions:\n\n1. Out of curiosity, it seems that it is standard in the literature, but isn’t the assumption that one can go over the whole dataset, U, at each iteration of the active learning algorithm, limiting? It is not that cheap to go over large datasets (e.g., ImageNet).\n2. MARG seems to often outperform the other baselines but it doesn’t have a reference attached to it (bullet points on page 5). Is this a case that a “trivial” baseline outperforms existing methods or is there a reference missing?\n3. In some figures, such as Figure 2, there are shaded regions in the plots. It is not clear what they are though. Are they representing confidence intervals? Standard deviation? They are quite tight for a sample size of 5.\n4. In the section “Pairwise comparisons” it reads “Algorithm i is said to beat algorithm j in this setting if z > 1.96, and similarly … z < -1.96”.  It seems to me that the number 1.96 comes from the z-score table for 95% confidence. However, if that’s the case, it seems z should be much bigger in this context. With a sample-size of 5 (if this is still the sample size, maybe I missed something here), the normal assumptions do not hold and the t-score should’ve been used here. What did I miss?\n\nIn terms of presentation,  Proposition 1 seems to be a very interesting result. I would move it to the main paper instead of leaving it in the Appendix. I also think the paper would read better if it didn’t use references as nouns (e.g., “algorithm of (Derezinski, 2018)”). Finally, there’s also a typo on page 7 (Apppendx).\n\n\n--- \n\n>>> Update after rebuttal: I stand by my score after the rebuttal.  This is a really strong paper in my opinion. I appreciate the fact that the authors took my feedback into consideration.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a simple method of active learning for classification using deep nets. The method is motivated by choosing examples based on an embedding computed that represents the last layer gradients, which is shown to have a connection to a lower bound of model change if labeled. The algorithm is simple and easy to implement. The method is justified by convincing experiments. 

The reviewers agree that the rebuttal and revisions cleared up any misunderstandings.

This is a solid empirical work on an active learning technique that seems to have a lot of promise. Accept. 

Decision: Accept (Talk)