Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies the label solicitation strategy in active learning. In particular, it focuses on the expected loss reduction (ELR) strategy, analyzes its problem, and modifies the original ELR method to make sure the active learner converges to the optimal classifier along learning iterations. The paper provides theoretical guarantees on the new method’s convergence. In the experiment, the proposed method is evaluated on synthetic data and UCI data. The improvement margin over the existing method is very limited.
 
Strong point:
1. The paper’s finding on the existing ELR method is interesting and novel.
2. The theoretical analysis of the convergence of the proposed method seems to be sound.
 
Weak point:
1. The experiment is conducted on low-dimensional data and the proposed method’s performance is not very competitive.
2. The notation in this paper can be confusing to readers, especially the use of (*). Star usually means the “optimal”.
3. The main paper does not have an algorithm.
4. There is no validation in experiments for the theory. In the synthetic experiment, it should be possible to simulate a case with ground truth optimal classifier and verify whether the proposed method actually converges to the optimal.
 
My major concern is the practical impact of the proposed method. Therefore, I recommend a weak reject for this paper (5).
 
Additional questions and suggestions:
 
1. I think the paper would be improved if there is a discussion on how the proposed method can be extended to deal with high-dimensional data and/or using deep learning models.

2. It seems to me the proposed weighted method is not the only way to guarantee convergence. But I am not sure about that. It would be nice to have some discussion about that.

3. The one-step-look-ahead strategy involving expectation model change or expected loss reduction usually suffers from the large class space for computing the expectation. The experiments are mostly conducted in a small class space. It would also be good to have a discussion about the complexity in terms of class space.

4. MES usually suffers a lot from noise (experiments in the appendix also show that). ELR methods are usually more robust to noise. I was wondering whether different noise level has been tried and how the proposed method compare with ELR on that. A similar question is also, for certain data there is a larger gap between the proposed method and ELR (in appendix). What would be the reason?   

5. The visual presentation can be improved for the paper, as well as the explanations. In figure 1’s explanation, I got very confused by the “side”. What does that mean?

6. The results should be shown with error bars if experiments are conducted multiple times.
 
================
Update after rebuttal:

I increased the score to 6 and appreciated the revision of the paper. The readability is improved. However, I also have different opinions with the authors in terms of how empirical evaluation of algorithms should be regarded in active learning research. So I would further encourage the authors to apply their method on high-dimensional large scale data, even it may take a lot of computing resources or require actual sample acquisition. 

I agree that the goal of active learning is to reduce the burden of labeling data. But it does not conflict with the requirement of dealing with high-dimensional (feature space) data. Also, I see a lot of active learning works focusing on theoretical analysis but cannot be easily put into real-world applications, which actually undermines the significance of the theory to some extent. In the real world, a lot of assumptions would be violated. As the authors also mentioned that, it is "expected" that different feature space and data quality affects the performance. Therefore, I think the theory does not spare us from justifying our methods in practice. 

Last but not least, actual sample acquisition is not unrealistic if given real-world problems. So I encourage the authors to further demonstrate the nice properties of the proposed algorithms in more realistic settings in the future.
review_title: Official Blind Review #2

final_score: rating: 7: Good paper, accept
review_content: This paper addresses the active learning paradigm in which the learner queries an oracle to obtain the class label of some inputs. Depending on the querying strategy, the learner can improve its classification model more or less efficiently. 

Among other possibilities, the authors focus on a class of methods known as Expected Loss Reduction, which is optimal in one-step-ahead risk minimization. However, the authors shed light on the fact that the long-term effect of this strategy do not necessarily allow to reach an optimal classifier. They thus introduce an alternative approach that achieves this goal by focusing on loss uncertainty.

More precisely, the authors introduce the Mean Objective Cost of Uncertainty (MOCU) that captures the expected difference between the error of Bayesian optimal classifier (BOC) and the expectation (against the parameter theta posterior) of the error of the theta-best classifier. An active learning strategy can devised by looking for a new input that (roughly speaking) will cause the largest MOCU drop.

Because the strategy consists in selecting inputs that maximizes MOCU drop, MOCU will decrease as new class labels are revealed but this does not imply that MOCU will reach its minimum (zero). To achieve long run convergence of MOCU to zero (and thus get obtain the optimal classifier), the authors propose a so-called weighted strategy that solve this issue. 

Finally, the authors provide fair numerical experiments on both synthetic and real datasets. The results indicates that the proposed strategy seems to provide good results in a wider range of situations as compared to SOTA.


Major Remarks : 

Although the authors provide some proof that the weight function can solve the long-run convergence issue, I wish they would provide intuitions as to why their particular choice can choose inputs that will be beneficial in this regard. The chosen weight function is going in the opposite direction of MOCU. Its effects are thus hard to interpret although it is instrumental to obtain a concave functions for the proofs.

The major drawback of the paper is that the scope of the proofs is very limited. Can the authors give insights as to what would remain valid in more realistic situations in which one has class imbalance, non-uniform utility (more general loss than 0-1), continuous parameter space ? The proof (unless I am mistaken) also do not account for approximation errors incurred by replacing expectation with empirical versions. 
A few comments are provided in the appendices concerning multi-class problems.
I, however, reckon that the numerical experiments are reassuring 

An algorithm is provided in the appendix but some comment on complexity as compared to prior arts in the main text would be appreciated.

Minor remark :

I am bewildered by this statement : "Converging to the true model is unnecessary and inefficient for classification". Should this be understood as the myopic strategies standpoint ?




review_title: A fairly good submission

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
Summary:

This paper provides an interesting algorithm to address the previous Bayesian active learning query strategy in (binary) classification. By the simple modification, the algorithm can overcome the drawbacks of ELR in the convergence to the optimal classifier parameterized by $\theta_r$. In experiments, the proposed algorithm can achieve the advantages of ELR and BALD simultaneously. 

Reasons for score:
Overall, I vote for the marginally above the acceptance threshold. The proposed methodology is impressive and well-motivated. However, there are some lacks in addressing the problem of ELR in a qualitative manner. The assumptions of theorems look strong. I feel that there can be room to be improved in this paper. 

Pros:
1. This paper was well motivated by the drawbacks of ELR and insightful comparison of BALD and ELR. In Bayesian approaches, these issues can be interesting and valuable.
2. The proposed algorithm is simple and addresses the problem caused by only mitigating the mean difference. The proposed algorithm can diminish the mean difference and ensure that $M^w ( \pi^*(\theta) )$ converges to 0.   
3. The proposed algorithm can dominate the random and ELR. Also, the prior can be used to provide better results. 

Cons:
1. The problem of ELR is not verified thoroughly. The stuck in the convergence of ELR can be due to the lack of considering the long term effects. However, the detail of this phenomenon is not verified in a more detailed manner. Can you show the details of what happened in the ELR active learning? At least, I want to see the values of $U$ and $M$ when the ELR is used.  
2. The proofs assume that the supports of $\pi(\theta)$ and $x$ are finite, respectively, and prior is limited to the discrete-type probability measure. These assumptions can be a good starting point. However, it is better to provide any clue that we can extend this result to more general settings.  
3. The counter-example of the proposed algorithm for multi-class in the Appendix shows this paper's prematurity in multi-class problems, and there are no details to address this problem. If you can provide some clues to address the multi-class problem, it is very helpful.  

Minor Comments:

1. It is not easy to follow the proofs in Section 3.1. The authors claim that the lower bound of OBC error will be canceled in the (5). The equations after (5) can imply this cancelation. However, there is no direct wording to conclude this cancelation.
2. In the equation of $\sum_y p^*(y | x) \pi^*( \theta | x, y) = \pi^*( \theta )$, $\pi^* ( \theta ) = \pi^*(\theta | x),$ it is better to clarify that $\pi^*$ is not affected by $x$.  
3. In the proofs of theorem 1,  the notation of $X_A (w)$ is not consistent with the previous notation of  $X_A$.  
4. The infinite querying for a fixed $x$ cannot be realistic in some cases. Therefore, the proof should be extended for the case that the support of $x$ is an open subset of $\mathbb{R}^p$ where $p$ is the dimension of $x.$ 


review_title: Review for the paper  

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors of this paper introduced a new acquisition function of active learning for optimal Bayesian classifier. The new query strategy is based on mean objective cost of uncertainty, defined as the expected difference between losses of the optimal Bayesian classifier and the optimal classifier.

I think this paper can benefit from revisions to improve clarity. Unfortunately, in the current state of writing, I found it very difficult to understand what this approach is doing exactly. The lack of clarity makes it hard to appreciate the interestingness of the proposed approach. In the following, I will list some possible improvements and my confusions.

1, In the abstract, please rewrite the sentence "To improve convergence ... classification error." This sentence is probably the most important summary of this work, but it's so long and dense that it's very difficult to parse. I believe people read abstract to get a general idea of what this paper is, not a dense summary of what the technical details are. 

2, The introduction should be called related work. Especially in 2nd-3rd paragraph, the authors tried to pack all competing algorithms in and explain why they don't work well. It is too detailed, I think. I expect more high-level descriptions of why this problem is important, where the field is now, or why the authors think this is an important problem to solve rather than, e.g., solving active learning for regression. 

3, The authors have a tendency of defining a symbol or an abbreviation, and expect the readers to register them in their memory. It would help the clarity significantly if the authors could just repeat in English what \pi (or \phi or C_\theta , M, U etc) is again when they are mentioned. 

4, It's not clear to me why the entire introduction and definition of MOCU is under section 3.1 Analysis of ELR Methods. Perhaps section 3.1 needs to be segmented into more subsections.

5, I'd recommend that the authors leave the most important theorem in the main paper and move all the less important lemmas and proofs to appendix. Then, the authors can have more space explaining the intuitions behind the proofs and the newly designed weighted MOCU. It is nice to see the convergence analysis, but it also makes me wonder how useful it really is. The theorem is saying, as we get infinite samples, we get the optimal classifier, under a bunch of conditions. It's nice to have, but it almost feels like every algorithm that can loop through all possible inputs can do that. What about the convergence rate that we care more about? Or how many active learning iteration is needed to achieve a certain performance.

6, While it is unclear how useful the theoretical guarantees are, it is also unclear if the empirical results should enough evidence. Only toy datasets were examined, and the performance of the proposed approach is quite similar to other competitors.
review_title: Difficult to read

Meta-review: The paper proposed weighted-MOCU, a novel objective-oriented data acquisition criterion for active learning. The propositions are well-motivated, and all reviewers find the analysis of the drawbacks of several popular myopic strategies (e.g. ELR tends to stuck in local optima; BALD tends to be overly explorative)) interesting and insightful. Reviews also appreciate the novelty of the proposed weighted strategy for addressing the convergence issue of MOCU-based approaches. Overall I share the same opinions and believe the paper offers useful insights for the active learning community.

In the meantime, there were shared concerns among several reviewers in the readability (structure and intuition), lack of empirical results on more realistic active learning tasks, and limited discussion on the modeling assumptions. Although the rebuttal revision does improve upon many of these points, the authors are strongly encouraged to take into account the reviews, in particular, to further strengthen the empirical analysis and discussions, when preparing a revision.

Decision: Accept (Poster)