DIVERSE, UNCERTAIN GRADIENT LOWER BOUNDS
Year: 2019

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.

text: 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.

heading: 1 INTRODUCTION
text: In recent years, deep neural networks have produced state-of-the-art results on a variety of important supervised learning tasks. However, many of these successes have been in domains where large amounts of data are available. A promising approach for minimizing labeling effort is active learning, a supervised learning protocol where labels can be requested by the algorithm in a sequential feedback-driven fashion. Active learning algorithms aim to identify and label only maximally informative samples, so that a highperforming classifier can be trained with minimal labeling effort. As such, a robust active learning algorithm for deep neural networks may considerably expand the domains where these models are applicable.
How should a practical, general-purpose, label-efficient active learning algorithm for deep neural networks be designed? Theory for active learning suggests a version-space-based approach (Balcan et al., 2006), which explicitly or implicitly maintains a set of plausible models, and queries examples for which two models that make different predictions. But when using highly-expressive models, these algorithms degenerate to querying every example. Further, the computational overhead of training deep neural networks preclude algorithms that update the model to best fit the data after each label query, as is often done (exactly or approximately) for linear methods (Beygelzimer et al., 2010; Cesa-Bianchi et al., 2009). Unfortunately, the theory provides little guidance for these models.
One option is to use the network’s uncertainty to inform a query strategy, for example by labeling samples for which the model is least confident. However, in a batch setting this creates a pathological scenario where data in the batch are nearly identical, a clear inefficiency. Remedying this issue, we could select samples to maximize batch diversity, but this might choose points that provide little useful new information to 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 a ResNet, for 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. Even what in practice constitutes a “big” or “small” batch size is largely a function of the statistical properties of the data in question. These
weaknesses pose a major problem for real, practical batch active learning situations, where data are unfamiliar and potentially unstructured. There is no way to know which active learning algorithm is best to use.
Further, in a real active learning scenario, every change of hyperparameters typically causes the algorithm to label examples not chosen under other hyperparameters, provoking substantial labeling inefficiency. That is, hyperparameter sweeps in active learning can be label expensive. Because of this, 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 an approach which creates diverse batches of examples about which the current model is uncertain. We measure uncertainty as the gradient magnitude with respect to 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, we build up the batch of query points based on these hallucinated gradients using the k-MEANS++ initialization (Arthur and Vassilvitskii, 2007), which simultaneously captures both the magnitude of a 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 to 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 4. We defer discussion of related work to Section 5.

heading: 2 NOTATION AND SETTING
text: Define [K] := {1, 2, . . . ,K}. Denote byX the instance space, andY the label space. In this work we consider multiclass classification, so that Y = [K]. Denote by D the distribution from which examples are drawn, DX the unlabeled data distribution, andDY|X 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 x ∈ U . We use ED to denote expectation under the data distribution D. Given a classifier h : X → Y , which maps examples to labels, and a labeled example (x, y), we denote the 0/1 error of h on (x, y) as `01(h(x), y) = I(h(x) 6= y). The performance of a classifier h is measured by its expected 0/1 error, i.e. ED[`01(h(x), y)] = Pr(x,y)∼D(h(x) 6= y). The goal of pool-based active learning is to find a classifier with a small expected 0/1 error, using as few label queries as possible. Given a set S of labeled examples (x, y), where each x ∈ S is picked from U , followed by a label query, we use ES as the sample averages over S.
In this paper, we consider classifiers h parameterized by underlying neural networks f of fixed architecture, with the weights in the network denoted by θ. We abbreviate the classifier with parameters θ as hθ since the architectures are fixed in any given context, and our classifiers take the form hθ(x) = argmaxy∈[K] f(x; θ)y , where f(x; θ) ∈ RK is a vector of scores assigned to candidate labels, given the example x and parameters θ. We optimize the parameters by minimizing the cross-entropy loss ES [`CE(f(x; θ), y)] over the labeled examples, where `CE(p, y) = ∑K i=1 I(y = i) ln 1/pi.

heading: 3 ALGORITHM
text: BADGE, described in Algorithm 1, starts by drawing an initial set of M examples uniformly at random from U and asking for their labels. It then proceeds iteratively, performing two main computations at each step t: a gradient embedding computation and a sampling step. Specifically, at each step t, for every x in the pool U , we compute the label ŷ(x) preferred by the current model, and the gradient gx of the loss on (x, ŷ(x)) with respect to the parameters of the last layer of the network. Given these gradient embedding vectors {gx : x ∈ U}, BADGE selects a set of points by sampling via the k-MEANS++ initialization scheme (Arthur and Vassilvitskii, 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.
Algorithm 1 BADGE: Batch Active learning by Diverse Gradient Embeddings Require: Neural network f(x; θ), unlabeled pool of examples U , initial number of examples M , number of
iterations T , number of examples in a batch B. 1: Labeled dataset S ←M examples drawn uniformly at random from U together with queried labels. 2: Train an initial model θ1 on S by minimizing ES [`(f(x; θ), y)]. 3: for t = 1, 2, . . . , T : do 4: For all examples x in U \ S:
1. Compute its hypothetical label ŷ(x) = hθt(x). 2. Compute gradient embedding gx = ∂∂θout `(f(x; θ), ŷ(x))|θ=θt , where θout refers to parameters
of the final (output) layer. 5: Compute St, a random subset of U \S, using the k-MEANS++ seeding algorithm, on {gx : x ∈ U \ S}, and query for their labels. 6: S ← S ∪ St. 7: Train a model θt+1 on S by minimizing ES [`CE(f(x; θ), y)]. 8: end for 9: return Final model θT+1.
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 parameter, and hence a large update to the model. A difficulty with this reasoning is 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 is the true label. We show in Proposition 1 that, assuming a common structure satisfied by most natural loss functions, 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 label, then the example’s gradient embedding will have a small norm (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.
Consider a neural network f where the last nonlinearity is a softmax, i.e. σ(o)i = e oi/ ∑K j=1 e
oj . Specifically, f is parametrized by θ = (W,V ), where θout = W = (W>1 , . . . ,W > K ) > ∈ RK×d are the weights of the last layer, and V consists of weights of all earlier layers. This means that f(x; θ) = σ(W · z(x;V )), where z is the nonlinear function that maps an input x to the output of the network’s penultimate layer. We define gyx = ∂ ∂W `CE(f(x; θ), y) for a label y and gx = g ŷ x as the gradient embedding in our algorithm, where ŷ = argmaxi∈[K] pi. Fixing an unlabeled sample x, we define pi = f(x; θ)i.
Proposition 1. For all y ∈ {1, . . . ,K}, denote by gyx = ∂∂W `CE(f(x; θ), y). Then
‖gyx‖2 = ( K∑ i=1 p2i + 1− 2py ) ‖z(x;V )‖2.
Consequently, ŷ = argminy∈[K] ‖gyx‖.
Proof. Observe that by Equation (1),
‖gyx‖2 = K∑ i=1 ( pi − I(y = i) )2‖z(x;V )‖2 = ( K∑ i=1 p2i + 1− 2py ) ‖z(x;V )‖2.
The second part follows from the fact that ŷ = argmaxy∈[K] py .
The sampling step. We want the newly-acquired labeled dataset to induce large and diverse changes to the model. To this end, we 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 a single single label could alleviate our uncertainty on all remaining samples.
A natural way of making this selection without introducing additional hyperparameters is to sample from a k-DPP (Kulesza and Taskar, 2011). That is, to select a batch of k points with a probability proportional to the determinant of their Gram matrix. Recently, Dereziński 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 error than learning from any 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 chooses points that are diverse because linear dependence makes the Gram determinant equal to 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 a significant computational hurdle. The state-of-the-art algorithm of (Dereziński, 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 a good initialization for k-means clustering. k-MEANS++ seeding selects centroids by sampling points in proportion to their squared distances from the nearest centroid that has already been chosen. For completeness, we give a formal description of the k-MEANS++ seeding algorithm in Appendix A.
This simple sampler tends to produce diverse batches similar to a k-DPP. As shown in Figure 1, switching between the two samplers does not affect the active learner’s statistical performance while greatly improving the computational performance. A thorough comparison on the running times and test accuracies of k-MEANS++ and k-DPP based gradient embedding sampling can be found in Appendix G.
Figure 2 describes the batch diversity and average gradient magnitude per selected batch for a 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 with batches) and high magnitude. Other samplers, like furthest-first traversal for k-Center clustering (FF-k-CENTER), do not seem to have this property. The FF-k-CENTER algorithm is the sampling choice of the CORESET approach to active learning, which we describe in the proceeding section (Sener and Savarese, 2018). Appendix F discusses diversity with respect to uncertainty-based approaches.
Example: multiclass classification with softmax activation. Recall that the neural network f has the form f(x; θ) = σ(W · z(x;V )), where σ(o)i = eoi/∑Kj=1 eoj , and the loss function is the cross entropy, `CE(p, y) = ∑K i=1 I(y = i) ln 1/pi. By substitution,
`CE(f(x; θ), y) = ln ( K∑ j=1 eWj ·z(x;V ) ) −Wy · z(x;V ).
Given this, the i-th block of gx is equal to
(gx)i = ∂ ∂Wi `CE ( f(x; θ), ŷ ) = ( pi − I(ŷ = i) ) z(x;V ). (1)
Based on this expression, we can make the following observations:
1. Each block of gx is a scaling of z(x;V ), the output of the network’s penultimate layer. In this respect, gx captures the representation information of z(x;V ), the space in which diversity-based algorithms operate (Sener and Savarese, 2018).
2. Proposition 1 shows that the norm of gx is a lower bound on the norm of the loss gradient induced by the example with true label y with respect to the last-layer weights, i.e. ‖gx‖ ≤ ‖gyx‖. This suggests that the norm of gx conservatively estimates the example’s influence on the current model.
3. If the current model θ is highly confident about x, i.e. vector p is skewed towards a standard basis vector ej , then ŷ = j, and vector (pi − I(ŷ = i))Ki=1 has a small length. Therefore, gx has a small length as well. Consequently, such high-confidence examples tend to have gradient embeddings of small magnitude, which are unlikely to be repeatedly selected by k-MEANS++ at iteration t.
For the special case of binary logistic regression (K = 2 and z(x;V ) = x), we provide further justifications on why BADGE yields better updates than vanilla uncertainty sampling in Appendix B.

heading: 4 EXPERIMENTS
text: We evaluate the performance of BADGE against several algorithms in 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 a comprehensive comparison among all algorithms, we evaluate them in a batch mode active learning setup, with M = 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 algorithm performs representative sampling; the next three algorithms are uncertainty based; the last algorithm is a hybrid of representativeness and uncertainty based approaches.
1. CORESET: active learning with coreset selection (Sener and Savarese, 2018), where the embedding of each example is computed as the network’s output of the penultimate layer, and the samples at each round are selected using a greedy furthest-first traversal conditioned on all labeled examples.
2. CONF (Confidence Sampling (Wang and Shang, 2014)): uncertainty-based active learning algorithm that selects B examples with the smallest predicted class probability, maxKi=1 f(x; θ)i.
3. MARG (Margin Sampling (Roth and Small, 2006)):uncertainty-based active learning algorithm that selects the bottom B examples sorted according to the example’s multiclass margin, defined as f(x; θ)ŷ − f(x; θ)y′ , where ŷ and y′ are the indices of the largest and second largest entries of f(x; θ).
4. ENTROPY (Wang and Shang, 2014): uncertainty-based active learning algorithm that selects the top B examples according to the entropy of the example’s predictive class probability distribution, defined as H((f(x; θ)y)Ky=1), where H(p) = ∑K i=1 pi ln 1/pi.
5. ALBL (Active Learning by Learning (Hsu and Lin, 2015)): A bandit-style meta-active learning algorithm that selects between CORESET and CONF at every round.
6. RAND: the naive baseline of randomly selecting k examples to query at each round.
We consider three neural architectures: a two-layer Perceptron with ReLU activations (MLP), an 18-layer convolutional ResNet (He et al., 2016), and an 11-layer VGG network (Simonyan and Zisserman, 2014). We evaluate our algorithms using three image datasets, SVHN (Netzer et al., 2011), CIFAR10 (Krizhevsky, 2009) and MNIST (LeCun et al., 1998), 1 and four non-image datasets from the OpenML repository (#6, #155, #156, and #184). 2 We study each situation with 7 active learning algorithms, including BADGE, making for 231 total experiments.
For the image datasets, the embedding layer in the MLP is 256. For the openML datasets, the embedding dimensionality of the MLP is 1024, as more capacity is helpful to fit the training data. We fit models using the cross entropy loss and the Adam variant of SGD until the training accuracy of the algorithm exceeds 99%. We use a learning rate of 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 for training.
Baselines use implementations from the libact library (Yang et al., 2017). All models are trained in PyTorch (Paszke et al., 2017).
1Because MNIST is a dataset that is extremely easy to classify, we only use MLPs, rather than convolutional networks, to better study the differences between active learning algorithms.
2The OpenML datasets are from openml.org, and are selected on two criteria: first, they have at least 10000 samples; second, neural networks have a significantly smaller test error rate when compared to linear models.
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 is better to do diversity sampling, and later in training, it is 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. BADGE does about as well as representative sampling when that strategy does best, and as well as uncertainty sampling once those methods start outpacing CORESET. This suggests that BADGE is a good choice regardless of labeling budget.
Separately, we notice that diversity sampling only seems to work well when either the model has good priors (inductive biases) built in, or when the data are easy to learn. Otherwise, penultimate layer representations are not meaningful, and diverse sampling can be deleterious. For this reason, CORESET often performs worse than random on sufficiently complex data when not using a convolutional network (Figure 3b). That is, the diversidy induced by unconditional random sampling can yield a batch that better represents the data. Even when batch size is large and the model has helpful inductive biases, the uncertainty information in BADGE can give it an advantage over pure diversity approaches (Figure 3c). Comprehensive plots of this kind, spanning architecture, dataset, and batch size are in Appendix C.
Pairwise comparisons. We next give a comprehensive comparison over all pairs of algorithms over all datasets (D), batch sizes (B), model architectures (A), and label budgets (L). From the learning curves, it can be observed that when the label budgets are large enough, the algorithms eventually reach similar performance, hence the comparison between algorithms in the large sample limit is uninteresting. For this reason, for each combination of (D,B,A),
we select a set of labeling budgets L where learning is still progressing. As there are 3 choices of batch sizes, and in total 11 choices of (dataset, architecture) combinations, the total number of (D,B,A) combinations is 3× 11 = 33. Specifically, we compute n0, the smallest number of labels where RAND’s accuracy reaches 99% of its final accuracy, and choose label budget L from { M + 2i−1B : i ∈ [blog((n0 −M)/B)c] } . The calculation of scores in the penalty matrix P follows the protocol: for each (D,B,A,L) combination and algorithms i, j, we have 5 test errors (one for each repeated run) { e1i , . . . , e 5 i } and { e1j , . . . , e 5 j } for each algorithm respectively. We compute the t score as t = √ 5µ̂/σ̂, where
µ̂ = 1
5 5∑ l=1 (eli − elj), σ̂ = √√√√1 4 5∑ l=1 (eli − elj − µ̂)2.
We use the two-sided t-test to compare pairs of algorithms: Algorithm i is said to beat algorithm j in this setting if t > 2.776 (the critical point of p-value being 0.05), and similarly algorithm j beats algorithm i if t < −2.776. For each (D,B,A) combination, suppose there are nD,B,A different values of L, then for each L, if algorithm i beats algorithm j, we accumulate a penalty of 1/nD,B,A to Pi,j ; otherwise, if algorithm j beats algorithm i, we accumulate a penalty of 1/nD,B,A to Pj,i. The choice of the penalty value 1/nD,B,A is to ensure that every (D,B,A) combination gets equal share in the aggregated matrix. Therefore, the largest entry of P is at most 33, the total number of (D,B,A) combinations. Intuitively, each row i indicates the number of settings where algorithm i beats other algorithms; and each column j indicates the number of settings where algorithm j gets beaten by other algorithms.
The penalty matrix in Figure 4 summarizes all experiments, showing that BADGE generally outperforms baselines. Matrices grouped by batch size and architecture are in Appendix D, each suggesting that BADGE outperforms other algorithms.
Cumulative distribution functions of normalized errors. For each (D,B,A,L) combination, we have five average errors for each algorithm i: ēi = 15 ∑5 l=1 e l i. To ensure that the errors of these algorithms are on the same scale in all settings, we compute the normalized error of every algorithm i, defined as nei = ēi/ēr, where r is the index of the RAND algorithm. By definition, the normalized errors of the RAND algorithm are identically 1 in all settings. Same as in the generation of penalty matrices, for each (D,B,A) combination, we only consider a subset of L values from the set { M + 2i−1B : i ∈ [blog((n0 −M)/B)c] } ; in addition, we assign a weight proportional to 1/nD,B,A to each (D,B,A,L) combination, where there are nD,B,A different L values for this combination of (D,B,A). We then plot the cumulative distribution functions (CDFs) of the normalized errors of all algorithms: for a value of x, the y 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 show the generated CDFs in Figures 5, 22 and 23. We can see from Figure 5 that, BADGE has the best overall performance. In addition, from Figures 22 and 23 in Appendix E, we can conclude that, when the batch sizes are small (100 or 1000), or when the MLP model is used, both BADGE and MARG outperform the rest. 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.

heading: 5 RELATED WORK
text: Active learning is a well-studied problem (Settles, 2010; Dasgupta, 2011; Hanneke, 2014). There are two major strategies for active learning algorithms: representative sampling and uncertainty sampling.
In representative sampling, the algorithm selects a batch of examples that are representative of the unlabeled set to ask for labels. The high-level idea is that the set of examples chosen, once labeled, can act as a surrogate for the full dataset. Performing loss minimization on the surrogate suffices to ensure a low error with respect to the full dataset. In the context of deep learning, (Sener and Savarese, 2018; Geifman and El-Yaniv, 2017) select representative examples based on core-set construction, a fundamental problem in computational geometry. Inspired by generative adversarial learning, (Gissin and Shalev-Shwartz, 2019) selects samples that are maximally indistinguishable from the pool of unlabeled examples.
On the other hand, uncertainty sampling is based on a different principle: it tries to select new samples that maximally reduce the uncertainty the algorithm has on the target classifier. In the context of linear classification, (Tong and Koller, 2001; Schohn and Cohn; Tur 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 consistency (Hanneke, 2014; Balcan et al., 2006). Such methods have also been recently generalized to deep learning. For instance, (Gal et al., 2017) uses Dropout as an approximation of the posterior of the model parameters, and develop information-based uncertainty reduction criteria; inspired by recent advances on adversarial examples generation, (Ducoffe and Precioso, 2018) uses the distance between an 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., 2018).
There are several existing approaches that support a hybrid of representative sampling and uncertainty sampling. For example, (Baram 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., 2010) develops label query criteria that balances between the representativeness and informativeness of examples. Another method for this is Active Learning by Learning (Hsu and Lin, 2015), which can select whether to exercise a diversity based algorithm or an uncertainty based algorithm at each round of training as a sequential decision process.
There is also a large body of literature on batch mode active learning, where the learner is asked to select a batch of samples within each round (Guo and Schuurmans, 2008; Wang and Ye, 2015; Chen and Krause, 2013; Wei et al., 2015). In these works, batch selection is often formulated as an optimization problem, with objectives based on (upper bounds of) average log-likelihood, average squared loss, etc.
A different query criterion based on expected gradient length (EGL) has been proposed in the literature (Settles et al., 2008). In recent work, (Huang et al., 2016) show that the EGL criterion is related to the T -optimality criterion in experimental design; in addition, they show that the samples selected by EGL are very different from those by entropy-based uncertainty criterion. (Zhang et al., 2017a) uses the EGL criterion in active sentence and document classification with CNNs. These works differ most substatially from BADGE in that they do not take into account the diversity of the examples queried within each batch.
There are many theoretical works that focus on the related problem of adaptive subsampling for fully-labeled datasets in regression settings (Han et al., 2016; Wang et al., 2018; Ting and Brochu, 2018). Empirical studies of batch stochastic gradient descent also employ adaptive sampling to “emphasize” hard or representative examples (Zhang et al., 2017b; Chang et 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 emphasizes samples that induce large updates to the model.
As mentioned earlier, our sampling criterion has resemblance to sampling from k-determinantal point processes (k-DPPs) (Kulesza and Taskar, 2011). Note that in multiclass classification settings, our gradient-
based embedding of an example can be viewed as the outer product of the original embedding in the penultimate layer and a probability score vector that encodes the uncertainty information on this example (see Section 3). In 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 a natural probabilistic tool for sampling that trades off between quality and diversity (See Kulesza et al., 2012, Section 3.1).

heading: 6 DISCUSSION
text: 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 fundamental 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 (a lower bound on 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 a batch, and does so without requiring any hyperparameters.
3. The randomization associated with the k-MEANS++ initialization sampler implies that even for adversarially constructed datasets it eventually converges to a good solution.
The combination of these properties appears to generate the robustness that we observe empirically.

heading: B BADGE FOR BINARY LOGISTIC REGRESSION
text: We consider instantiating BADGE for binary logistic regression, where Y = {−1,+1}. Given a linear classifier w, we define the predictive probability of w on x as pw(y|x, θ) = σ(yw · x), where σ(z) = 11+e−z is the sigmoid funciton.
Recall that ŷ(x) is the hallucinated label:
ŷ(x) = { +1 pw(+1|x, θ) > 1/2 −1 pw(+1|x, θ) ≤ 1/2.
The logistic loss of classifier w on example (x, y) is defined as:
`(w, (x, y)) = ln(1 + exp(−ŷ(x)w · x)).
Now, given model w and example x, we define ĝx = ∂∂w `(w, (x, ŷ)) = (1− pw(ŷ|x, θ)) · (−ŷ ·x) as the loss gradient induced by the example with hallucinated label, and g̃x = ∂∂w `(w, (x, y)) = (1−pw(y|x, θ))·(−y·x) as the loss gradient induced by the example with true label.
2000 4000 6000 8000 10000 12000 14000 16000
#Labels queried
0.4
0.5
0.6
0.7
0.8
0.9
A cc
ur ac
y OpenML#6, MLP, Batch size: 100
2000 4000 6000 8000 10000 12000 14000 16000
#Labels queried
0.4
0.5
0.6
0.7
0.8
0.9
A cc
ur ac
y
OpenML#6, MLP, Batch size: 1000
2000 4000 6000 8000 10000
#Labels queried
0.4
0.5
0.6
0.7
0.8
0.9
A cc
ur ac
y
OpenML#6, MLP, Batch size: 10000
ALBL Conf Coreset BADGE Entropy Marg Rand
Figure 6: Full learning curves for OpenML #6 with MLP.
10000 20000 30000 40000 50000
#Labels queried
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
A cc
ur ac
y
OpenML#155, MLP, Batch size: 100
10000 20000 30000 40000 50000
#Labels queried
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
A cc
ur ac
y OpenML#155, MLP, Batch size: 1000
10000 20000 30000 40000 50000
#Labels queried
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
A cc
ur ac
y
OpenML#155, MLP, Batch size: 10000
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 Sw = {x : w · x = 0}, then as pw(+1|x, θ) = pw(−1|x, θ) = 12 , we have that for all x in Sw, ĝx = sx ·gx for some sx ∈ {±1}. This implies that, sampling from a DPP induced by ĝx’s is equivalent to sampling from a DPP induced by gx’s. It is noted in Mussmann and Liang (2018) that uncertainty sampling (i.e. sampling from D|Sw ) implicitly performs preconditioned stochastic gradient descent on the expected 0-1 loss. In addition, it has been shown that DPP sampling over gradients may reduce the variance of the updates (Zhang et al., 2017b); this suggests that BADGE, when restricted sampling over low-margin regions (Sw), improves over uncertainty sampling by collecting examples that together induce lower-variance updates on the gradient direction of expected 0-1 loss.

heading: C ALL LEARNING CURVES
text: We plot all learning curves (test accuracy as a function of the number of labeled example queried) in Figures 6 to 12. In addition, we zoom into regions of the learning curves that discriminates the performance of all algorithms in Figures 13 to 19.

heading: D PAIRWISE COMPARISONS OF ALGORITHMS
text: In addition to Figure 4 in the main text, we 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 total number of (D,B,A) combinations aggregated; as discussed in Section 4, this is also an upper bound on all its entries. It can be seen uncertainty-based methods (e.g. MARG) perform well only in small batch size regimes (100) or when using MLP models; representative sampling based methods (e.g. CORESET) only perform well in large batch size regimes (1000) or when using ResNet models. In contrast, BADGE’s performance is competitive across all batch sizes and neural network models.
OpenML#156, MLP, Batch size: 100
OpenML#156, MLP, Batch size: 1000
OpenML#156, MLP, Batch size: 10000
OpenML#184, MLP, Batch size: 100
OpenML#184, MLP, Batch size: 1000
OpenML#184, MLP, Batch size: 10000
5000 10000 15000 20000 25000 30000
#Labels queried
0.2
0.3
0.4
0.5
0.6
0.7
0.8
A cc
ur ac
y
SVHN, MLP, Batch size: 100
10000 20000 30000 40000 50000
#Labels queried
0.2
0.3
0.4
0.5
0.6
0.7
0.8
A cc
ur ac
y
SVHN, MLP, Batch size: 1000
10000 20000 30000 40000 50000
#Labels queried
0.2
0.3
0.4
0.5
0.6
0.7
0.8
A cc
ur ac
y
SVHN, MLP, Batch size: 10000
10000 20000 30000 40000 50000
#Labels queried
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
A cc
ur ac
y
SVHN, ResNet, Batch size: 100
10000 20000 30000 40000 50000 #Labels queried 0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
A cc
ur ac
y
SVHN, ResNet, Batch size: 1000
10000 20000 30000 40000 50000 #Labels queried 0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
A cc
ur ac
y
SVHN, ResNet, Batch size: 10000
SVHN, VGG, Batch size: 100
SVHN, VGG, Batch size: 1000
SVHN, VGG, Batch size: 10000
MNIST, MLP, Batch size: 100
MNIST, MLP, Batch size: 1000
MNIST, MLP, Batch size: 10000
10000 20000 30000 40000 50000
#Labels queried
0.25
0.30
0.35
0.40
0.45
0.50
A cc
ur ac
y
CIFAR10, MLP, Batch size: 100
10000 20000 30000 40000
#Labels queried
0.25
0.30
0.35
0.40
0.45
0.50
A cc
ur ac
y
CIFAR10, MLP, Batch size: 1000
5000 10000 15000 20000 25000 30000 35000 40000
#Labels queried
0.25
0.30
0.35
0.40
0.45
0.50
A cc
ur ac
y
CIFAR10, MLP, Batch size: 10000
10000 20000 30000 40000
#Labels queried
0.1
0.2
0.3
0.4
0.5
A cc
ur ac
y
CIFAR10, ResNet, Batch size: 100
10000 20000 30000 40000
#Labels queried
0.1
0.2
0.3
0.4
0.5
0.6
A cc
ur ac
y
CIFAR10, ResNet, Batch size: 1000
5000 10000 15000 20000 25000 30000 35000 40000
#Labels queried
0.1
0.2
0.3
0.4
0.5
0.6
A cc
ur ac
y
CIFAR10, ResNet, Batch size: 10000
CIFAR10, VGG, Batch size: 100
CIFAR10, VGG, Batch size: 1000
CIFAR10, VGG, Batch size: 10000
OpenML#6, MLP, Batch size: 100
OpenML#6, MLP, Batch size: 1000
OpenML#6, MLP, Batch size: 10000
OpenML#155, MLP, Batch size: 100
OpenML#155, MLP, Batch size: 1000
OpenML#155, MLP, Batch size: 10000
OpenML#156, MLP, Batch size: 100
OpenML#156, MLP, Batch size: 1000
OpenML#156, MLP, Batch size: 10000
OpenML#184, MLP, Batch size: 100
OpenML#184, MLP, Batch size: 1000
OpenML#184, MLP, Batch size: 10000
2500 5000 7500 10000 12500 15000 17500 20000
#Labels queried
0.2
0.3
0.4
0.5
0.6
0.7
0.8
A cc
ur ac
y
SVHN, MLP, Batch size: 100
5000 10000 15000 20000 25000
#Labels queried
0.2
0.3
0.4
0.5
0.6
0.7
0.8
A cc
ur ac
y
SVHN, MLP, Batch size: 1000
10000 20000 30000 40000 50000
#Labels queried
0.2
0.3
0.4
0.5
0.6
0.7
0.8
A cc
ur ac
y
SVHN, MLP, Batch size: 10000
5000 10000 15000 20000 25000 30000 35000
#Labels queried
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
A cc
ur ac
y
SVHN, ResNet, Batch size: 100
5000 10000 15000 20000 25000 30000 35000 40000 #Labels queried 0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
A cc
ur ac
y
SVHN, ResNet, Batch size: 1000
10000 20000 30000 40000 50000 #Labels queried 0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
A cc
ur ac
y
SVHN, ResNet, Batch size: 10000
SVHN, VGG, Batch size: 100
SVHN, VGG, Batch size: 1000
SVHN, VGG, Batch size: 10000
MNIST, MLP, Batch size: 100
MNIST, MLP, Batch size: 1000
MNIST, MLP, Batch size: 10000
10000 20000 30000 40000
#Labels queried
0.25
0.30
0.35
0.40
0.45
0.50
A cc
ur ac
y
CIFAR10, MLP, Batch size: 100
5000 10000 15000 20000 25000 30000 35000
#Labels queried
0.25
0.30
0.35
0.40
0.45
0.50
A cc
ur ac
y
CIFAR10, MLP, Batch size: 1000
5000 10000 15000 20000 25000 30000 35000 40000
#Labels queried
0.25
0.30
0.35
0.40
0.45
0.50
A cc
ur ac
y
CIFAR10, MLP, Batch size: 10000
10000 20000 30000 40000
#Labels queried
0.20
0.25
0.30
0.35
0.40
0.45
0.50
0.55
A cc
ur ac
y
CIFAR10, ResNet, Batch size: 100
10000 20000 30000 40000
#Labels queried
0.1
0.2
0.3
0.4
0.5
0.6
A cc
ur ac
y
CIFAR10, ResNet, Batch size: 1000
5000 10000 15000 20000 25000 30000 35000 40000
#Labels queried
0.1
0.2
0.3
0.4
0.5
0.6
A cc
ur ac
y
CIFAR10, ResNet, Batch size: 10000
CIFAR10, VGG, Batch size: 100
CIFAR10, VGG, Batch size: 1000
CIFAR10, VGG, Batch size: 10000
Batch size: 100
Batch size: 1000
Batch size: 10000

heading: E CDFS OF NORMALIZED ERRORS OF DIFFERENT ALGORITHMS
text: 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 errors by conditioning on fixed neural network models (MLP, ResNet and VGG) in Figure 23.

heading: F BATCH DIVERSITY
text: Figure 24 gives a comparison of sampling methods with gradient embedding in two settings (OpenML # 6, MLP, batchsize 100 and SVHN, ResNet, batchsize 1000), in terms of uncertainty and diversity of examples selected within batches. These two properties are measured by average `2 norm and determinant of the Gram
MLP
ResNet
VGG
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 −∞. These areas are indicated by gaps in the learning curve for CONF. Situations where there are many gaps in the CONF plot seem to correspond to situations in which CONF performs poorly in terms of accuracy. 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 k-DPP IN BATCH SELECTION
In Figures 25 to 31, we 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 a time complexity of O(τ · (k2 + kd)) and space complexity of O(kd + k2), where τ is the number of sampling steps. We set τ as b5k ln kc in our experiment. The comparisons for batch size 10000 are not shown here as the implementation of k-DPP sampling runs 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 are 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-MEANS++.

Review summaries:
This paper examines the problem of warm-starting the training of neural networks. In particular, a generalization gap arises when the network is trained on the full training set from the start versus being warm-started, where the network is initially (partially) trained on a subset of the training set, then switched to the full training set. This problem is practical, as it is often preferable to train online while data is collected to make up-to-date predictions for tasks (such as in online advertising or recommendation systems), but it has been found that retraining is necessary in order to obtain optimal performance. The paper also mentions active learning, domain shift, and transfer learning as two other relevant and important problems.

The author proposes different approaches to the problem of  "warm-started" neural networks. Models trained from scratch on the whole dataset have better performance than "warm-started" models, which are trained with weights initialized from training using part of the available data.  The authors change hyperparameters like batch size and learning rate and demonstrate a tradeoff between generalization performance of the model and time, required for its training. We can also see that the choice of hyperparameters, necessary for the best performance, levels benefit in time from "warm starting."