Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper describes a new active learning algorithm for classification problems. The authors propose a selection criteria that trades off between uncertainty and diversity. The novelty lies in formulating a three-pronged approach to diversity that still manages to maintain submodularity of the selection criteria:
1) a traditional diversity metric based on cosine similarity of embeddings
2) a new triplet/clique "loss" that penalizes the selection of nearby points
3) class-balancing and boundary-balancing constraints

By showing this three-pronged approach maintains submodularity, they are able to devise a greedy algorithm that still has a constant approximation guarantee to the optimal selection subset (as measured by the selection criteria). Experiments on CIFAR-10, CIFAR-100, ImageNet, and CIFAR-100LT (long-tailed) suggest that the new approach performs as well as or better than state-of-the-art methods.
main_review: ### Strengths

S1) This paper identifies and addresses a common issue in active learning, which is that selection criteria generally don't address class imbalance and decision boundary imbalance.

S2) Experiments were performed on multiple datasets, including a highly class-imbalanced dataset (CIFAR-100LT) which may be more reflective of real-world settings.

### Weaknesses and Issues

**W1) Need to clarify misleading "constant approximation guarantee"**

The paper claims to have a "constant approximation guarantee," which is misleading. This guarantee is only with respect to the proposed selection criteria $f(S)$, but there is no guarantee that a set $S$ which maximizes $f(S)$ is actually a good training set. To the best of my knowledge, the correlation between $f(S)$ and test accuracy is merely heuristic and empirical. This point needs to be made much clearer in the text to prevent readers from conflating a "constant approximation guarantee" for maximizing $f(S)$ and the (non-existent) guarantee for maximizing test accuracy.

In contrast, active learning methods based on influence functions (see W2 below), actually try to directly maximize test set accuracy.

**W2) Missing discussions and comparisons against other related works**

The paper is missing discussions and comparisons against about other relevant active learning techniques such as [Deep Bayesian Active Learning (Gal et al., 2017)](https://proceedings.mlr.press/v70/gal17a) and [Active Learning via Influence Functions (Xu and Kazantsev, 2019)](http://arxiv.org/abs/1905.13183). Note that DBAL can be considered as another "uncertainty" metric. However, active learning via influence functions does not seem to fall within the uncertainty vs. diversity framework that this submission describes. Therefore, I would be particularly interested in seeing a discussion and comparison between the proposed framework and active learning via influence functions.

**W3) How does the proposed framework address the limitation that "no single subset selection criterion achieves the best performance"?**

The authors write, "To address the first limitation, we develop a unified algorithm based on maximization of a submodular function, which can combine different selection objectives." The limitation that they refer to is "First, there is no single subset selection criterion that achieves the best performance on different classification datasets."

It is unclear to me how the proposed framework addresses this limitation. Putting the various selection objectives into a single selection criteria function $f$ does not magically mean that the combined criteria achieves the best performance on different classification datasets. The authors' claim seems very misleading.

**W4) Need better justification and discussion about $f_{triple}$**

It is unclear to me how $f_{triple}$ is practically different from $f_{diversity}$. Are there situations where the two are very different? Is there a theoretical justification for why including both metrics is better than including just one of the two? Could you show a scatter plot of the two metrics (e.g., sample many different sets $S$, then plot $f_{diversity}(S)$ on the x-axis and $f_{triple}(S)$ on the y-axis)?

Also, I'm not sure I fully understand what the "volume consumed by the embeddings of the triplet $\{i,j,k\}$" means. A more thorough discussion of this is warranted. How is $\mathcal{T}_{thresh}$ chosen? And why use a threshold on $t(i,j,k)$, instead of a proportional penalty on $t(i,j,k)$?

**W5) How to select hyperparameters parameters like $\lambda_i$, $\gamma$, $\mathcal{T}_{thresh}$, and $k$**

I would appreciate a discussion on how to select the hyperparameters mentioned throughout the paper. The values chosen seem rather arbitrary.

**W6) What about active learning for regression?**

The paper only describes active learning for classification problems. The authors should make this clearer from the start of the paper. Are any of the ideas proposed here generalizable to regression settings?

**W7) Clarity Issues - please address each point individually in your response**

- In the "Subset selection and model evaluation" paragraph under "Section 3: Problem Statement", it is unclear what edges are included in $E$. For example, is $E$ directed? Is $E$ fully-connected? Only after reading through the end of the paper did I understand $E$ to be the edge set of a $k$-degree nearest neighbor, where $k$ is a hyperparameter. This point should be made clearer.

- Why define the margin score as $m(x) = 1 - \left( P(Y=bb|x) - P(Y=sb|x) \right)$? Why not define it more simply as $m(x) = P(Y=bb|x) - P(Y=sb|x)$?

- What unary function did you use for $f_{diversity}$ in your experiments? Did you use the constant term?

- Equation (7) says $M = (G, \mathcal{I}_p)$, but then defines $\mathcal{I}_c$. Looks like a typo.

- The authors write that on ImageNet, "we found that 15% of all possible boundaries were covered." Help me interpret this statement. Is 15% surprising? Is this more or less than the authors expected?

- In equation (10), what is $M$? It seems like $M$ is used both as an integer (for the number of decision boundaries) and as a matroid. Please clarify.

- In the "Evaluation" subsection under "Section 6: Experiments," the authors write, "Note that, on this dataset, accuracies with 80% and 90% subsets exceed that with the full dataset." Which dataset is this referring to?

- In the Ablation study subsection, what are the standard deviations for the reported improvement percentages? Are these relative improvements, or absolute improvements? On which dataset(s) did the authors test the larger values of $k$?
summary_of_the_review: The active learning approach proposed by the paper builds incrementally on existing ideas of uncertainty and diversity sampling. They provide decent empirical evidence to suggest that their methods are at least as good as existing methods, and sometimes better. However, I hesitate to recommend this paper for acceptance as-is, due to misleading claims, incomplete discussions, and a number of clarity issues. Many of the design choices seemed arbitrary and require more thorough justification. I would be inclined to raise my score if the paper's current weaknesses and issues are properly addressed.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Most batch-mode active learning strategies involve maximizing a sub-modular score function of the value of each image to be labeled. This paper demonstrates that current methods fail to sample diverse classes or images near decision boundaries, arguably one of the most important regions to obtain label information. The paper proposes a technique for incorporating class-balance and boundary-balance constraints to the sub-modular optimization problem and performs experiments over several image data sets to show the value of class and boundary balancing.

main_review: AFTER REBUTTAL:

I thank the authors for their detailed rebuttal and for testing out some of the suggested ablations. However, in light of the number of ablations and some of the confusion regarding the motivation behind class and boundary balancing, I feel this paper may not yet be ripe and could do with another round to review the explored experiments and revise the intuition and justification behind the setup. Therefore I leave my score as is.

-------------------


I like the review of how different strategies are biased to miss class and boundary diversity, as well as the matroid constraints for incorporating them. However, I feel that the paper can be improved with additional ablation and analysis. Below are some suggestions.


- I found the histograms in Fig 3 and corresponding discussion confusing. It would be useful to revise the axis and give some more information as to how a reader can interpret the plot. I interpret the x-axis of the histogram as “boundaries covered by $n$ images”. So for example with CIFAR10, there are 12 decision boundaries that are covered by only 1 image, and 13 boundaries covered by 2 images. Is this correct?
- It seems there is extensive parameter tuning involved, particularly in selecting how much to weigh the different terms in the objective function. Parameter tuning in active learning is a fundamental challenge since we typically don't have the validation data to tune parameters at onset. Can you provide details to how much parameter tuning was involved and how your custom objective would work in practice?
- An alternative to the above point, in terms of delineating the value of parameter tuning would be to implement the class and decision boundary constraints with respect to existing active learning strategies. For example, $\lambda_1 = 1, \lambda_2 = \lambda_3 = 0$ would give us a fair comparison on the value of class and boundary balance and how it improves a well-known existing method like margin. 
- The improvement of the proposed method over baselines is attributed to the balancing constraints (e.g., comparing submod-bal vs submod). How well does the proposed method work in covering class and decision boundaries? For example, it may be useful to have a histogram of labeled class frequencies after each round of active learning for each method. Ideally, we expect the proposed method to select more balanced sets to label than baselines. We can do a similar analysis replicating Fig. 3 evaluating selections in each round with the decision boundary of a final classifier trained with 100% of the data as ground truth. These analyses can answer: how much does the current method improve over baselines in selecting class and boundary-balanced data, whether there is room for more improvement, and what is more important (class or boundary balance?)
- I am most interested to see what this looks like on CIFAR100-LT since this is where the proposed method shines the most and I expect class-balancing to be a key contributor. A good class balancing AL strategy can very much help imbalanced data collection practices and I encourage the authors to emphasize this value of their proposed method further. For example, another ablation could be to test on different imbalance factor for CIFAR100-LT and track the relative improvement of the proposed method over baselines as we vary the degree of imbalance.

summary_of_the_review: Overall the approach and results look interesting, but the limited experiments make it difficult to fully capture the value of the methods proposed. I would be happy to increase my score if the authors can further expand numerically on where the improvements are coming from.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper presents a new method for batch active learning in deep neural networks, which aims to progressively construct compact subsets from a training dataset that maximize accuracy of learned models. The authors propose to address this problem by optimizing a submodular set function, expressed as a weighted combination of uncertainty, diversity, and triplet objectives, under a set of balancing constraints on classes and decision boundaries. The resulting optimization problem is solved using a greedy algorithm. Experiments are conducted on CIFAR10, CIFAR100, ImageNet and CIFAR100-LT datasets, where the proposed approach outperforms all baselines, with larger improvements under a class-imbalanced setting (CIFAR100-LT).
main_review: ## Pros
- Formulation of the optimization problem is well motivated.
- The proposed algorithm is clearly described using rigorous equations.
- Proofs of important properties of the method (submodularity of objective functions) are provided in the appendix.

## Cons
- The motivation for the triplet clique objective (6) is unclear. The function appears to encourage diversity of subset $S$ as (5) has addressed, and no discussion (theoretical or empirical) is provided as to whether the advantage of including (6) can offset the additional computational complexity it introduces.
- Balancing constraints seem to play the most important role from the empirical results. This puts into question the importance of the first claimed contribution of the paper, namely the unified objective function of (2), as `submod` without balancing does not significantly outperform other baselines. However, no ablation experiments are included to study the importance of boundary-level balancing constraints in addition to class-level balancing.
- Theoretical analysis or ablation studies for important hyperparameters of the proposed method are also missing from the experiments. Some examples for these include the loss weights $\lambda_1, \lambda_2$ and $\lambda_3$; the choice of balancing hyperparameters $k_{1:L}$, $d_{1:M}$; the margin score threshold $\tau$.
- Lack of comparison to state-of-the-art active learning methods. While the paper compared to core-set selection, stronger baselines (e.g. [A-C]) were not included. In addition, comparisons in the paper are limited to classification datasets, but not for more label-intensive tasks such as semantic segmentation, which [B, C] has studied.
- Error bars for methods other than `submod-bal` were not reported. This makes it hard to determine the statistical significance of results when comparing two approaches.

## Minor comments
- Equation (9) seems redundant given the margin score has been defined in (4). I wonder if it makes more sense to instead define the boundary assignment function $b(x_i) = (bb(x_i), sb(x_i))$?

[A] Yoo, Donggeun, and In So Kweon. "Learning loss for active learning." *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*. 2019.

[B] Sinha, Samarth, Sayna Ebrahimi, and Trevor Darrell. "Variational adversarial active learning." *Proceedings of the IEEE/CVF International Conference on Computer Vision*. 2019.

[C] Zhang, Beichen, et al. "State-relabeling adversarial active learning." *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*. 2020.
summary_of_the_review: I appreciate the effort of authors towards a unified framework for sample selection in active learning. However, as detailed in the Cons section above, the importance of many elements of the proposed method are not adequately justified through theoretical or empirical results, and comparisons to prior work are lacking in number of baselines as well as range of tasks. I believe additional experiments/analysis addressing these concerns are needed to support the major claims of the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a new subset selection method with novel diversity objective and balancing constraints. The authors prove that the proposed sample selection criterion is a submodular function. Hence its greedy algorithm comes with approximation guarantees (Nemhauser et al., 1978). The experiments on popular image classification datasets show that the proposed method is slightly better than k-center (Sener & Savarese, 2018). 
main_review: Strengths:
1.	The paper is easy to read and understand.
2.	The proposed boundary balancing constraint is interesting.
3.	It is good to do experiments on large datasets.

Weaknesses:
1.	The authors claimed that “we develop a unified algorithm based on maximization of a submodular function, which can combine different selection objectives” in Introduction. However, I can’t see the necessary or benefit of using “submodular function and matroid intersection” in this paper, except that some prior works about submodular show the guarantee of approximation to the original dataset in the some feature/output space. The question is that the subset with optimal approximation of a dataset in some feature space doesn’t guarantee that it is the optimal for training neural networks. It is known that random selection can also perfectly approximate the geometry of original dataset (Chen et al 2012) as long as the subset is large enough. In addition, it is also unknown that such approximation guarantee of using submodular function is better or faster to reach than other approximation methods like herding, k-center (Sener & Savarese, 2018), k-medoids etc. 
2.	The authors admitted that “the difference between our method and k-center is marginal” in Discussion. The performance comparison also verified it. The performance improvement of the proposed method is mainly due to balancing constraints. More detailed ablation study on each individual balancing constraint should be given. Otherwise, it is unclear which constraint works. 
3.	The experiments lack the comparison to state-of-the-art subset selection methods.
4.	In the balancing constraints, the image number of each class is pre-defined and the underlying assumption is that the class number is known. Is this assumption realistic in the experimental setting (active learning)?

(Chen et al 2012) Super-Samples from Kernel Herding

summary_of_the_review: The proposed method achieves slight improvement over a classic method (k-center) by introducing new objective and constraints. The paper lacks deep analysis and solid experiments that explain why the new components are better. The contribution is somewhat incremental.
review_title: null

Meta-review: The paper studied an interesting yet challenging problem in active learning and provided an intuitive heuristic for selecting informative subset(s) of training examples. The reviewers generally find the paper well presented and highlight that the clarity of the exposition of the issues of existing query heuristics, especially for training deep models with class-imbalance data.

However, there are shared concerns among all reviewers in whether the existing experiments sufficiently justify the practical significance of the proposed heuristic (Reviewer 4ATq: Missing comparison against important baselines such as Gal et al 2017; Reviewer Cp2k: ablations of class and boundary balancing; Reviewer yngU: lack of comparison to SOTA and ablation for important hyperparameters; Reviewer oEcZ: lack comparison against SOTA). Reviewers also point out that the approximation guarantee is against an algorithm that is optimal wrt a somewhat ad-hoc objective, which makes the theoretical components of the paper not as significant. Given the above concerns, the paper does not appear to be ready for acceptance at the current stage.
Decision: Reject