On The Difficulty of Warm-Starting Neural Network Training
Authors: Jordan T. Ash
Ryan P. Adams
Venue:  (2020)
Keywords: deep learning
neural networks

Abstract: In many real-world deployments of machine learning systems, data arrive piecemeal. These learning scenarios may be passive, where data arrive incrementally due to structural properties of the problem (e.g., daily financial data) or active, where samples are selected according to a measure of their quality (e.g., experimental design). In both of these cases, we are building a sequence of models that incorporate an increasing amount of data. We would like each of these models in the sequence to be performant and take advantage of all the data that are available to that point. Conventional intuition suggests that when solving a sequence of related optimization problems of this form, it should be possible to initialize using the solution of the previous iterate---to "warm start'' the optimization rather than initialize from scratch---and see reductions in wall-clock time. However, in practice this warm-starting seems to yield poorer generalization performance than models that have fresh random initializations, even though the final training losses are similar. While it appears that some hyperparameter settings allow a practitioner to close this generalization gap, they seem to only do so in regimes that damage the wall-clock gains of the warm start. Nevertheless, it is highly desirable to be able to warm-start neural network training, as it would dramatically reduce the resource usage associated with the construction of performant deep learning systems. In this work, we take a closer look at this empirical phenomenon and try to understand when and how it occurs. Although the present investigation did not lead to a solution, we hope that a thorough articulation of the problem will spur new research that may lead to improved methods that consume fewer resources during training.

Under review conference paper at ICLR 2020
DEEP BATCH ACTIVE LEARNING BY DIVERSE, UNCERTAIN GRADIENT LOWER BOUNDS
Anonymous authors Paper under double-blind review
ABSTRACT
We design new algorithm for hatch 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 a useful option for real world active learning problems.
INTRODUCTION
In recent years, deep neural networks have produced state-of-the-art results on 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 (eedback-driven fashion. Active learning algorithms aim identify and label only maximally informative samples, that high- performing 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 applicable.
How should a practical, general-purpose, label-efficient active learning algorithm for deep neural networks be designed? Theory for active learning suggests version-space-basel approach (Balcan et al. 2006), which explicitly or implicitly maintains set of plausible models, and queries examples for which two models that make different predictions. But when using highly-expressiv 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 '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, 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 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 function of the statistical properties of the data in question. These
multilayer-perceptrre
A diversity-based approach might work well

---

Under review conference paper at ICLR 2020
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 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 +-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 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
B and experiments in Section 4 We defer discussion of related work to Section S
2 NOTATION AND SETTING
Define [K] := (1,2.... KJ. Denote by X' the instance space, and y the label space. In this work we consider multiclass classification, so that y [K]. Denote by the distribution from which examples are drawn, Dx the unlabeled data distribution, and Dylæ 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 Dyyx for any E U. We use En to denote expectation under the data distribution D. Given a classifier h : X + V. which maps examples to labels, and a labeled example (z, y). we denote the 0/1 error of h on (x, y) as E0i (h(x), y) = [h((x) y). The performance of a classifier h is measured by its expected 0/1 error, i.c. Ep oo (f(z). v)] = PT( (h(x)) o 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 (Ir, y). where each E S is picked from U, followed by a label query, we use Eg as the sample averages over S.
In this paper, 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 9 as he since the architectures are fixed in any given context, and our classifiers take the form ho argmax,e[k] fxx; y- where f(x; 0) E K is vector of scores assigned to candidate labels, given the example x and parameters 0. We optimize the parameters by minimizing the cross-entropy loss [s[[ce(f 0), y)] over the labeled examples, where (c v) EK [ i) In 1/p..
3 ALGORITHM
BADGE, described in Algorithm [ 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 f, for every x in the pool
U, compute the label ((x) preferred by the current model, and the gradient 92 of the loss on (x. (())) with respect to the parameters of the last layer of the network. Given these gradient embedding vectors {g. U). BADGE. selects set of points by sampling via the k-MFANSS+ initialization scheme Arthhr and Vassilvitskij] 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.
2

---

Under review conference paper at 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 (x;( 0).
3: for f = 1, ........ T: do
4: For all examples x in U S::
1. Compute its hypothetical label ((x) = ha, (2)).
2. Compute gradient embedding 9r 89 of the final (output) layer.
8 [(](( 0), (==:)))o=0, where Oon refers to parameters
5: Compute St, random subset of U,S, using the +-MEANS++ seeding algorithm, on {gz x E U \ 1), and query for their labels.
6: S USSSSS U..
7: Train model 0.41 on S by minimizing Es(ece(f(2;0))
8: end for
9: return Final model Or+1-
The gradient embedding. Since deep neural networks are optimized using tradient-basedd methods, 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 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 compute the gradient. As proxy, we compute the gradient if the model's current prediction on the example is the true label. We show in Proposition [ 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 highly certain about the example's label, then the example's s gradient embedding will have small norm (see example below). Thus, gradient embedding conveys information both about the model's uncertainty and potential update direction upon receiving label at an example.
Consider a neural network f where the last nonlinearity is a softmax, i.c. o(o), = <"////, e Specifically, ff is parametrized by = (W, V), where Aour = W = (W,T. ...., W E IR Kxd xd are the weights of the last layer, and V consists of weights of all earlier layers. This means that f(x; is the nonlinear function that maps an input x to the output of the network's 's penultimate layer. We define of o (f 0),y) for label y and Oz g as the gradient embedding in algorithm, where y = argmax,e(x] Ps. Fixing an unlabeled sample æ, we define = f(r;
o(W 2(x; V)), where
Proposition 1. For all y E {L...., K}. denote by 9 a LcD (f(: 0), y). Then 2pv [| V)I2
K
1| =
Σ
pt +
i=1
Consequently, 9 = argmin uekk] [|
Proof. Observe that by Equation ①
| 2 = Σ (p.- - 1yy 1)) 1=<; VI12
Σ
2s + 1 2pr) ||=(;; v)1l2.
The second part follows from the fact that argmax,yelat py-
3

---

Under review conference paper at ICLR 2020
DPP
k-means1
OpenML#6,, MLP, Batch size:
SVHN. ResNet, Batch size: 1000
SVHN, ReeNet, Batch size: 1000
00/0
Aasuwwyy
0000
0
2000
1000
ALabels quideed
N.obels querid
Rlabels quededd
Learning curves for BADGE versus k-DPP sampling with gradient embeddings for different scenarios. Right: A run time comparison (seconds) for BADGE versus D-DPP sampling corre- sponding to the middle scenario. The performance of the two sampling approaches nearly perfectly overlaps. Each line is the average over five independent experiments. Standard errors are shown by shaded regions.
Figure 1: Left and center:
The sampling step. We want the newly-acquired labeled dataset induce large and diverse changes 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 & 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 to sample from a k-DPP (Kulesza and Taskar 2011). That is, to select a batch of k points with a probability proportional to Drrently,Derezzinski 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 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 MCMC, where mixing time poses significant computational hurdle. The -f-h--oft algorithm of [Derezinski) (2018) has 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 (007), originally made to produce a good initialization for k-means clustering. ?:-MAAN++ seeding selects centroids by sampling points 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 [
This simple sampler tends to produce diverse batches similar to a k-DPP. As shown in Figure switching be- tween 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 kDD based gradient embedding sampling can be found in Appendix G
Figure 2 describes 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 with batches) and high magnitude. Other samplers, like furthest-first traversal for k-Center clustering (FF-K-CEN)) -CEETER,,,ER), do not seem to have this property. The FF-R-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 discusses diversity with respect uncertainty- based approaches.
4

---

Under review conference paper at ICLR 2020
Rand
k-center
OpenMiL 85, MLP, Batch size: 100
SVHN, ResNet, Batch size: 1000
OpenML 46, MLP. Batch size: 100
Aeonage nuem in Jake
Log oeeemteeeett on
52
Win
#1.bbel Querle
MLa0mls quariedd
#Labels quarted
Plots showing the log determinant of the Gram matrix of the gradient embeddings within batches as learning progresses. Right: The average embedding magnitude (a measurement of predictive uncertainty) in the selected batch. The k-centers sampler finds points that not diverse high-magnitude other samplers. Notice also that than k-DPP,
Figure 2: A comparison of batch selection algorithms in gradient space. Left and center:
k-MEANS++ tends to actually select samples that are both more diverse and a potential pathology of the k-DPP's degree of stochastisity. Standard errors are shown by shaded regions.
Example: multiclass classification with softmax activation. Recall that the neural network f has the form f(x; () o(W <<2;;<VV V)), where d()); = < es, (cE(p. v) Ei= I(y i) In l/p. By substitution,
e",, and the loss function the cross entropy,
(cE(f(a; In Σ emb=((xiV)) W, W =(;; V).
Given this, the i-th block of 9N is equal to
(gx) = ow: tee (f(x)))) (p. 1(0 (0- 1) 2(x;; V).
a
(I)
Based on this expression, we can make the following observations:
1. Each block of 9z is scaling of =<;; V), the output of the network's penultimate layer. this respect, IN captures the representation information of 2(;; V), the space in which diversity-based algorithms operate (Sener and Savarese 2018).
2. Proposition shows that the norm of 9u is a lower bound on the norm of the loss gradient induced by the example with true label with respect to the last-layer weights, i.e. I|g. S || |l. This suggests that the norm of gx conservatively estimates the example's influence on the current model.
3. If the current model 0 is highly confident about x, i.e. vector p is skewed towards standard basis vector ej, then y = j. and vector (p; - [ū i) has small length. Therefore, Iv 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 binary logistic regression (K = 2 and <(x; V) = X),, we provide further justifications why BADGE yields better updates than vanilla uncertainty sampling in Appendix B
5

---

Under review conference paper at ICLR 2020
4 EXPERIMENTS
We evaluate the performance of BADGE against several algorithms in the literature. 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 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 list of the baseline algorithms evaluated: the first algorithm performs representative sampling; the next three algorithmss 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 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, max (a;; 0);-
3. MARG (Margin Sampling (Roth and Small ) :uunceetainty--aaaee -based active learning algorithm that selects the bottom B examples sorted according to the example's 's multiclass margin, defined as f(I; 0)g- - f(z; 0)y', where I and y' are the indices of the largest and second largest entries of f(z;; 0).
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 's predictive class probability distribution, defined as (1F(x;; 0),)) K 1). where (p) = > P; In t/p.
5. ALBL (Active Learning by Leaming (Hsu and Lin 2013)): A bandit-style meta- meta-active learning algorithm that selects between CORESET and CONF at every round.
6. RAND: the naive baseline of randomly selecting h: examples to query at each round.
We consider three neural architectures: a two-layer Perceptron with ReLU activations (MLP), 18- 18-layer convolutional ResNet (He et al. 2016), and an I1-layer VGG network (Simonyan and Zisserman, 2014). We evaluate algorithms using three image datasets, SVHN (Netzer et al. 2011). CIFARIO (Krizhevsky) 2009) and MNIST (LeCun et al. 1998), and four non-image datasets from the OpenML repository (#6, #155, #156, and #184). 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 Yangg et al., 2017). All models are trained in Py Py/oh Paszke et al. 2017).
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 OpenML datascts are from openml. org and are selected on criteria: first, they have at least 10000 samples; second, neural networks have significantly smaller test error when compared to linear models.
6

---

Under review conference paper at ICLR 2020
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
SVHN, ResNel, Batch size: 100
#156 MLP. Batch size: 1000
CIFAR10 VGG, Batch size: 10000
#Labels
4L.bbls quaried
48, 48.bbed quaried
(b)
Figure 3: Active learning test accuracy versus the number of total labeled samples for a range of conditions. Standard errors shown by shaded regions.
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 early rounds of training, 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.
better to do diversity sampling, and later
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 easy learn. Otherwise, penultimate layer repre- sentations are not meaningful, and diverse sampling can be deleterious. For this reason, CORESET often performs worse than random sufficiently complex data when not using convolutional network (Fig- ure 3b). That is. the diversidy induced by uncondi- tional 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 un- certainty information in BADGE can give it an ad- vantage over pure diversity approaches (Figure 3c). Comprehensive plots of this kind, spanning archi- tecture, dataset, and batch size are in Appendix
BADGE
ALBL
Careset Conf
Entropy Rand
BADGE
0.0
9.18
10.97
12.56
3.88
13.16
10.04
12
ALBL
0.34
0.0
5.16
3.15
0.31
6.61
4.95
10
1.65
2.02
0.0
6.55
3.08
8:13
6.56
8
Conf
Marg
0.96
7:14
10.87
0.0
11.33
9.34
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
Pairwise comparisons. We next give a compre- hensive comparison over all pairs 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 sim- ilar performance, hence the comparison between algorithms in the large sample limit uninteresting. For this reason, for each combination of (D, B, A),
0.66
4.08
6.9
5.93
1.56
8.01
6.01
Figure 4: A pairwise penalty matrix over all experiments. Element Pt., corresponds roughly to the number of times algorithm outperforms algorithm, Column-wit averages the bottom show overall performance (lower better).
7

---

Under review conference paper at ICLR 2020
we select set of labeling budgets 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 x 11 = 33. Specifically, we compute ne. the smallest number of labels where RAND'S s aceuracy reaches 99% of its final accuracy, and choose label budget L from (M + 2 B E [[log( noo M) []] 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) {e),..., algorithm respectively.
..] }
and { (c)..... ..} for each
We compute the t score as t = VoR/e, where
1 Σ (c] -cj 10)2. A D (e) -5),)===
We use the two-sided I-test to compare pairs of algorithms: Algorithm i is said to beat algorithm j in this setting i > 2.776 (the critical point of p-value being 0.05), and similarly algorithm j beats algorithm if t 2.776. For each (D, B, A) combination, suppose there are B,D different values of L. then for each L. if algorithm/ i beats algorithm j. we accumulate a penalty beats algorithm we accumulate penalty of 1/n //D,,BB. B.A P3.s. The choice of the penalty value 1/mD, 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 indicates the number of settings where algorithm é beats other algorithms; and each column j indicates the number of settings where algorithm gets beaten by other algorithms.
1/nD,B,. to P.ji otherwise, if algorithm j
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, I.) combination, we have five average errors for each algorithm i: é; E eç. 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 ne, e where r is the index of the RAND algorithm. By definition, the normalized errors of the RAND algorithm are identically in all settings. Same as in the generation of penalty matrices, for each B, A)
1.0
Curnuattvv furuuatveeerquuaa frequency
0.6
B,
combination, we only consider a subset of L values from the set (M + 2 : E [[log((no [)]] in addition, we assign a weight proportional to 1/nD,B,, A to each (D, (D B, L) combination, where there are B. different L values for this combination of (D, B, A). We then plot the cumulative distribu- tion functions (CDFs) of the normalized errors of all algorithms: for value of xr the y value is the total weight of settings where the algorithm has normalized error at most in general, an algorithm that has a higher CDF value has better performance.
Normalized error
Marg
AL BL
Conf
Entropy
Figure 5: Cumulative distribution function of the normalized errors of all algorithms.
We show 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 22 and 23 in Appendix [E] we can conclude that, when the batch sizes are small (100 or 1000), 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 the best performing approaches.
8

---

Under review conference paper at ICLR 2020
5 RELATED WORK
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 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, fundamental problem in computational geometry. Inspired by generative adversarial learning. (Gissin and Shalev-Shwand 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 [014]] 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- baaaattoo--bedddd uncertainty reduction criteria; inspired by recent advances on adversarial examples generation, (Ducoffe and Precioso 2018) uses the distance between example and one of its adversarial examples 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 sam- pling. For example, (Baram al. (2004] Hsu and Lin 2015) present meta-active learning algorithms that can combine the advantages of different active learning al algorithms. Inspired by expected loss minimization, (Huang et al., (210)) develops 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| 2013), 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 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 al. 2015). In these works, batch selection is often formulated as an optimization problem, with objectives based on (upper bounds of) average ligeliie,, average squared loss, etc.
A different query criterion based on expected gradient length (EGL) has been proposed in the literature (Settles jtt al. 2008). In recent work, (Huang et al. 2016) show that the EGL criterion is related to the T Tooptmaaiity 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. 201 7a) 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.] [0117]] Chang et al. 2017). These works aim at reducing computation costs or finding a hetter 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-
9

---

Under review conference paper at ICLR 2020
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).
6 DISCUSSION
We have established that BADGE is empirically an effective deep active learning algorithm across different architectures and batch sizes, performing similar better than other active learning algorithms. A funda- mental remaining question is: "Why?" While deep learning notoriously difficult to analyze theoretically, there 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 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 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.
REFERENCES
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In Machine Learning, Proceedings the Twenty-Third International Conference (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25-29, 2006, pages 65-72, 2006.
Alina Beygelzimer, Daniel J Hsu, John Langford, and Tong Zhang. Agnostic active learning without constraints. In Advances in Neural Information Processing Systems, pages 199-207, 2010.
Nicolo
Claudio Gentile, and Francesco Orabona. Robust bounds for classification via selective sampling. In Proceedings of the 26th annual international conference on machine learning, pages 121-128. ACM, 2009.
David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. In Proceedings of the eighleenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027-1035. Society for Industrial and Applied Mathematics, 2007.
Alex Kulesza and Ben Taskar. k-dpps: Fixed-size determinantal point processes. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pages 1193-1200, 2011.
Michal Dereziński and Manfred K Warmuth. Reverse iterative volume sampling for linear regression. The Journal of Machine Learning Research, 19(1):83-8811, 2018
Byungkon Kang. Fast determinantal point process sampling with application clustering. Advances in Neural Information Processing Systems, pages 22192327, 2013.
Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei. Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes. In Conference on Learning Theory, pages 103-115, 2016.
10

---

Under review conference paper at ICLR 2020
Michal Dereziáski. Fast determinantal point processes via distortion-free intermediate sampling. arXiv preprint arXiv:/811.03717, 2018.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. ew net/
In International Conference on Learning Representations, 2018. URL
Eorum? Elaluk RW
Dan Wang and Yi Shang. A new active labeling method for deep learning. In 2014 International joint conference on neural networks (IJCNN), pages 112-119. IEEE, 2014.
Dan Roth and Kevin Small. Margin-based active learning for structured output spaces. In European Conference Machine Learning, pages 413-424. Springer, 2006.
Wei-Ning Hsu and Hsuan Hsuan-Tien Lin. Active learning by learning. In Twenty-Ninth AAAI conference on 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 arXiv: /409. 1556, 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 Botton, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-233 23224, 1998.
Jordan Ash and Ryan P Adams. On the difficulty of warm-starting neural network training. arXiv preprint arXiv: 19.008475 2019.
Yuo-Yuan Yang, Shao-Chuan Lee, Yu-An Chung, Tung-En En Wu, Si-An Chen, and Hsuan-Tien Lin. libact: Pool-based active learning in python. arXiv preprint arXiv: 2017.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary VeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Burr Settles, Active learning literature survey. University of Wisconsin, Madison, 52(55-66):11, 2010.
Sanjoy Dasgupta. Two faces of active learning. Theoretical computer science, 412(11))1767-1788) 2011.
Steve Hanneke. Theory of disagreement-baane based active learning. Foundations and Trends in Machine Learning, 7(2-3):131-309, 2014.
Yonatan Geifman and Ran El-Yaniv. Deep active learning over the long tail. arXiv preprint arXiv:1711.00941
2017.
Daniel Gissin and Shai Shalev-Shwartz. Discriminative active learning, 2019. openreview www.:n/oooooooorlllleeeo
URI. https://
Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classification. pages 45-66, 2001.
Greg Schohn and David Cohn. Less is more: Active learning with support vector machines. Citeseer.
11

---

Under review conference paper at ICLR 2020
Gokhan Tur, Dilek Hakkani- and Robert Schapire. Combining active and semi-supervised learning for spoken language understanding. Speech Communication, 45(2):171-186, 2005.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In Proceedings of the 34th International Conference on Machine Cooninn--Volunee 70, pages 1183-1192.
JMLR. org. 2017.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. arXiv preprint /80.009444 2018.
William H Beluch, Tim Genewein, Andreas Nürnberger, and Jan M Köhler. The power of ensembles for active learning image classification. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 9368-9377, 2018.
Yoram Baram, Ran EI Yaniv, and Kobi Luz. Online choice of active learning algorithms. Journal of Machine Learning Research, 5(Mar):255 25M5r)):555299)) 291, 2004.
Sheng-Jun Huang, Rong Jin, and Zhi-Hua Zhou. Active learning by querying informative and representative examples. In Advances in neural information processing systems, pages 892-900, 2010.
Yuhong Guo and Dale Schuurmans. Discriminative batch mode active learning. Advances in neural information processing systems, pages 593-600, 2008.
Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode active learning. ACM Transactions on Knowledge Discovery from Data (TKDD), 93)) 2015.
Yuxin Chen and Andreas Krause. Near-optimal batch mode active learning and adaptive submodular optimization. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning. volume 28 of Proceedings of Machine Learning Research, pages 160- 168, Atlanta, Georgia, USA. 17-19 Jun 2013. PMLR. URL http::/proceedings www. v28 / htccchen111 htm
Kai Wei, Rishabh Tyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International Conference on Machine Learning, pages 1954-1963, 2015.
Burr Settles, Mark Craven, and Soumya Ray. Multiple-instanee active learning. Advances in neural information processing systems, pages 1289-1296, 2008
Jajj Huang. Rewon Child, and Vinay Rao. Active learning for speech recognition: the power of gradients. arXiv preprint arXiv: 1612.0326, 2016.
Ye Zhang, Matthew Lease, and Byron C Wallace. Active discriminative text representation learning. In Thirty-Fire Fiirt 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 arXiv: 1604.0098. 2016.
Ying Wang, Rong Zhu, and Ping Ma. Optimal subsampling for large sample logistic regression. Journal of the American Statistical Association. 113(522):829-888) 2018.
Daniel Ting and Eric Brochu. Optimal subsampling with influence functions. In Advances in Neural Information Processing Systems, pages 3650-3659, 2018.
Cheng Zhang, Hedvig Kjellstrom, and Stephan Mandt. Determinantal point processes for mini-batch diversification. arXiv preprint arviv: Xrv: 1705.00077, 2017b.
12

---

Under review conference paper at ICLR 2020
Haw-Shiuan Chang, Erik Learned-Miller, and Andrew McCallum. Active bias: Training more accurate neural networks by emphasizing high variance samples. In Advances in Neural Information Processing Systems, pages (002-1012, 2017.
Alex Kulesza, Ben Taskar, et al. Determinantal point processes for machine learning. Foundations and Trends in Machine Learning, 5(2-3): 123-3)2223-26, 2012.
Stephen Mussmann and Percy S Liang. Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss. In Advances in Neural Information Processing Systems, pages 6955-6964, 2018.
A THE K-MEANS+ SEEDING ALGORITHM
Here briefty review the k-MEANS++ seeding algorithm by (Arthur and Vassilvitskii 2007). Its basic idea is to perform sequential sampling of k centers, where each new center is sampled from the ground set with probability proportional Vissilv 2007) that the set of centers returned is guaranteed to approximate the k-means objective function in expectation, thus ensuring diversity.
the squared distance to its nearest center. It is shown in (Arthur and
Algorithm 2 The k-MEANS++ seeding algorithm (Arthur and Vassilvitskii 2007)
Require: Ground set G' C TRd, size k.
Ensure: Center set C of size C {cI}, where e₁ is sampled uniformly random from G. for t = 2,...,k: do
Define D,(x)= mineec,-1 || cl12-
Ct SSmple from G with probability Eseo Detay
D.(z)²
C. U
end for return C₁.
B BADGE FOR BINARY LOGISTIC REGRESSION
We consider instantiating BADGE for binary logistic regression, where y = f-1,+1) Given linear classifier w, we define the predictive probability of w on x as (wl 0) = a ayy - 2)), where ((2) = Ite- is the sigmoid funciton.
Recall that j(x) is the hallucinated label:
+1 Pu (+1 ar, 0) 1/2
((x)
Pw (+1 a. 8) S 1/2.
The logistic loss classifier w on example (x, y) is defined as:
f(w, (a. v)) In(1
x)).
Now, given model w and example x, we define 9.- i fww, (z, 1) (0) -- x)) as the loss
gradient induced by the example with hallucinated label, and 9. = ou f(w, (x, = (1 (1-p..(y)l: 0))- the loss gradient induced by the example with true label.
à
13

---

Under review conference paper at ICLR 2020
OpenMI M.P..
100
OpenML Batch
OpenMi MLP,, 10000
HLazels queried
Rlabe cuated
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 6: Full learning curves for OpenML #6 with MLP.
Oper
OpenMLa155, Belch
OpenMLA155,
FLabels quereed
stabel querle
PLabo queree
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 7: Full learning curves for OpenMI. #155 with MLP.
Suppose that BADGE only selects examples from region S.. = (x: w x = 0}, then as (+1/2, 0) P.. (-1 0) = 1.2. we have that for all in S., 0r. 8x In for some 8, {+1]. This implies that, sampling from a DPP induced by 92 's is equivalent to sampling from DPP induced by 9u 's It is noted in MMsssmann and Liang (018) that uncertainty sampling (i.e. sampling from Dis 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 updates (Zhang al.) 2017b): this suggests that BA BADGE, when restricted sampling over low-margin regions (Sww). improves over uncertainty sampling by collecting examples that together induce lower-variance updates on the gradient direction of expected 0-1 loss.
C ALL LEARNING CURVES
We plot all learning curves (test accuracy 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 T9
D PAIRWISE COMPARISONS OF ALGORIHTM
addition to Figure 4 in the main text, we also provide penalty matrices (Figures 20 and 21). where the results are aggregated by conditioning a fixed batch size (100, 1000 and 10000) or on a fixed neural network model (MIP, ResNer 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 upper bound on all its entries. It can be seen uncertainty-bru bbased methods (c.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.
14

---

Under review conference paper at ICLR 2020
O195ML#166 M.P, Batch size: 100
OaonMLe106 MLP, Batch szz:: 1000
OnenML#156, MLP, Batch sac: 10000
VLabale Cuared
VLabela quared
ALabe cuMted
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 8: Full learning curves for OpenML #156 with MLP.
OpenMLe4184, MLP. Balch size: 100
OpenMLa184, MLP, Batch size: 1000
OpenMLA184, MLP. Balch size: 10000
querled
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 9: Full learning curves for OpenML #184 with MLP.
15

---

Under review conference paper at ICLR 2020
SVH-N,
SVHN, MLP, Batch size:
SVHN, MLP. sze:
1000
100m VLabele
1000
1300
300
SVHN. ResNel,
SVHN, ReeNel, Betch size: 1000
SVHNN ReeNeel, Batch
VLabele
MLabete
10000
SVHN, VGG,
VGG, Batch 1000
SVHNN, VGG, Balch 10000
50000 1000
PLabels querled
sLatels querled
PLabes 2uofid
queree
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 10: Full learning curves for SVHN with MLP, ResNet and VGG.
MNIST,, Batch
MLP. Batch size: 1000
MNIST, Betch 10000
querees
#latels querie
s.able-suwted
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 11: Full learning curves for MNIST with MLP.
16

---

Under review conference paper at ICLR 2020
size:
1000
2000
2000
2000
2000
2000
4000
CIFAR10,
CIFAR10, ReeNel.
CIFAR10, Belch 10000
20/00
5000
1000
2006
5000
CIFAR10, Batch
CIFAR10,
CIFAR10, Betch 10000
Acararo
Acourate
PLatel querle
statels querled
fLabes quefedd
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 12: Full learning curves for CIFAR10 with MLP, ResNet and VGG.
OpenMLA6, MUP.
OpenMLAG, Betch 1000
OpenML 10000
PLatels querded
querles
statels querie
Flabes-suwted
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 13: Zoomed-in in learning curves for OpenML #6 with MLP.
17

---

Under review conference paper at ICLR 2020
1555 MLP. Baich size: 100
OpenMLL115, MLP, Batch sice: 1000
1555ML MLP, Betch size: 10000
querled
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 14: Zoomed-in learning eurves for OpenMI. #155 with MI..
Oper
OpenMLa156, Belch
OpenMLA156,
VLabelx
100
KLazela
200
2006 ALabes cuarted
1000
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 15: Zoomed-in learning curves for OpenML #156 with MLP.
OpenMLe184 MLP, Batch size: 100
OpenML#184, MLP, Batch size: 1000
OpenMLA184, MLP, Batch sze: 10000
#Labels
#Lacela quaried
RLibes cuared
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 16: Zoomed-in learning curves for OpenML #184 with MLP.
18

---

Under review conference paper at ICLR 2020
SVH-N,
SVHN, MLP, Batch size:
SVHN, MLP. sze:
700
8000
Mlabele
1983
1300
300
SVHN, ResNel,
ReeNel, Betch
SVHNN ReeNeel Batch
2006
MLabeee
2000
2000
MLabele
2000
21:00
SVHN,
VGG, Batch
SVHNN VGG, Balch 10000
200 4000
slabels querled
#Latels querled
PLabes queree
quefied
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 17: Zoomed-in learning curves for SVHN with MLP, ResNet and VGG.
MNIST, Batch
MLP. Batch size:
MNIST, Betch 10000
quered
PL.t445 queried
s-ublessuwled
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 18: Zoomed-in learning curves for MNIST with MLP.
19

---

Under review conference paper at ICLR 2020
CIFAR1C, M.P.. Batch size: 130
CIFAR1C, MLP,, Batch size: 1000
10 MLP, Batch size: 10000
Mlabelk Guadied
Ml.btel quaetedd
CIFAR10, ResNet, Batch size: 100
CIFAR10, ResNet, Batch size: 1000
CIFAR10, ResNet, Batch size: 10000
#Label Querfod
#Lacel queried
PLabo's 2u00cc
CIFAR10, VGG, Batch sice: 100
CIFAR10, VGG, Batch sbc: 1000
CIFAR10, VBG. Batch sire: 10000
200
sLabels ouotlod
sLaces querled
PLabess
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 19: Zoomed-in learning curves for CIFARIO with MI.,, ResNet and VGG.
10000111)
BA0G2
ALD
Canuet
hand
BADGE
AUX
Encopy Band
$40:22
ADL
Enropy fund
AUN
A.8L
47
231
1:19
45
25
1.0
122
CommA
2.39
FF
Corf
0:2
0-2
5.
2.34
Ccet
6.0
112
3.2
2.7
265
Cnr
5-24
J
22
R.2
0:46
25
477
2:25
3:72
3:2
2.24
3.9
2
622
200
2.24
1.0
Aand
Rand
-3
Rand
-05
1.24
2.14
2.2
3.2
1.56
2.53
30
252
625
837
2:52
2:23
300
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 (i,j) j) corresponds roughly the number of times algorithm outperforms algorithm j. Column- wise averages at the bottom show aggregate performance (lower is better). From left to right: batch size 100, 1000, 10000.
20

---

Under review conference paper at ICLR 2020
MLPI21)
ResNett6)
(6)
AMM Carset
Mary R.Skaay Aaxi
AUM
Plng Belley RAKE
ACDIA
9.0
3.3L
27.67
25-6
277
31:44
6.39
-10
61140
66
0.22
33
2.00
662
13
3.04
3.6
33
64
0.00
C.2
8:92
2.02
1.4
9.0
86
3.21
ALBL
3.4
66
820
333
A.4L
93
60
Mag
5/22
76
202
24
1.45
Mag
86
C24
2.5
Par
C20
B24
2.25
Dr/w
6.44
23
607
60
86
2.46
64
0.92
6:30
60
2.6
94
64
66
9.2
G.8
6.2
6.00
1-32
3.0
0.29
659
C24
824
C22
2.59
4.5L
322
0.39
3.52
C15
8:57
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, A) combinations aggregated, which is also an upper bound on all its entries. Element (i,j) corresponds roughly to the number of times algorithm i outperforms algorithm j. Column Golumn-wise averages at the bottom show aggregate performance (lower is better). From left to right: MIP, ResNet and VGG.
Batch size: 100
Batch size: 1000
Batch size: 10000
04
Curta Wdve
60
0.5
87
09
0.1
12
07 86
08
3.0
12
03
34
07
80
09
14
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 to right: batch size 100, 1000, 10000.
CDFs OF NORMALIZED ERRORS OF DIFFERENT ALGORITHMS
In addition to Figure 5 that aggregates over all settings, we show here the CDFs of normalized errors by conditioning 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
F
BATCH DIVERSITY
Figure 24 gives comparison of sampling methods with gradient embedding in 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 measured by average E norm and determinant of the Gram
21

---

Under review conference paper at ICLR 2020
MLP
ReeNel
VGG
Ouitu alnu Bog
944
08
86 87
09
07 66
08
03
62
60
ALBL
Conf
Coreset
BADGE
Entropy
Marg
Rand
Figure 23: CDFs normalized errors the algorithms, group by different neural network models. Higher CDF indicates better performance. From left to right: MLP, ResNet and VGG.
matrix of gradient embedding, respectively. It can be seen that, K-MEANS++ (BADGE) induces good batch diversity 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 -oo. 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-R-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 31 we give running time and test accuracy comparisons between k-MEANS+ and k-DPP for selecting examples based on gradient embedding batch mode active learning. We implement the k-DPP sampling using the MCMC algorithm from (Kang 2013), which has a time complexity of O(T (A3 + kd)) and space complexity of (kk + 1²2), where r is the number of sampling steps. We set r as 55k In k in experiment. The comparisons for batch size 10000 not shown here the implementation of k-DPP sampling runs out of memory.
It can be from the figures that, although k-DPP and k-MEANS++ are based different sampling criteria, the classification accuracies of their induced active learning algorithm are similar. In addition, when large batch sizes are required (e.g. A 1000), the running times of k-DPP sampling are generally much higher than those of 6-MEANS++.
22

---

Under review conference paper at ICLR 2020
OpenML #6, MLP, Batch size: 100
SVHN, ResNet, Batch size: 1000
Log determinant batch
Log determinant of
-1000
1000
-500
-06
-2000
-106
-000
#Labels queried
@Labels queried
(a)
(b)
OpenML #6, MLP, Batch size: 100
SVHN, ResNet, Batch size: 1000
Average in batch
Average 1 norm in
1499)
#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 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 predictive uncertainty) in the selected batch. The k-centers sampler finds points that are not diverse high-man gigg-magnttude 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. Among all algorithms, CONF has the largest average norm of gradient embeddings within a batch; however, in OpenML #6, and the first few interations of SVHN, some batches have a log Gram determinant of 3o (shown gaps the curve), which shows that CONF sometimes selects batches that are inferior in diversity.
k-DPP
k-means++
Figure 25: Learning curves and running times for OpenML #6 with MLP.
23

---

Under review conference paper at ICLR 2020
Ocenttll p155, M. Barch 100
Grendd p155, MIP. Battouuzee: 100
Openki A151 MLD. Bateo 1050
Opentt 4155. MIP thatr 1050
k-DPP
k-means++
Figure 26: Learning curves and running times for OpenML #155 with MLP.
Obentill 2155, Banch siee
Gpentdl
OperkLLA15, MED. 1050
Opents
0:000 could
K-DPP
k-means++
Figure 27: Learning curves and running times for OpenML #156 with MLP.
OponMi Batth 100
OpenMLi1
OperMLL164,,
OpenMML9184
K-DPP
k-means++
Figure 28: Learning curves and running times for OpenML #184 with MLP.
24

---

Under review conference paper at ICLR 2020
SYIIN MLP, Sulon aou: 100
EVANN MLP, Barch aze 100
SVHNN, M.P.. Batch sizo 1000
SWHH, MLP. Butch stzz: 1000
SVANN Rastlet, Banch dize:
SVINN Redter Saten
EVINN Reabiet Batchsiow
5V0%, Resber, Batch sze
K-DPP
k-means++
Figure 29: Learning curves and running times for SVHN with MLP and ResNet.
MLP.. slae:
SLIEE comted
K-DPP
k-means++
Figure 30: Learning curves and running times for MNIST with MLP.
25

---

Under review conference paper at ICLR 2020
CIFAR10. MLP. Sanch 520
CIPAR10, MLP.P Satcn Ste.
CIFAR1S MLP. Balth doo 1000
CIFAR! 0, M.P. Batch slze 1000
CIFAR10 Rastel, sine:
CIFAR Bastie Banch dre:
CIFAR10 Reabat Batch Eze
CIARRO Reatiet Batchsio
k-DPP
k-means++
Figure 31: Learning curves and running times for CIFARIO with MLP and ResNet.
26


Reviews:
[{"review_id": "rygClmZstB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 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.\"\n\nThe core idea of the paper is the investigation of various possible causes of difficulty of \"warm start\" to reduce training time without damaging a generalization performance. The authors investigate the dependence of this effect with gradient values, regularization, part of \"warm started\" layers, noising weights, catastrophic forgetting, and so on. \n\nThe authors describe different problems where this research can be useful and tries to shed light on the causes of this problem, but the solution is not found. This article can be helpful for future researchers as they continue research in this direction from a warm start. However, it is hard to judge how valuable this contribution is.\n\nAlso, see a few minor comments:\n1. Maybe it should be useful to include in Table 1 results for models trained using only 50% of data.\n2. Typo: NVIDA -> NVIDIA (p. 6)\n3. It seems that the problem lies in the area of the complex learning landscape for optimization of Neural Networks as we end up in the worse local optimum if we use a warm start. Maybe one should attack the problem with this direction, as there are several papers that investigate how the loss function landscape looks like e.g. [1] \n4. It seems that the behavior becomes worse if we increase the complexity of the model. Investigation of the dependence of severity of warm start effect on e.g. number of layers in the network can be useful. Also, it can be possible to gain some theoretical insights and provable results while dealing with simpler models. [1.] H. Li, Zh. Xu et. al. Visua\n5. It might be useful to research the dependence of \"warm start\" effect from the portion of data on which the model was pre-trained. As I understand situations, where 80-90% of data are used in the first round of training, are more common.\n6. The authors provide us with graphics of accuracy on training dataset for \"warm started\" and trained from the scratch models. We can see that both models reach 100% train accuracy, and the authors state that it is impossible to spot the \"warm start\" problem on the training dataset because the metrics are equal. Maybe it could be useful to show graphics of loss function. Despite of similar 100% train accuracy, final losses might be different(\"warm start\" loss > from scratch loss). It may mean that in case of warm start we reach a local minimum, but not the best one. \n7. It might be a good idea to add to Table 2 results for not-regularized model in order to compare results with and without regularization and figure out what effect on \"warm started\" models regularization have.\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "rkxpchfIKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 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.\n\nThe paper attempts to investigate this phenomena from a few different avenues: (1) simple experiments segmenting the training set into two different subsets, then training to completion or partial training on the first subset before switching to training on the full set; (2) looking at the gradients of warm-started models; (3) adding regularization; (4) warm-starting all layers, then training only last layer; (5) perturbing the warm-started parameters. \n\nStrengths:\n\nI believe very strongly in the practical impact of the problems presented in this paper. These indeed are challenging problems that are relevant to industry that have not been given sufficient attention in the academic literature. I appreciate the initial experimentation on this subject, and the clear demonstration of the problem through simple experiments. The paper is also well-written.\n\nWeaknesses:\n\nSome questions I had include:\n\n- Why is the Pearson correlation between parameters of the neural network a good way of measuring the correlation to their initialization?\n\n- Why is it surprising that the magnitude of the gradients of the \"new\" data is higher than at a random initialization?\n\n- Why does this phenomena occur even though the data is sampled from the same distribution? \n\n- Does this work have any relationship with work on generalization such as:\n[1] Recht, Benjamin, et al. \"Do CIFAR-10 classifiers generalize to CIFAR-10?.\" arXiv preprint arXiv:1806.00451 (2018).\n[2] Recht, Benjamin, et al. \"Do ImageNet Classifiers Generalize to ImageNet?.\" arXiv preprint arXiv:1902.10811 (2019).\netc.\n\nAlthough I like the topic of this paper, the investigation seems too preliminary at this point. There is no clear hypothesis towards answering the problems proposed in the paper. There is also no analysis, which places the burden on the numerical experiments to demonstrate something interesting, and the experiments seem sparse and small-scale. For these reasons, I am inclined to reject this paper at this time, but I strongly encourage further exploration into the topic. \n\nSome potential questions or directions could include:\n\n1. What if only a single epoch of training is used on 50% of the data? Does the gap appear in that setting? I ask because one would expect that a single epoch of training on 50% of the data, then training on new data would be equivalent to training on the full dataset from the start.\n\n2. How does this gap change with respect to the (relative) amount of new data introduced into the problem? For example, if one were to only add a single datapoint to the training set, would one still observe this behavior? Could one potentially add data more incrementally (rather than half of the training set) and potentially mitigate this drastic change in the problem?\n\n3. There are optimization algorithms specifically designed for stochastic optimization (with a fixed distribution) versus for online optimization (online gradient, Adagrad). Is the online optimization framework perhaps more \"realistic\" than the stochastic optimization framework in these streaming/warm-starting settings?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "B1l_dMc5tr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\nThis paper conducted an empirical study on why training with warm starting has worse generalization ability than learning from scratch. The paper is interesting, however, it has something unclear to me, as explained below.\n\n\n1)\tThe scale and diversity of the study can be improved. Only three models and three datasets were examined, which might not be representative enough. For example, the popular Transformer model, the large-scale datasets like ImageNet, the language understanding and machine translation tasks, etc. were not included in the study. This may make the study less relevant to many important tasks and domains.\n\n2)\tThe interesting and highlight part of the paper is that it studies many different factors and aspects, including the influence of batch size, learning rate, regularization, moment, denoising, etc. However, I kind of feel that the experimental setting has some fatal problems, which makes the experimental results not convincing. The authors partitioned the dataset into two halves, using the first half for pre-training, and then use the whole datasets for continued training. Although the partitioning is random, given the limited size of the datasets, such a treatment will change the underlying distribution (frequency of the samples during training). The first half of the dataset plays a more important role in training: it was used during pre-training, and also used in training. So somehow the first half was used twice, or at least used more than once,  depending on the numbers of epochs in pre-training and training. This distribution change may make the training a little biased, and at least it is not a fair comparison with learning from scratch (the latter will not have such bias in data). So for a fair comparison, one needs to add some baselines to understand the influence of data frequency change. Without the understanding from this angle, the study may be mis-leading.\n\n\n**I read the author rebuttal, however, I still think the experiments are not comprehensive and the use of data partitions in the experiments are problematic (nothing to do with realistic or not, just for fair comparison with learning from scratch). So I would not change my assessment.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses the question of why warm starting could result in worse generalization ability than training from scratch.  The reviewers agree that increasing the circumstances in which warm starting could be applied is of interest, in particular to reduce training time and computational resources.  However, the reviewers were unanimous in their opinion that the paper is not suitable for publication at ICLR in its current form.  Concerns included that the analysis was not sufficiently focused and the experiments too small scale.  As the analysis component of the paper was considered to be limited, the experimental results were insufficient on the balance to push the paper to an acceptable state.
Decision: Reject