Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: summary: The paper proposes a large-scale batch active learning approach.  "large-scale" means large-scale batches, e.g., 100K-1M. The key idea is to first perform Hierarchical Agglomerative Clustering on the pool of data points. Each time, it compute the confidences of each data point (based on the difference between the largest two predicted class probabilities), and picks the ones with the lowest confidence, matches their clusters, and then samples the data points across these clusters in a round-robin fashion. The clustering is based on the second last layer's neurons (given the input). Some experiments were conducted to confirm the effectiveness of the method. 
main_review: The paper proposes a very simple method to select samples for active learning. The method makes sense. However, several severe issues are here. 

(1) Skeptical motivation. The paper claims it aims to select very large batches for active learning, like 100K-1M. That sounds violating the principle of active learning.  AL is intended to reduce the number of labels (and labeling cost) as much as possible. They key is to smartly select the training examples, so that we can use much less samples to achieve good performance (comparable to abundant data).  If you are able to offer so many training examples, why not just run batch learning on the large dataset?  Why do you use AL?

(2) Skeptical efficiency. The paper claims that their batch selection is very scalable. However, the most costly part --- the HAC step, takes a complexity of O(n^2 log(n)) , which is very expensive and not scalable at all. see line 145. Although the paper says the HAC can be accelerated in practice from multi-thread implementation. The complexity is still there, more than quadratic to the number of candidates. Although the selection step is fast, the overall efficiency is very limited, given that the pool can be orders of magnitude larger than a batch. 

(3) The paper claims BatchBALD (line 86) is infeasible for large batch size in practice. I think this is a wrong claim. BatchBALD is greedy heuristics, and the point is added into the batch one by one. It scales linearly in the size of the batch and data pool. The paper needs to explain why it is infeasible for large batch sizes. 

(4) The paper mentions BatchBALD in Intro, but does not compare with it in the experiment. It misses an important soa as the baseline.  
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper introduces a new active learning acquisition function, Cluster-Margin, which clusters the samples with the lowest confidence scores (margin scores), and selects samples round-robin from the clusters to obtain a diverse set of low-confidence points. The experiments show that it works with very large batch sizes (100k--1M). Additionally, the paper provides an initial theoretical analysis of their algorithm.
main_review: ### Originality

The suggested method seems novel. Compared to the CoreSet algorithm in active learning, which computes a cover of all unlabeled pool points, Cluster-Margin essentially approximates a cover of mainly *low-confidence* pool points. 

### Quality

The submission seems technically sound. The experiment results are impressive. Especially, the results on Open Images are impressive, but also the results on CIFAR-10 and CIFAR-100 show good improvements over the baselines. The Open Images results are great because a real-life dataset has other characteristics than smaller curated datasets ala CIFAR-10, etc, which shows promise for real-world applications of the proposed method.

### Clarity

The paper is very well written. The introduction and related work are great. The introduction is lacking citations, though. The algorithm and experiment section are also clear and of high quality. The theory section is difficult to understand and only seems to give a high-level overview of "Cluster-MarginV". The appendix is clearer on that. 

I believe it might be worth extracting the theory section into a separate contribution. I believe the algorithm and results are sufficient on their own. The fact that the theoretical motivation comes at the very end seems telling.

### Significance

I assume the paper will be of significance for practitioners. An expanded theory section could be interesting overall. It would be nice to have more results on additional large datasets. On the other hand, the paper already provides results for the common three datasets (CIFAR-10, CIFAR-100, and SVHN), and then provides results for the large and high-dimensional Open Images Dataset. Within the constraints, this seems absolutely reasonable.

### Summary
Strengths:

+ method novel
+ very well written
+ experiments convincing: great results on large real-life datasets

Potential improvements
- the introduction might deserve more citations
- theoretical motivation needs to be more fleshed out (it feels a bit tacked on in its placement in the paper)

### Questions
1. Were there any experiments run that recompute the embeddings after every acquisition round? This could improve the performance as the quality of the embeddings ought to improve as more labelled data is used for training (esp given the large batch sizes).
2. Could Accuracy be provided instead of mAP for the CIFAR-10, CIFAR-100 and SVHN results? It is very hard to compare results as accuracy is the usual metric, and plots are not provided in the appendix either.

I would be happy to increase my score if the above questions are answered.

### Typos

Algorithm 2: line 5: $HAC(E_X, \epsilon, \infty)$: should the last argument be 0 instead of $\infty$? Otherwise, Algorithm 1 will early out right away in line 1.
limitations_and_societal_impact: I agree with the author's answer in 1.c) about societal impact. Generally, the paper does not introduce concerns beyond the concerns of Active Learning itself, which are not part of the paper (but prior art): acquisition functions can introduce additional bias given how they select data to be labelled and included.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a large-batch active learning Clustering based algorithm, Cluster-Margin. The authors show that the algorithm is more efficient and more effective than comparable approaches (Random, Margin, CoreSet and BADGE) on several benchmark datasets (Open Images Dataset, CIFAR10, CIFAR100 and SVHN). The authors also provide initial theoretical guarantees justifying the relevance of the algorithm. 

main_review: Originality: 
The algorithm seems to be novel and differs from previous comparable approaches like CoreSet or BADGE. Related work is adequately cited. 

Quality: 
The authors show empirically that their algorithm, Cluster-Margin, is both more efficient (O(nlog(n) vs O(n√(n)) than CoreSet and BADGE in practice and more effective. In particular, the algorithm clearly outperforms CoreSet, BADGE, Margin and Random on the Open Images dataset. The algorithm requires 29% less labels than the second-best model in the 100k batch-size setting and 60% less labels in the 1M batch-size setting to achieve the same result (mAP). Cluster-Margin also outperforms all other methods on CIFAR10, CIFAR100 and obtains a similar performance on SVHN. 

The authors also establish a theoretical guarantee for the Cluster-MarginV algorithm and show that those results hold for the Cluster-Margin algorithm in specific settings. In particular, they show that the Cluster-MarginV algorithm has a label complexity bound which improves over the Margin algorithm by a factor beta. They also show that this improvement is possible, under specific hypotheses like an optimal volume-based sampler, when the dimensionality of the embedding space is small or when the batch size k is large. They also show that the optimal volume-based sampler is approximately equivalent to the Cluster-Margin algorithm. They finally show that log(k) is an upper bound on the improvement of query complexity for any sampler. 
The authors are aware and mention that their theoretical results are initial and that equating volume based samplers and the Cluster-Margin algorithm is an open research question. 

Clarity: 
The paper is very clear and well organized. The authors detail the hyper-parameters and compute details used for the experiments. The Cluster-Margin algorithm is also explained in detail.  

Significance: 
The results are important as the algorithm allows for more efficient and effective large-batch-size active learning compared to existing methods. The authors also provide initial theoretical guarantees to explain the improvements obtained with the Cluster-Margin algorithm. 


limitations_and_societal_impact: It would be interesting to perform some experiments to assess if the results hold for other data modalities, like NLP (text) or ASR/Speech (audio) for instance.
review_title: null

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