Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses on stream-based (online) active learning for training classifiers in the binary classification setting. In particular, the authors propose a strategy, the so-called ALPS*, that trains classifiers by optimizing a surrogate loss over both the labeled instances and sequentially predicted data points by the learner. Theoretical guarantees on label complexity and error of the returned model are provided, and are shown to be competitive with the existing bounds. A set of experiments are conducted on datasets using multi-layer perceptrons as classification models, where the performance of ALPS is illustrated to have good performance with small labeling cost.


*Actively Learning over Pseudo-labels for Surrogate losses
main_review: -This work uses some existing techniques such as importance weighting, margin based functions in their building of final algorithm. The intuition is provided to understand the role of each component, for instance, how importance weighting helps with reducing the noise in hypothetical labels through requester functions. It is also mentioned by the authors in the paper that the proposed method is an extension of [1] to surrogate loss functions. With differences identified, the final methodology is sufficiently original in my assessment.

-The theoretical results on label complexity as well as the excessive risk of returned hypothesis (over the risk of best one in the hypothesis class) are competitive, although one may argue with certain assumptions at times such as access to a large unlabeled data pool (as in, once it is the case, there already exist several competitive pool-based methods over the online approaches, which makes prediction on the pool and measure disagreement among all pool examples). Overall, together with its empirical performance, the contributions seem adequately significant.

-The paper is well written and clear.

-My main argument would be the experiments. Namely,\
--I find the experimental setting limited. That is, if the focus is active learning hence reducing the number of label requests, then I believe a better comparison would be where each model is restricted to the same labeling budget throughout the entire stream. For instance, the query probability in the IWAL approach can be linearly scaled with a constant such that it queries the same amount of labels with ALPS by the time n rounds end, then illustrating the performance of methods over the rounds would be very informative. Often times, performance may change only a little after a certain amount of requests, hence it could help to see how they compare when they are restricted to limited amount of queries. As a note, I think passive learning in active learning literature refers to _random sampling_ than querying all labels (in this paper, it would correspond to $p_n$ being fixed at each round where $Q_n\sim Ber(p_n)$) throughout the stream, similar to label efficient prediction in online learning. As trivial as it may sound, the passive learning is shown to be very robust in the existence of noise studied in the paper. I recommend conducting experiments in which proposed approach is compared to the passive learning baseline in terms of its robustness.\
--The model space could be extended further than multi layer perceptrons.\
--There are other approaches that can be adapted/designed-for online setting [2,3] that uses disagreement among the classifiers (through measures like entropy). It would have been informative to see how ALPS performs compared to those approaches that are generally good.



[1] S. Dasgupta, D. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. In Proceedings of NeurIPS, pages 353—360, 2008\
[2] Ido Dagan and Sean P. Engelson. Committee-based sampling for training probabilistic classifiers. In Machine Learning Proceedings 1995, pages 150–157. Elsevier, 1995\
[3] Burr Settles. Active learning literature survey. Technical report, University of Wisconsin-Madison Department of Computer Sciences, 2009.
limitations_and_societal_impact: No discussion of societal impact, limitations on the theoretical assumptions have been addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose an active learning algorithm in the streaming setting for binary classification tasks. The algorithm leverages weak labels to minimize the number of label requests and trains a model to optimize a surrogate loss on a resulting set of labeled and weak-labeled points. The paper contains a number of theoretical results and supporting empirical results. Overall, its a very strong paper.
main_review: Pros of this paper:
- Has theoretical guarantees in addition to good empirical performance. Theoretical guarantees hold in the agnostic case where the true labeling function is not realizable.
- Furthermore, theoretical guarantees have generalization complexity and LABEL complexity
- Has good discussion on existing work
- Aside from its length, the introduction is very, very good. It is well-written, explains detriments in previous theoretical results in active learning, and clearly qualifies what setting it is tackling and how its solution is effective.
- Uses a very large assortment of real-world datasets
- Notations are good; the definition of consistency matches the usual definition
- The explanation for ALPS naturally develops itself, making it easier to follow along.
- Theoretical findings have bounds that match proven lower bounds up to log terms, showing near optimality.

Cons of the paper/questions:
- Models used are neural networks, but they are not deep networks (they are MLPs). 
- Will the techniques work for DNNs? If yes, how and what needs to change? Will be good to add some intuition for practitioners particularly if this needs to be used in a batch setting
- Introduction is a bit lengthy; perhaps it could be broken down into more sections	
- Link in Algorithm 1 (superscript 2) is broken; doesn't tab to footnote
- Alg 1 notation for h_y could be refined to show that h_{-1} and h_{1} are both being trained as mentioned in lines 164-173
- ALPS depends on the existence of consistent hypotheses on the relevant subsets of the data, which might not always be the case.
- Line 203: Is the notation used for list?

Summary:
Largely, I think this paper is very well written in that it develops the delivery of its results very well in the introduction and that it explains the workings of the algorithm in a logical order. They provide an astounding amount of experiments/datasets. Hence, I would recommend that this paper be accepted for these reasons, on top of the fact that it provides the empirical edge to other similar AL works for online binary classification. 
limitations_and_societal_impact: The authors state their work does not have any negative societal impact. The limitations discussed are mainly in the theory. I think another point worth discussing is how this approach can be used in a batch setting and for DNNs.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of online active learning for classification. In order to learn a classification algorithm, the paper proposes to employ surrogate loss function. The error of the proposed method is analyzed and some empirical results are presented.
main_review: The paper focuses on a problem that has been studied extensively. However, I think the contribution of this work relevant to prior works is not clear. Firstly, the authors does not explain that whether considering surrogate loss function results in obtaining tighter bound for error or not. In fact, the paper makes two additional assumptions compared to existing algorithms such as DHM (as it is called in the paper). Thus, it is expected that under these two assumptions  a tighter regret can be obtained. Otherwise, the error bound of the proposed algorithm is not tighter than existing works under two additional assumptions. This means that the paper does not make a significant contribution compared with existing works. Therefore, more discussion on error bounds and comparison with error bounds of other algorithms is required. Also there are two minor comments. 1- It seems that the proposed algorithm needs to store previously observed data samples while one of the reasons that online learning algorithms may be used is that data cannot be stored in batch. Thus, the proposed algorithm cannot be leveraged in these cases. Hence, this can be account as a limitation of the proposed algorithm. 2- In the theorem 1, it is stated that the inequality holds with probability at least $1-\delta$. However, there is not any $\delta$ in the inequality. It is highly recommended presenting the upper bound of error in theorem 1 using some terms which include $\delta$.

==============Review Update===============

Thanks the authors for the rebuttal. The authors' responses addressed most of my concerns. I think revisions that authors want to make will improve the paper. I am happy to increase my score. 
limitations_and_societal_impact: The authors discuss some of limitations in their work. Also they can add that their proposed algorithm needs storing observed data samples to make decision.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents Actively Learning over Pseudo-Labels for Surrogate Losses (ALPS), an active learning algorithm for binary classification with surrogate losses in the streaming setting. The main idea is to generate pseudo-labels for points whose labels are not requested and train on the union of data points with ground-truth labels and those with pseudo-labels. Since the pseudo-labels may not be accurate, the authors propose requestor functions that have a final say in whether a pseudo-label is used, and in effect, enable control over the noise generated by erroneous pseudo-labeling. Under an assumption involving the requestor function class, the authors prove bounds on the generalization error and label complexity of ALPS that are roughly on the same order of prior work (e.g., IWAL). 
main_review: Strengths

- The paper is generally very well-written and organized, with a clear exposition.

- Good coverage of related work (Sec. 1) and comparison of the proposed method to prior approaches. I also appreciate the discussion concerning the reduction of ALPS to DHM under certain conditions (Lines 107-113), which to me highlights the generality of the approach.

- I found the ideas of requestor functions and the definition of the version space as a function of both the requestor function and hypothesis class to be interesting and novel. The authors were also forthright about the relation of requestor functions to similar ideas like abstention functions from prior work.

- At a high level, the theoretical analysis of the generalization error and label complexity seems sound to me. I also think the relaxed assumption (Assumption 2) is relatively mild in the context of, for example, deep learning due to the high-confidence predictions that are typically produced.

- The authors present compelling empirical evaluations on a wide variety of data sets and compare to IWAL and instantiations of a margin-based algorithm. 


Weaknesses
	
- Relation to heuristic approaches: given that the primary appeal of the algorithm seems to be its practical effectiveness compared to prior work, e.g., IWAL (which has roughly the same guarantees), can anything be said about the performance of ALPS relative to SOTA active learning approaches like BADGE (which is actually cited in the paper as [1])? Although experimental comparisons would be best (the code for BADGE is publicly available [1]), even a qualitative discussion would be insightful.

- The method seems to work only for binary classification tasks. Can it be extended to multi-class classification?

- This is mostly a stylistic concern, but the introduction is quite long and the full extent of the contributions of the paper are not made clear until (roughly) page 3. I wonder whether partitioning the introduction section into two sections (intro and related work) or adding at least one subsection in the introduction for related work would improve the exposition.


[1] https://github.com/JordanAsh/badge 
limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper proposes a fresh approach to active learning with non zero-one losses. The proposed algorithm has theoretical guarantees that are competitive with existing works, while also performing in practice better than existing practical techniques, in a large set of experiments. This double advantage is of significant value to the advancement of the field. Moreover, the approach includes fresh ideas that could open up new avenues of investigation. Some reviewers have suggested additional experiments. We encourage the authors to add those to their final version.

Decision: Accept (Spotlight)