Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose online selective classification and explore strategies with a goal to make the least number of mistakes and abstain the fewest number of times. Concretely, they explore the adversarial case and the stochastic case. They argue that the regret bounds in the ‘versioned uniform explorer’ (VUE) scheme in the adversarial case can be improved logarithmically in N in the stochastic setting by using the VUE-PROD scheme.
main_review: Pros of this work:
- The introduction and related work sections are well written and easy to understand. 
- The authors have described the main differences with other closely related work in a neat and concise manner.
- The authors provide strong theoretical bounds for the presented algorithms, VUE, VUE-PROD and MIXED-LOSS-PROD.


 Cons of this work:
- The experimental section in the main paper is very limited and has less details for reproducibility and is hard to understand.
- It seems that the error bars on the GAS dataset are very high for both the measures, excess mistakes and MMEA. It would be great to explain such large standard deviation error regions.

Minor typo:

L111. basis *of its history

Post Rebuttal Update: I will maintain my score of accepting this paper. I would encourage the authors to carefully go through the reviewers concerns and update their paper for the next version.
limitations_and_societal_impact: The authors have not discussed the limitations and societal impact of this work in as much detail.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper focuses on selective classification models in the online setting where the true label is revealed to the learner only when the abstention option is picked. Both adversarial and stochastic cases are studied in this paper, and algorithms are provided for these cases, respectively. 
main_review: Different from the existing paper [Cor+18], this paper is focused on the setting where the true label is revealed to the learner only when the abstention option is picked, which the authors have provided real-world scenarios. Different algorithms are proposed for adversarial and stochastic cases, and detailed regret analysis are also provided for them. This paper looks quite interesting to me. But I have a few questions below. I would really appreciate it if the authors could further clarify them.
- The goal is to design an online algorithm that doesn’t abstain more times than the best-in-hindsight error-free classifier f*. However, the regret bound from Theorem 4 and 7 has a linear dependence on T, i.e., the term pT if p is a constant. Normally we would hope to get a sublinear dependence on T for the purpose of convergence. Therefore, we need to have varying p. It would be more clear if the authors could explicitly provide the formula for p in the theorems.
- It would be great if the authors could provide more explanations about the implication of Lemma 1 for regret analysis, especially in the context of Algorithm 1. In this way, it's easier to understand the rationality of how Theorem 2 is derived.
- It looks like there is no Conclusion section at the end of this paper.

limitations_and_societal_impact: The limitations are discussed in Section 3.
This is primarily a theoretical paper. There is no negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This manuscript proposes a framework for selective classification in an online fashion. In particular, it proposes strategies that make few mistakes while not abstaining too many times. A tight regret analysis is well established and experiments on real datasets demonstrate the power of the approach. 
main_review: The framework appears to be novel and the proposed strategies are impressive, supported by a tight regret analysis.

The experiments on real datasets also support the usefulness of the framework. 

The paper is well written and is easy to follow. I personally enjoy reading this manuscript. 
limitations_and_societal_impact: Some practical guidelines on the choice of epsilon and p should be provided.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces a new setting for online classification with abstention and provide algorithms with provable guarantees for both the stochastic and adversarial setting. The bounds obtained are tight and very well exposed in the paper. The paper overall is of high quality, however, the setting studied makes multiple simplifying assumptions. Most importantly, the cost to abstention is constant, which may not be the case in real world settings. How changing this assumption affects the methods proposed is unclear. Empirical evidence serves mainly as a sanity check of the the theoretical guarantees. 
main_review: Originality: While online learning with abstention has been studied previously, the particulars of the observability and metrics has not been studied previously.  The algorithms provided combines different pieces from the online learning literature. The theoretical analysis is very detailed and novel on it is own. Prior work is compared to adequately. 

Quality: The technical details of the paper are clearly argued for and the appendix provides full proofs for al the claims made in the paper. Empirical results do not much to the paper beyond a sanity check of the theoretical results. 

Clarity: The paper is very well written and details are carefully explained. The proofs are non-trivial but are well explained to understand the technique. However, I will suggest reducing the amount of technical language in the text favor of some more basic explanations of the algorithms and what exactly do the theorems imply.

Significance: I think this paper makes a nice theoretical contribution to the study of online prediction with abstention. However, I am unsure of how their methods can be generalized to more practical scenarios. Mainly, what if there is a variable cost to abstention that depends on the context, the  setting for this is when the high capacity model may still make mistakes. Furthermore, the methods rely on the finite class assumption, I think an extension to VC classes is possible.

--------------

Post response: I have read the authors responses, although we uncovered that generalization to VC classes is harder than previously thought, the paper still remains interesting in it's own right
limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper considers an online learning setting in which the true label is revealed only when the algorithm abstains from making a prediction. Algorithms are proposed for several variants of this setting, and strong theoretical guarantees provide a trade-off between the number of mistakes and the number of abstentions. Some experiments demonstrate that these procedures can also be applied in practice. The work advances the theoretical understanding of selective classification, and as such could be of interest to many in the NeurIPS community.
Decision: Accept (Spotlight)