Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces a formalization of an online learning setup for labeling with human annotators and machine evaluation and gives an algorithm that simultaneously learns a model and decides when to request a label. Authors prove an upper bound on the algorithm’s label complexity and a matching lower bound for any algorithm adapted to this setup. 
main_review: General Assessment:  The paper is well written and easy to follow. The distinction between proper and improper settings is interesting and the lower bound result for proper setting is novel and relevant. 

Comments: 
- Empirical comparison to existing approaches in active learning is missing. Are there methods in active learning that can be adapted and compared to the proposed DPL-IWAL algorithm. 
- Is it possible to make proper dual-purpose labeling framework work in an online setting with some distributional/margin assumptions. It would be interesting to see how the lower bound can be avoided in a typical practical scenario?
 
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors propose a new learning problem that combines aspects of active learning and learning with abstention. They formalize the setting, provide an algorithm. They also prove an upper bound on the algorithm’s label complexity and a matching lower bound for any algorithm in this setting. Experiments are presented, too.
main_review: In general, I like the setting introduced in the paper, which is practically motivated and nicely combines abstention with active learning. I would have appreciated a better discussion of the consequences of this combination, however, especially on an intuitive level. At first, it looks as if the learner is supposed to find a compromise, but upon closer look, that does not necessarily seem to be the case. From an active learning point of view, it makes sense to query those instances on which the uncertainty is high (except in the case pf pure noise, as used by the authors in their proofs, because nothing can be learned from it), but for the same instances it is reasonable to abstain. So where is the problem, and if the learner cannot achieve the learning rate of the standard (supervised, active) agent, what is its disadvantage? Is it because of the slightly different evaluation? 

Upon closer inspection, I was also puzzled by some technical details of the setting. For example, why is a complete request function R_t needed for every t if this function is only applied to a single instance x_t? What the learner needs is a rule that decides whether or not x_t is queried, given the history so far. Why should one consider the conditional accuracy given r(x)=0 and not the overall accuracy, and isn't is a problem that the request function may change from one time point to the other? If eta is the request rate and e the conditional probability of a correct prediction, then the overall accuracy is eta*1 + (1-eta)*e, so maximizing the overall accuracy is equivalent to maximizing e.  Moreover, I was puzzled by the assumption of a finite time horizon T. Is this an online setting or not? Are new examples still queried after T, using r_T, or does querying stop at that time? If it continues, there would not be a need for the finite time horizon. If it stops, that would be a bit strange from a practical point of view. 

The paper is quite dense and not always easy to follow, especially since many things are moved to the appendix -- a bit too much in my opinion. For example, I'd have appreciated to see at least a sketch of the proofs in the main paper. They seem to be technically sound, but it's of course hard to check 10 pages of proofs in detail. 

The title of the paper is quite unspecific and in my opinion not well chosen.

limitations_and_societal_impact: adequately addressed
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Summary: This paper sets and explores relations between learning and labeling. The article develops a new method requesting labeling combining abstention and active learning. The authors develop a new method and detail their corresponding algorithm DPL-IWAL. They also provide asymptotic statistical guarantees concerning their approach to show the efficacy of their approach (lower and upper bounds).
main_review: Significance: The results are interesting and motivated. The novelty of the so-called dual purpose learning is perhaps the paper's biggest strength and applications to real-world scenario seem natural and well justified by the ablation study depicted in Section 6 of the article. The paper seems relevant to NeurIPS.

Clarity: I applause the author for the well-written article. Even though, Section 5 and 6 are harder to digest than the rest of the article. 
Minor typo: l. 203 "is contains"

Questions/concerns: 
1. DP-IWAL requires several hyper parameters and their selection seems obscure. How to set these parameters as the approach is online?
2. I am suprised that the cardinality of the label set $\mathcal{Y}$ does not appear in the upperbounds while it seems natural that the larger the label set, the more labels request are needed. How come the approach remains unchanged between binary classification and extreme classification?

limitations_and_societal_impact: N/A
review_title: null

Meta-review: This work formally proposes a novel learning  setup, which, on a high level can be viewed as a combination of active learning and learning with abstentions. The framework works with two function classes, a function class R, that contains regions of where labels should be requested and a (standard) hypothesis class of classifiers H. The goal of the earning is set to minimize the classification loss in the regions where labels are not requested, that is, minimize classification loss conditioned on r=0 (in the regions where r=1, labels are assumed to be always requested, so the classifier does not need to get labels correct). To make this setup non trivial, the the region, where r=1 is budgeted to probability weight rho. 

This paper proposes and analyzes this setup. The submission contains upper and lower bound on the query complexity and this is compared with standard active learning. Additionally, the authors provide some experimental evaluation on an adaptation of IWAL to their setup.

This overall appears to be a solid and rounded piece of work. The reviewers have critized a lack of proper motivation as well as clarity issues in the presentation. More intuitive explanation and guidance to the readers could have been given. I agree with the reviewers on these aspects, and would therefore rate this work as borderline, with a storng tendency to accept.
Decision: Accept (Poster)