Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study the problem of active learning in binary classification with the presence of agnostic noise in the streaming model. The adversary chooses a priori some corrupted distributions $D_t$ for each round $t$. The goal is to design an algorithm that outputs a hypothesis $h$ that minimizes the expected risk using a few labeled samples. In this work, they assume that they do not have any a priori information on corruption. The authors proceed by first analyzing the ERM for the passive learning for using it as a benchmark for the rest of the algorithms. The authors analyze two algorithms the RobustCAL (which has been analyzed extensively in previous works) and the CALruption which is the new algorithm they propose. For RobustCAL they show that as long as the corruption is bounded enough (the number of corruptions is less than $t/8$) in all the $t=1,2,4,...,2^k$ then the classic RobustCAL along with a regularization term will output a hypothesis that achieves expected risk competitive with the passive learning, i.e., the RobustCAL will not eliminate the optimal hypothesis in any elimination step. Moreover, they show that the regularization term is necessary by showing that without this term the best hypothesis will be eliminated. In order to remove the assumption on the bounded corruptions, the authors suggest a new algorithm CALruption, that overcomes this issue. However, this algorithm in the general case outputs a hypothesis $h$, such that $R(h)-R^* \leq \epsilon +O(\bar{C}/n)$ where RobustCAL gets $R(h)-R^* \leq \epsilon +O(R^* C/n)$, $\bar{C}$ is the number of corruptions in each epoch with some weights if the corruptions are large or small. Furthermore, if the corruptions are bounded enough in each epoch, then the difference of expected risk can be improved to $\epsilon +O(R^*C/n)$.

main_review: 
### Main Review
- Strengths of this work: 
1. Extends previous approaches on robust active learning to the agnostic streaming setting, when there is not a priori information on the corruption size.
2. Shows why known approaches fail in this setting.
3. Suggest a new approach for this setting that in several cases is optimal.

- Weaknesses:   
1. The algorithm is much more complicated and less intuitive than RobustCAL.
2. The difference between $R^* C/n$ and $C/n$ seems a large gap.


### Other comments: 
- The paper is well organized and well written except pages 6-7 (and Appendix) which are the main contributions, which also hold for the respective section in the appendix (section D). 
- I would suggest the authors rephrase/clean algorithm 2 to make it easier to parse.
- This section is notation-heavy and the authors fail to explain the use of each symbol. In order to understand several parts/notations, I needed to check the proofs in Appendix. 
- Appendix is full of typos and difficult to read. 
- I suggest the authors provide a full proof in the appendix and provide an intuition for the algorithm and the proof.
Some Typos: 
- In label complexity: $|H|^2$ should be $|H|$ because of $O$.
- Line 178: at least*
- 157: h should be $h^\ast$ and "and." 
-  Typos in Appendix (including not limited to): Lines: 532, 558-559, 562-563,566-567,570,575-576,624.
- Some inequalities need justification.

I suggest the authors improve the clarity of this work in the camera-ready version (and in the full version of this work). For instance, I cannot understand why in some lemma statements the authors prove inequalities instead of doing it in the proof, e.g., Lemma C1. 
limitations_and_societal_impact: This is a theoretical work and has no negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers active learning with an "oblivious adversarial model": before the start of learning, an adversarial chooses a series of distributions $P_t(Y\mid X)$ , and at time t the label $Y$ would be drawn from that distribution. The adversarial level is characterized by $C_{total}=\sum_t \sup_x |P_t(Y\mid X=x)-P(Y\mid X=x)|$ where $P(Y\mid X=x)$ is the distribution over which the error for the model is calculated. 

It first shows an error bound for passive learning with ERM. Then, it shows a slightly modified version of CAL (disagreement based active learning) could tolerate around $C_{total} <= n/8$ and achieve an error of $R^* + \epsilon + O(R^* C_{total}/n)$ where R* is the best error achievable without corruption and n is the number of unlabeled samples. Its label complexity is similar to that of the original CAL. 

To tolerate any level of adversarial, instead of shrinking the version space permanently, it proposes a new algorithm that queries examples with some carefully designed probabilities. It gives its label complexity bounds, and shows that (1) its label complexity matches standard CAL without corruption; (2) it can tolerate higher corruption ($C_{total}>n/8$) while the previous modified CAL cannot; (3) its label complexity is slightly worse when the adversarial corruption is not high (e.g. the mispecification case where the probability that the adversarial corrupts the label in each round is uniformly upper bounded).
main_review: This paper considers an interesting setting where the noise condition is harder than what existing active learning papers studied. Its results are new and nontrivial. I briefly went over its proofs and they look sound to me. However, this paper in its current shape is a bit premature to me, and I'm not sure if its quality is good enough for NeurIPS.

Main concerns:
- Clarity.
  - The main algorithm, Algorithm 2, is not very well explained. The high level explanations before Theorem 5.1 are nice, but it would be better if you can provide some explanation and *intuition* of detailed designs (if page limit is a problem, putting them in Appendix would still be helpful). For example:
    - how is the robust estimator constructed? What's the intuition behind the equation?
    - lines 9~13 in Algorithm 2 are quite hard to parse. Could you explain what these variables stand for? What are the rationale behind the chosen values? 
    - If there is no corruption or under the mispecification case, is there any connection between Algorithm 2 and existing active learning algorithms with importance reweighting like [Beygelzimer et al 2010, Huang et al 2015] in your reference?
  - There are a lot of notations. It would be clearer if you can have a list of notations, even just in Appendix.
- Setup & results
  - The characterization of corruption level $C_{total}$ looks quite loose. One extreme example is that this quantity can be large even if the adversarial only corrupts the labels on a zero-measure set. It would make more sense if this measure takes the distribution of P(X) into account.
  - This is a relatively new setting, it would help understand the hardness of the problem and optimality of the proposed methods if you could show some lower bounds (even just for passive learning).
  - This paper only considers *oblivious* adversary model where the adversary has to decide its corrupted distribution beforehand. This looks a bit weak. What's the main obstacle to work against that?

Minor issues:
- It might be worth citing [1] though it only works under the mispecification case for linear separators.
- It would be clearer if you could provide some simple examples to show how traditional active learning algorithm fails with adversarial corruption.
- Algorithm 2 has a worse label complexity than modified CAL under low corruption.
- Disagreement coefficients are often not a constant (for example it can be O(\sqrt{d}) for linear classifiers with log-concave distributions).

A technical question:
At a glance, the guarantee for the robust estimator (Lemma D.2) is quite similar to what one typically gets with naive importance sampling. Could you state why importance sampling does not work for your use case?

[1] Awasthi, Pranjal, Maria Florina Balcan, and Philip M. Long. "The power of localization for efficiently learning linear separators with noise." Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 2014.

limitations_and_societal_impact: See main review
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors consider robust active learning. They demonstrate that an existing algorithm Robust CAL can be tricked into permanently discarding the optimal hypothesis by large amounts of corruption early on during learning (followed by no corruption to keep overall levels low). The authors repair this flaw by modifying the algorithm to do a soft-elimination so that no hypothesis is permanently discarded. However, the cost is a higher unlabeled sample complexity, which also creates a weakness to increasing corruption.

main_review: This work improves our understanding of the impact of corruption in active learning. While intuitative, it provides machinery for understanding the importance of the timing of the corruption during the learning process. 

As pointed out by the authors, the proposed algorithm requires significantly more unlabeled samples. While it is often assumed that unlabeled data are cheap and/or easily obtained, this is not always the case. 

Overall the paper is well written and clear. The only real criticism I have is that the result is of middling impact. By improving our understanding of robust active learning, the authors make a step toward better learning algorithms, but do not create fundamentally new capabilities. Thus, the impact is not low, but neither is it high.


limitations_and_societal_impact: The authors address limitations of unlabeled sample complexity and other weak points of the proposed algorithm.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper discusses binary classification when the labels can be corrupted by noise in an active learning scenario. In this direction the authors show that in a benign corruption setting the, a known algorithm, which the authors call RobustCAL, can achieve pretty-much the same label complexity as in a non-corrupted setting. However, the algorithm may fail in general and the authors propose a variation of this algorithm in order to be able to deal with the general case. This latter algorithm, though it requires more labels compared to RobustCAL, nevertheless it does come with good theoretical properties. 

main_review: The paper discusses an interesting problem in an interesting framework. Active learning, as well as robustness guarantees are sought for in many situations for classification and the content of this paper lies at the intersection of these two fields.

I have not seen the proofs in detail. However, to me there are a few things that are a little bit unclear even at a higher level. For example, the authors cite 3 papers about RobustCAL, but it appears that the name comes from the most recent citation and it is a bit unclear if all the details are the same across all three references.

As another example, I would expect a little bit broader description of the results that are related to corrupted labels. For example, the first paper that comes to one's mind is "Learning From Noisy Examples", by Angluin and Laird with constant misclassification rate, and another one is Sloan's "Four types of noise in data for PAC learning" which discusses malicious misclassification. None of these two papers is cited and I believe they should -- even if they discuss results in the non-agnostic case. Then one can make the jump to the agnostic case and cite and compare related literature and finally discuss everything in the context of the paper where active learning is also taken into account. 

Another issue that the paper has is that the papers are not listed in alphabetical order and this makes it hard to find the paper one is looking for.

For the claim in lines 38-40, which is the appropriate reference?

Missing the reference (and a brief discussion) on the original CAL algorithm/paper in the related work section.

- line 152: is the upper bound by epsilon, an assumption of the misspecification model?
- Algorithm 1, line 7: the equality is perhaps set membership?
- Algorithm 1, line 12: what is $\hat{h}_{t+1}$?

I would also like to see more discussion of the proposed algorithm (CALruption) on the main text and get more explanations on the actual operations that take place in the various lines of the pseudocode. Similarly, I think the paper would also benefit if one could state simple versions of the bounds, in terms of label complexity. For example, the label complexity in line 244 (Corollary 5.1) seems quite daunting to someone who reads the paper for the first time.

Some typos:
- l 136: extend -> extended
- l 143: game -> label?
- l 157, equation: X -> x (lowercase in the subscript of the numerator)
- l 161: Is $\hat{R}_{[1, n]}$ defined somewhere?
- l 203: In the Section -> In Section
- l 220: hypothesis -> hypotheses (both occurrences on that line)

Overall, I think the paper should be above the acceptance threshold, but I would like to see some responses on the above.

============================================================

I am happy with the different points that have been raised in the reviews and the responses that we have received. Therefore, I am maintaining my recommendation for acceptance.
limitations_and_societal_impact: The authors could be more explicit with a paragraph dedicated for this purpose to explain the limitations of the algorithm. For example, while the statistical question is resolved in a nice way, nevertheless, the algorithm does not appear to be computationally efficient. So, this is one example of the limitations that could be discussed. Also, one can compare further the label complexity between RobustCAL and CALruption.
review_title: null

Meta-review: The paper studies active learning under label corruptions and presents a robust version of the classical CAL algorithm. All the reviewers agreed that the paper studies an interesting direction and presents good theoretical results. While the results in the paper do not present a complete picture of the problem setting, there is enough technical novelty to make the paper slightly above the bar for publication. The authors are encourage to carefully take into account the reviewers' comments when preparing the final version.
Decision: Accept (Poster)