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.
The paper proposes a new method for active learning, which picks the samples to be labeled by sampling the elements of the dataset with highest gradient norm, under some constraint of diversity. The aforementioned gradient is computed w.r.t. the predicted label (rather than the true label, that is unknown) and diversity is achieved by sampling via the k-MEANS++ algorithm.
The paper is well written and while the experiments look thorough, the motivation to support the proposed method seem too weak and unconvincing as does the discussion of the results, which is why I am leaning toward rejection. 
I am willing to amend my vote if the authors provide stronger (not empirical) motivations on why using the gradient norm w.r.t. the predicted label is a better metric than those in the literature, and  More comments below.
 
Detailed feedback:
1) The paper lacks a proper motivation as to why using the norm of the gradient is a better metric than the many others already present in the literature. In particular, I cannot think of any case where it would be best to use that than the entropy of the network’s output distribution, even though the empirical results seem to suggest otherwise. Specifically, while I believe that in many cases it will be similarly good, if we consider the case when the network is able to rule out most of the classes but is unsure on a small fraction of them, the entropy will better reflect this uncertainty than the norm of the gradient of the predicted class. 
Generally speaking, I believe that the use of the norm of the gradient of the predicted class should be much better motivated, being the core idea of the paper. Stating that it is cheap to compute and empirically performs as well as k-DPP in two experiments is not convincing enough in my opinion.
2) I wonder how much of the performance of BADGE is due to k-MEANS++ and how much to the choice of using the gradient norm. Please perform an ablation study where you can e.g., replace the gradient norm with the entropy, or replace k-MEANS++ with random sampling, and discuss the results. 
3) How is the embedding “ground set” space determined for k-MEANS++? How are the centroids determined? In which space? It is unclear to me how k-MEANS++ is used in the context of the norm of the gradients. Please improve the explanation in the main text.
4) Please add a curve for k-DPP to the plots in the main text, rather than having separate plots for it in the appendix. Also, it would be interesting to compare against Derezinski, 2018 as well, if that’s the current state of the art (which is what I infer from your text, but I might be wrong).
5) The paper builds on the claim that the gradient norm w.r.t. the prediction is a lower bound for the gradient norm induced by any other label, yet Proposition 1 that proves it is in Appendix B. This prove is central to the proposed idea and should be in the main text.
6) The authors claim that to capture diversity they collect a batch of examples where the gradients span a diverse set of directions, but it’s unclear to me that k-means++ actually accomplishes that. Where is the *direction* of the gradient taken into account in the algorithm?
7) The “discussion” section is really a “conclusion” one, and indeed a proper in-depth discussion of the experiments is missing. Please expand the comments on the experimental results. 
8) The metric to compute the “pairwise comparison” looks quite convoluted. Is it common in the literature? If so, please add a reference. If not, can you motivate the use of this specific formula?
9) The random baseline seems to be very competitive. Why is that? Please provide your intuition. Could this be indicative that the baselines have not been tuned properly?
10) Introduction: the sentence “[deep neural networks] successes have been limited to domains where large amounts of labeled data are available” is incorrect. Indeed, neural networks have been used successfully in many domains where labelled data is scarce, such as the medical images domain for example. Please remove the sentence.
11) Introduction: please add a sentence to explain what a version-space-based approach is.
12) Is Figure 2 the average over multiple runs or a single run?
13) Notation: please do not use g for the gradient (g^y_x) and for the intermediate activations (g(x; V)).
14) The lower margin seem too wide. Please make sure you respect the formatting style of the conference.
Minor:
- Notation: if you must shorten g^{\hat{y}}_{x} please do so with \hat{g}_{x} and equivalently shorten g^{y}_{x} as g_{x}
- Notation: in the pairwise comparison, please don’t reuse i to denote an algorithm (it is used a few lines before to compute the labeling budget)
- Please add reference to Appendix A when k-MEANS++ is first referred to in page 2.
- Page 3,  when Proposition 1 is mentioned add reference to the location where it’s defined.
Typos:
- Page 2: expenive -> expensive
- Page 5: Learning curves. “Here we show ..” -> Remove “here”
- Figure 3: pariwise -> pairwise
- Page 7: Apppendx E
----------------------
Updated review:
I thank the authors for for taking the time to address all my comments, and clarifying some of the misunderstandings I had. I am happy to revise my score accordingly.