Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper frames active learning as an integer optimization problem, that minimises the distance Wasserstein distance between unlabelled pool of data. This is done in a feature space (in this case trained using self-supervised methods all the data). The method outperforms existing active learning methods for very small labelling budgets, with theoretical guarantees of integer optimisation problem (although not the performance in terms of model accuracy itself).
main_review: Strengths:
-- Tackles active learning from a slightly different approach.
-- Wasserstein distance well justified and bounds of the integer optimisation problems are well specified (proof not checked carefully however)
-- Reasonable improvements over previous approaches: 
-- Well written paper: clear, algorithms and pseudo-code provided for ease of understanding and reproducibility.
-- Thorough evaluation in low data regime against other SOTA active learning methods, in a number of scenarios (with SSL, classical active learning setting and domain adaptation).
-- Time and complexity analysis provided

Weaknesses/Potential Areas of Improvement
-- Stated that there is improvement for high budget settings, but no evidence is provided in the text of that?
-- In fact, it seems like a trend for a drop-off in performance in terms of accuracy  as budget increases; would be nice to see that even it does occur.
-- There is limited analysis of scaling to larger unlabelled datasets or datasets with more classes. Skeptical that performance would be good, or that the method would scale well. Although, again training time is often cheaper than labelling so this is not necessarily a problem, but some experiment here would be useful.

Other questions:
-- Were the features used for greedy k-centers the same as the features used in your approach? Or did you continue to use the VGG16 features that was used in Sener and Savarese?
summary_of_the_review: Well written and polished paper with novel angle on the active learning problem, with some theoretical guarantees and good experimental performance in low budget scenarios. Would like see some additional results, but this a good paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work tackles the problem of active learning. In every iteration the subset of the unlabeled data pool that needs to be labeled is selected by posing it as an Integer Programming (IP) problem that minimizes the discrete Wasserstein distance. Generalized Benders Decomposition algorithm is used to solve this IP through relaxations. It is shown to converge and also some acceleration techniques are provided. All the above are supported through extensive empirical analysis.
main_review: Strength

The paper is well written. It describes the problem in detail. I believe using Wasserstein distance to bound the core set loss is a unique and interesting way of dealing with the active learning problem. The approaches are also backed by strong empirical analysis. I find this a very strong paper. I did not get to check all the proofs but I have checked some of them and they seem correct. 

Weaknesses

I dont find any weaknesses of the paper. This seems very relavant work and a strong accept in my view.
summary_of_the_review: Overall a strong accept for tackling an important problem.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a (batch mode) active learning method that chooses a subset of data points to be labeled through approximating the whole dataset in terms of Wasserstein distance, which is an upper-bound of the generalization error. The selection is formulated as a large-scale mixed integer programming, and the authors propose to solve it by the GBD. For acceleration, some additional constraints are proposed. Experimental results show that the proposed method is better (or competitive) than baseline methods like k-center, k-medoids, and WAAL.
main_review: **Strong Points**

- The paper discusses why Wasserstein distance is minimized (Theorem 1).
- The experiments show the effectiveness of the proposed method in downstream task (active learning).
- Presentation is clear.

**Weak Points**

- [Effect of the embedding method is not investigated] SimCLR is used for obtaining the encoding but I am curious what happens if other embedding methods are used. Intuitively, the embedding is very important because the proposed method assumes that nearby points in the embedding space have the same label. In the second paragraph of Section 5, the authors say "our approach is also effective without self-supervised features"; what is the meaning of this sentence?
- [Scalability] Scalability of the proposed method seems to be low. The experiments include relatively small datasets. Does the proposed method scale even for datasets including millions of data points or larger budget values? For example, Table includes larger B's results (from 1000 to 6000); how large is the computation cost? This concern is mainly from real application scenarios; ML projects usually have budget to label more than 1000 data points (and much larger unlabeled data pool for which we need to compute Wasserstein distance).

**Questions**

- The inequality in pp.2 seems to be equal. In what sense do you argue that the RHS upper-bounds the generalization error?
- How do we solve W-RMP? Do we use ILP solver?
- This paper deals with the batch mode active learning. Is it possible to extend the proposed method to the classical sequential active learning?
summary_of_the_review: This paper is well-written and motivated, with a theoretical guarantee.
Before seeing the other reviews, I am positive to accept the paper although including some concerns (e.g., scalability).
Please answer and clarify my concerns described above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies active learning from a mixed integer programming perspective. The active learning strategy is representation-based, and aims at selecting a core set that minimizes the Wasserstein distance. Various tricks, e.g., enhanced optimality cuts and pruning, from the integer programming literature are used to accelerate the algorithm. Empirical results show advantages of the proposed algorithm over existing ones.
main_review: The paper is well-written and easy to follow. The authors provide an integer programming based approach for representation-based active learning, which shows empirical advantages over existing ones. I summarize my questions as follows.

1. In section 3.2, the authors compare the size of the original optimization problem in Eq (4) and the relaxed one. In the relaxed problem, however, one needs to compute the Wasserstein distance at each iteration. What is the computational complexity of computing the mentioned Wasserstein distance? It would be great to include the explicit complexity, rather than just saying that ``efficient algorithms exist''.
2. The author mentioned that the proposed method usually takes longer to make selections. I wonder how well the proposed method performs when it is given the same running time as other baselines, e.g., 3 minutes for both k-medoids and the proposed method?

summary_of_the_review: I think overall the approach makes sense, but I didn't find significantly novel contributions, either theoretically or empirically (maybe the authors could point out their novel contributions). As a result, I'll vote for a weak acceptance.
review_title: null

Meta-review: This is an interesting submission, which was overall well received by the reviewers. I would recommend the authors to discuss further the vast modern litterature on efficient computation of Wasserstein distances and their minimization (see, e.g. Peyré and Cuturi 2019, and references therein)
Decision: Accept (Poster)