Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper provides a framework which attempts to find a weighted subset of the unlabeled pool that matches the loss on all the points. This paper introduces a seminorm on the loss functions and proposes an optimization method to minimize this. Somewhat favorable results are shown for vision datasets.
main_review: Although the algorithm features favorable empirical results and a nice conceptual framework, I have some concerns about the details of the algorithm algorithm and evaluation.

How are \alpha, \beta, and \tau chosen? Are they optimized for each dataset? If so, this may be a major drawback of the proposed method.

This optimization seems to have many heuristics and approximations: the choice of norm for the Bayesian and non-Bayesian settings, the L2 regularization, "squaring all of the terms for the ease of optimization", the "de-biasing" step, and using only the neural network's last layer. It would be very helpful if the effect of these approximations could be bounded or quantified. I'm concerned about the scenario that heuristics were added to the algorithm until the algorithm worked well, rather than being theoretically motivated.

If only using the neural network's last layer, isn't the loss convex, and it'd be better to match the loss optimizer rather than the loss (which is indirect), at least in the non-Bayesian setting?

Why are the dataset for the Bayesian setting (Fashion MNIST, CIFAR 10, CIFAR 100) different from the non-Bayesian setting (MNIST, SVHN, CIFAR 10)? Is it possible that all methods could be run on the 5 datasets presented?
summary_of_the_review: Without the above concerns addressed, this paper could have major drawbacks. Thus, for the time being, I'm recommending rejection.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work formulated batch active learning as sparse approximation problem and provided bayesian & non-bayesian versions of their framework. Experimental results shows their effectiveness of reducing the acquisition time, especially when compare with other hybrid AL sampling strategies, such as BADGE.
main_review: Strengths: This work decompose the upper bound of the sparse approximation problem as bias and variance terms, which naturally provides the uncertainty and representativeness during AL processes. By transforming the sparse approximation problem to finite-dim optimization problem, and solve w to implement subset selection of AL. The idea is interesting and novel.

Weaknesses: my questions focused on the experimental part.

1) The quota of different experiments are inconsistent, i.e., in Figure 1, the quota on CIFAR10 dataset is 18000, while in Figure 2, the quota of CIFAR10 is 23000. The change of quota would influence the value of AUC score.
2) For the chosen of baseline, why not employ BatchBALD[1] instead of BALD? SABAL should compare with hybrid AL sampling strategies, BatchBALD would be more suitable for comparison.
3) From the experimental results, although SABAL reduce the acquisition time, the improvement of performance is marginal. However, there is no shortage of AL algorithms that perform better and run faster, e.g., WAAL [2]. WAAL achieved significant performance improvement, while the acquisition time cost is low (see Table 1 in [2]).

References:

[1] Kirsch A, Van Amersfoort J, Gal Y. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning[J]. Advances in neural information processing systems, 2019, 32: 7026-7037.

[2] Shui C, Zhou F, Gagné C, et al. Deep active learning: Unified and principled method for query and training[C]//International Conference on Artificial Intelligence and Statistics. PMLR, 2020: 1308-1318.
summary_of_the_review: This paper provides a novel perspective of combining uncertainty and representativeness criteria together in deep active learning. However, the performance gain compared with baseline models is marginal.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper formulate the batched active learning problem as a sparse approximation problem. The authors also provide algorithms to solve the sparse approximation problem. Empirical evaluations show the advantages of the proposed methods.
main_review: The re-formulation of the active learning problem into a sparse approximation problem is interesting (which I haven't seen elsewhere before). The empirical results also show advantages of the proposed method (under certain approximations) over existing ones. The paper is generally well-written. I summarize my concerns as follows.

1. Is it true that the authors implicitly assume that they are studying the problem in a realizable case where there is no labeling noise in the Y domain?
2. The sparse approximation problem aims to optimize over $w \in {\mathbb R}^{n_u}_{+}$. However, it seems to me that it's more like optimizing over $w \in \{0, 1\}^{n_u}$? Otherwise, Eq (9) doesn't really make sense to me, e.g., what does it really mean to have $w_j = 0.01$?
3. The proposed method focuses on the batched active learning setting, what would happen in the case of sequential labeling?
summary_of_the_review: Based on the main review above, I vote for a weak rejection of the current version.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes SABAL as a framework to formulate batch active learning as a sparse approximation problem. The paper considers the SABAL framework as a finite-dimensional optimization problem, efficiently solvable by the proposed greedy or proximal IHT algorithms. 

Numerical experiments demonstrate the strong performance of SABAL, comparable to the state-of-the-art with lower time complexity.

Since directly optimising the original objective function is intractable, SABAL proposes to optimise (minimise) the upper bound which is obtained by the triangle inequality including the (i) variance and (ii) approximation bias.

main_review: Strengths:
* The formulation of batch active learning as sparse approximation is interesting and seems novel.
* The paper considers two choices for the norm for Bayesian and non-Bayesian settings.


Weaknesses:
* The formulation between batch active learning and sparse approximation requires a series of approximations. 
* In short, there are multiple approximation techniques used in this paper while the empirical gain is minimal. Random approach performs extremely well for batch active learning task without relying on complex computation.
* Missing a key comparison with Batch BALD. Note that the performance of BALD with $b>1$ is different from BatchBALD with $b>1$ as showed in [1].

Comments/Questions:
* Since the original objective function is intractable. The paper proposes to minimize the upper bound. However, the approximation relies on the tightness of the upper bound. It is questionable about the gap in Eq. (7).

* Then the final approximation form is nonconvex sparsity constraint and discontinuous objective function. To solve this approximation, the paper utilizes two approximation algorithms including the greedy and the iterative hard thresholding to optimize the objective function.

* In Eq (11), the variance term (right handside) will tend to enforce $w_j=0$ as much as possible. The effect is similar in using L0 regularisation.
* where $\alpha$ in Eq. (15) comes from?


Suggestions:
* Ablation study with respect to the batch size b
* while the reviewer has seen the ablation study of trading-off uncertainty and representation (E.1), the reviewer thinks it may be useful to empirically study the performance w.r.t. different choice of $\alpha$.

Presentation:
* The paper is in general well written and easy to follow.

Reproducibility:
* The results appear to be reproducible. The code is included in the appendix.

[1] Kirsch, A., Van Amersfoort, J. and Gal, Y., 2019. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. Advances in neural information processing systems, 32, pp.7026-7037.


summary_of_the_review: Active learning is helpful to acquire labelled data for supervised learning. Formulating the batch active learning as sparse approximation problem is interesting.

However, the reviewer has three main concerns: (i) while the maths looks correct, there are a lot of approximations used in finding the solution. These approximations may affect the overall performance and hinder the applicability of the paper. (ii) the empirical performance is minimal comparing to the random baseline. (iii) missing the key comparison to Batch BALD [1].
review_title: null

Meta-review: This paper presents a batch active learning approach (where in each active learning round, instead of a single input, we wish to select several inputs to be labeled). The paper attempts to solve this problem by posing it as a sparse approximation problem and shows that their approach performs favorably as compared to some of the existing methods such as BALD and Bayesian Coresets for batch active learning.

While the reviewers appreciated the basic idea and the general framework, there were several concerns from the reviewers (as well as myself upon reading the manuscript). Firstly, the idea of batch active learning as a sparse subset selection problem is not new (Pinsler et al, 2019). While previous methods such as (Pinsler et al, 2019) have used ideas such as Coresets, this paper uses sparse optimization techniques such as Greedy and IHT. Moreover, there were concerns about experimental settings relying on various heuristics, and lack of a more extensive and thorough comparison with important baselines, such as BatchBALD and others, which the authors acknowledged.

The reviewers have read the authors' response and engaged in discussion but their assessment remained unchanged. Based on their assessment and my own reading of the manuscript, the paper does not seem to be ready for publication. The authors are advised to consider the points raised in the reviews which I hope will help strengthen the paper for a future submission.
Decision: Reject