Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: Paper proposes an active learning algorithm in which labels are not acquired when the model chooses to abstain from predicting.
strengths_and_weaknesses: [note confidence score of 1 (@authors + @AC). this is largely outside my comfort zone with many proofs, of which I did not study in details. I would recommend discarding my opinion.]

I think lines 35-38 already starts this paper off on the wrong foot. The objective of active learning is to the learn the decision boundary with minimal labels; what the model does with points close to the decision boundary or with high uncertainty once this is learnt could be considered another problem. If the model can the learn the decision boundary with high accuracy given more queries around the decision boundary then this is justified.

Strengths
- The introduction makes clear what the paper is trying to achieve.

Weaknesses
- The paper is not easy to read.
- Scenario proposed does not reasonable.
- No experimental results whatsoever.
- Lots of propositions and theorems are stated in the paper, but all the proofs in the appendix. I have but skimmed these. 

Originality:
Certainly seems new, but a more directed related work would be appreciated.

Quality:
I find the theoretical exposition somewhat lacking in places-- e.g. for proposition 3 and the statement follows of the algorithms superiority over any uncertainty-based AL method. No experimental results.

Clarity:
Neither well written nor well organised. Language is imprecise and unclear. Parts of the paper make strong statements without backing.

Significance:
Difficult to assess the impact of the method. The impact of the paper however will be small, given the problems above.
questions: N/A
limitations: N/A
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes an active learning algorithm that can avoid sampling from regions of the input space with high label noise. The algorithm satisfies two important properties: 1) it achieves exponential improvements compared to passive learning with respect to an evaluation metric that penalizes abstentions (Chow’s excess error); and 2) the algorithm is computationally tractable for finite pseudo dimension function classes.

strengths_and_weaknesses: Strengths:

- The paper employs in a creative way techniques from contextual bandit literature to extend the idea of Puchkin et al and propose a computationally tractable algorithm. Moreover, the result is particularly remarkable since it does not require a condition constraining the amount of label noise, but rather captures it in the bound.

- The analysis for deriving the results is non-trivial and some of the connections to quantities from the contextual bandit literature (e.g. eluder dimension, disagreement coefficient) may be of independent interest for the active learning community.

- The paper contains several results that help to position the proposed algorithm in the broader active learning literature. For instance, the analysis of Section 3 confirms that the algorithm is minimax optimal (albeit not substantially better than passive learning) with respect to the standard excess risk.

Weaknesses:

- While the paper is generally easy to follow, certain details regarding the algorithm or the analysis could be discussed in more detail in the main text (see the Questions section)

- Minor remarks: There are a few typos in the paper (e.g. lines 259, 266, 274 etc). Also the pseudocode of Algorithm 1 can be made a bit more precise and easier to follow (perhaps add a notation for the labeled set; Q_t, x_t, y_t are not defined when they appears first in step 4; unspecified how $\hat{f}_1$ is selected etc).

questions: - How does the analysis of Algorithm 1 change if we assume a finite unlabeled set? Can the bound of Theorem 4 be changed to factor in the size of the unlabeled set?

- Steps 5-6 of Algorithm 1 approximate the lcb/ucb over the set of functions $F_m$. For what function classes $F$ is this step tractable? How can the approximation error of the lcb/ucb influence the result of Theorem 4? For what function classes is the approximation of the lcb/ucb “reasonable”?

- Algorithm 1 enjoys strong guarantees at arbitrary noise levels. This is captured in the bounds via $\gamma$ which needs to be chosen as a function of the noise level (indeed this is explicit in the proof of Theorem 6) and $\theta$ (which captures the disagreement compared to $f^\star$ at a fixed level $\gamma$). How do $\theta$ and the bound on sample complexity change when $\gamma$ is chosen inappropriately in Theorem 6, without knowledge of the noise level?

- Can the noise-seeking noise condition be relaxed for Proposition 3? The negative result for uncertainty-based AL is similar in spirit to the one in “On the relationship between data efficiency and error for uncertainty sampling” Mussman & Liang, 2018. While the analysis here is significantly different, the result in Mussman et al only requires non-vanishing Bayes error to reveal the failure of uncertainty sampling.

- Minor remark: “Noise-seeking Massart/Tsybakov noise” can be a bit confusing. Perhaps something like “Random flip-allowing Massart noise” could make it easier to grasp (although it’s a bit of a mouthful)?

limitations: The paper generally addresses some of the poignant limitations of the analysis (e.g. focus on finite pseudo dimensions function classes, realizable vs agnostic case etc). See the Questions section for other limitations that could also be discussed in the paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the pool-based active learning problem. The main contribution is to propose a computationally efficient algorithm to train a rejection model. Under the realizable case, the model enjoys $\epsilon$ chow's excess risk with $\widetilde{O}(\mathrm{polylog}(1/\epsilon))$ label complexity. The guarantee is achieved without any low noise assumption commonly used to achieve the exponential savings label complexity in literature. Although a similar rate (for learning with abstentions) has already appeared in the literature, the proposed method is more efficient (or practical) than the previous one. Besides the main result, the authors also show that (a slight modification of) the proposed method enjoys minimax optimal label complexity for the standard excess risk with the low noise assumption. Furthermore, this paper has shown a constant label complexity in a special case (with a finite hypothesis set) and presented the guarantees with model misspecification.
strengths_and_weaknesses: ### Strength:
Overall, I think this is a nice paper with fruitful results. Specifically, the strengths of this paper are listed as follows,
+ novelty& significance: although the algorithm framework shares a similar spirit as the previous work [Krishnamurthy et al. 2017] in standard active learning with abstention, the new criterion for label querying is interesting to me. A similar rate for active learning with abstention has been achieved by [Puchkin and Zhivotovskiy, 2021], but a computationally efficient algorithm is always what we desire. 

+ clarity: this paper is well written and clearly structured for the most part. Although there are fruitful results regarding Chow's excess risk and the standard excess risk (under different conditions), the authors have clearly organized them to make the results easy to follow.

### Weakness:
In general, I like the results of the paper, but I have still some reservations about the assumption and the computational cost as follows,
- about the realizable assumption: although the realizable has frequently appeared in the active learning literature,  the most related work on active learning with abstention seems not to require such an assumption (Theorem 1.1 of [Puchkin and Zhivotovskiy, 2021]). It seems to me that the realizable assumption is the price for the efficient algorithm since Algorithm 1 requires to approximate $\eta(y=+1|\mathbf{x})$ with the function $f(\mathbf{x})$ (by ucb and lcb). So, I think it would be necessary to make a more clear comparison with the previous work.

- about the efficient algorithm:
	- issue on the parameter setting: the algorithm takes the disagreement coefficient $\theta$ as the input. I am not sure whether such a coefficient can be calculated efficiently in general? (maybe an upper bound for $\theta$ is enough in special cases, but the realizable assumption could be violated.)
	- issue on the estimation of lcb and ucb: although the authors have referred to [Krishnamurthy et al. 2017] for the calculation of the lcb and ucb, I think it would be nice to discuss their computational costs since the efficiency is one of the main contributions of this paper. (for example how hard it is to compute lcb or ucb for a $\mathcal{F}$ containing the $f_\star$?).

questions: Q1: can the proposed method achieves similar Chow's excess risk without the realizable assumption when comparing with the best model in the hypothesis space $\mathcal{F}$.

Q2: how to compute the parameter $\theta$ efficiently (please refer to the second point of the weakness for more details)

Q3: what is the computational cost of ucb and lcb for a hypothesis space $\mathcal{F}$ containing $f_\star$
limitations: This paper has discussed its limitation on the realizable assumption in Section 4.2. It has shown that the same exponential saving label complexity is achieved with misspecified model space as long as $\epsilon$ is less than the approximation error $\kappa$. The results partially address the limitation on the assumption, but I think the paper would become even strong if the author could show a similar convergence rate for Chow's excess risk compared with the best model in the hypothesis when $f_*$ is not in $\mathcal{F}.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies active learning of general concept classes. Lower bound is known in this regime to rule out savings in label complexity over passive learning. However, [PT21] showed that with the additional action of abstention, active learning does provide exponential savings in terms of the error rate. This work follows the research line, and the main contribution falls into a computationally efficient algorithm that archives label complexity comparable to [PT21]. The main algorithm relies on efficient implementation of regression oracles, which has been developed in prior works.

strengths_and_weaknesses: Strengths:
+ Active learning is a very useful tool to reduce labeling cost, and this paper studies an interesting and practical extension.
+ The core contribution on efficient learning paradigm is important.
+ The paper is well written and easy to follow, with right amount of reminders and pointers.

Weakness:
- The computational efficiency is phased in terms of number of calls to an oracle, yet leaving the runtime of that oracle unsettled. Please provide concrete computational cost analysis to justify the main contribution.
- It is true that [PT21] runs with minimizing an empirical 0/1 loss which is NP-hard. Can you give more intuition on why the 0/1 loss is vital for their analysis, and why the regression oracle approach in the paper works as well?

questions: 
It is true that [PT21] runs with minimizing an empirical 0/1 loss which is NP-hard. Can you give more intuition on why the 0/1 loss is vital for their analysis, and why the regression oracle approach in the paper works as well?
limitations:   Yes.
review_title: null

Meta-review: metareview: In this paper, the authors develop the first computationally efficient active learning algorithm with abstention, while maintaining the exponential savings in terms of label complexity. Furthermore, the proposed algorithm enjoys other nice properties, such as recovering minimax rates in the standard setting. The algorithm is based on novel applications of techniques from contextual bandits, and the analysis is nontrivial. 

On the other hand, the authors should improve their paper by addressing the concerns of reviewers, especially the realizable assumption.

confidence: Certain
Decision: Accept