Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This work introduces a new active learning algorithm for the low-budget regime. The main idea is to maximize probability coverage. The method is demonstrated in both low-budget and high-budget regimes. Moreover, the author also conducts experiments on fully/semi-supervised settings to demonstrate the effectiveness of the method.
strengths_and_weaknesses: Pros:
- The task is important and fundamental in the research community.
- The low-budget regime is challenging for the realistic scenario.
- The experiments seem extensive and well-designed.

Cons:
- The training details are missing and making it difficult to follow.
- The experiments are only conducted in a small dataset.
- The comparison with TypiClust is confusing.
questions: 1. Please illustrate the data selection process with the proposed method. Using the feature of each data point or just the RGB image?  What are the points of the graph in the specific experiment?
2. The building process of the graph and data selection is time-consuming. Please elaborate on the cost of these two processes.
3. Please conduct experiments on a larger dataset or other tasks to demonstrate the method, especially for realistic applications. Like the full ImageNet or detection on the COCO dataset.
4. Comparing Fig.3(a) of this work with Fig.4(a) of TypiClust, the performance of TypiClust reported in this paper is lower than the result in TypiClust. Please clarify the difference between these two curves. Compared with the performance reported in TypiClust Fig.4(a), the improvement is marginal.

I would like to change the score if the concerns could be resolved in the rebuttal.
limitations: None
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper focuses on low-budget active learning tasks. The proposed method attempts to model the problem as Max Probability Cover question. As Max Coverage is known to be NP-hard problem, the author then adapts a greedy algorithm for subset selection for annotation through covering lens. The improvement of the proposed method over the baselines is shown in supervised and semi-supervised frameworks across different datasets
strengths_and_weaknesses: Strengths:

1. The idea of seeking maximize Probability Coverage for low budget AL is straightforward and the author gives theoretical proof for this.

2. It is interesting to treat Max Probability Cover and Coreset as dual problems.

3. Most of this paper is clear for practice and the insight for model design is well illustrated.

4. The improvement of the proposed method over the current state-of-the-art methods looks promising in low budget AL setting.

Weaknesses:

1. The greedy algorithm can not guarantee the optimality of Max coverage. Therefore, the sampling solution obtained by the greedy algorithm is hard to be optimal. 

2. Missing reference and comparison with ICML'22 Low Budget Active Learning via Wasserstein Distance: An Integer Programming Approach


questions: Why Max Coverage's objective is a submodular monotone function? Need a reference here.

The current greedy algorithm can not guarantee the optimality of Max coverage, the author may explore or discuss a better way to achieve optimal.
limitations: Adequately addressed the limitations and potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors propose Max Probability Cover which is the optimal strategy for 1-NN model in that it minimizes an upper bound on their generalization error.
As a data distribution is not known in practice, they use empirical data distribution which converts Max Probability Cover to Max Coverage.
To work around NP-hard nature of Max Coverage, they propose a greedy algorithm for the Max Coverage named ProbCover.
For 1-NN model, Max Probability Cover and Coreset are in “dual” relationship in that Max Probability Cover seek to maximize the coverage for a fixed \delta whereas Coreset seek to minimize \delta for the fixed coverage to 1.
In the low budget regime where the budget is not enough to cover the unlabeled set, the proposed ProbCover is effective than the existing AL methods most of which are designed for high budget regime. 
The authors demonstrate it using 3 different frameworks compared to 9 different baseline AL models.

strengths_and_weaknesses: Strength
1. This works is one of the first few works addressing the low budget regime problem in AL.
2. It theoretically demonstrates the close relationship (loose duality) between Max Probability Cover and Coreset in 1-NN model case. 
3. Hyperparameter tuning step is often ignored in AL but the authors address it (in this case \delta) in a reasonable way.


Weakness
1. The theoretical analysis is based on 1-NN model, which is not strong enough in practice. Also, there is a gap between 1-NN model and deep neural networks so there is a limitation of extending the theoretical results in Sec 2 to general architectures.

questions: 1. As discussed in Sec 3, the authors mentioned that their approach relies on the existence of a good embedding space. In Sec 4.3, although the authors demonstrated that being in a bad embedding space indeed makes the performance worse, I am not convinced that ResNet-18 trained on few hundreds of images would provide good representations for high dimensional inputs like images. 
It seems like being in the low budget regime and being in a good embedding space are controversial for over-parameterized neural networks. So, I think either the statement in Sec 3 is wrong or somehow ResNet-18 is in a good embedding space, which I don’t think is clearly demonstrated or justified. Could the authors elaborate it?

2. The authors clearly specify that the proposed method is for low budget regime. However, in practice, the budget $b$ would increase as time goes and so does the covered region. Then, there must be a point where a given problem transits from low budget regime to high budget regime. In that case, what do the authors think would be an efficient way (measurement) to detect the transit? 
limitations: Limitations have been mentioned throughout the paper.
review_title: null

Meta-review: metareview: This paper introduces an active learning method, ProbCover, that seeks to maximize probability coverage for the low budget regime. It also provides theoretical analysis and a dual way to view the proposed method with respect to methods better suited to the high budget regime like Coreset. The paper received two weak accept and a weak reject rating. After reviewing the paper, reviews, author responses, add additional discussion with reviewers, I believe that on the balance the strengths of the paper outweigh the weaknesses. Reviewers overall appreciated the importance of the task, the theoretical analysis, and thorough experiments. Most of the questions and clarifications about the approach were sufficiently addressed in the rebuttal, as well as additional requested experiments. Reviewers considered the use of a representation space from an auxiliary model to be a weakness, but I agree with the assessment (also concurred by reviewer) that this is not a limitation that invalidates the contributions of the paper. In practice it is a reasonable approach given the low budget regime. Reviewers also questioned the comparison with TypiClust, which was originally performed using only the SimCLR representation space, and not the one based on SCAN that TypiClust also used. The authors added comparison based on the SCAN representation for CIFAR-10 in their rebuttal, which is appreciated, and showed improvement in this setting as well. However, since an experiment on only one dataset was provided, and the improvement is smaller than for the main reported results using SimCLR (and TypiClust outperforms ProbCover at the smallest budget), the authors are highly encouraged include more comprehensive comparisons using the SCAN representation as well in the final paper for completeness. Overall, acceptance is recommended for this paper.
confidence: Certain
Decision: Accept