Venue: NeurIPS 2022 Conference

Reviews:

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: This paper provides the first near minimax optimal label complexity guarantees for deep active learning.
Section 2 analyzes the label complexity of deep active learning under Tsybakov noise. Section 3 analyzes it under another setting with an abstention option and without any low noise assumption. Section 4 extends the results to Radon BV2 space.
strengths_and_weaknesses: Strength:
1. This paper contributes new theoretical results to the area of deep active learning.
2. The proof techniques could be potentially useful for the theoretical study in this area. I like how the results do not require the Bayes classifier to be in the hypothesis class. Instead, it only requires a good approximation to be in the hypothesis class.
3. A new algorithm with theoretical support has been proposed.

Weakness:
1. The paper does not have a conclusion section.
2. No experiment is provided to support the claims. Especially, a new algorithm (Algorithm 2) is proposed, but no numerical simulation is demonstrated.
3. The limitation of the chosen set of neural networks $H_{dnn}$ and $F_{dnn}$ has not been discussed.
4. Results in Section 2 and Section 3 appear to be a bit disconnected.

questions: 1. In line 202 under Theorem 3, the paper says "The architecture of the neural network $f_{dnn}$ appearing in the above theorem is independent of $f^*$". Could the authors elaborate more on this conclusion? Intuitively, given a function $f^*$, why is the architecture of the neural network that can best approximate $f^*$ within a small error **independent** of $f^*$?
2. Following the above question, since both $H_{dnn}$ and $F_{dnn}$ are specific sets of neural networks defined based on the architecture of $f_{dnn}$, the problem setting becomes very limited if $f_{dnn}$ is chosen based on the true function $f^*$.
3. How important is the smooth assumption on $\eta$? Section 4 demonstrates how the results can be extended to Radon BV2 space. Can we assume that the results can be extended to any space as long as the approximation power of the neural networks can be proved?
4. Section 3 states that the results are generalized from that of Zhivotovskiy (2021); Zhu and Nowak (2022). Line 316-323 presents how this paper is new compared to Zhu and Nowak (2022). How about the work of Zhivotovskiy (2021)? How is section 3 technically novel compared to Zhivotovskiy (2021)?
5. Any numerical simulations?
6. There are many grammar errors:
- line 181: exhibit -> exhibits
- line 212: has well-controlled -> has a well-controlled
- line 287: analyze -> analyzes
- line 323: function -> functions
- ...
limitations:
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: This paper studies the deep active learning problem and focuses on the rigorous label complexity guarantees. Deep active learning has received practical success, however, there lack of rigorous theoretical guarantees of deep active learning. In this paper, they consider a nonparametric setting. They show the relationship between approximation and active learning. They also give an analysis of the disagreement coefficient. 
strengths_and_weaknesses: Pros:
 - Their result is easy to extend and can be applied to a large class of smooth functions that have recently been proposed. Their result can be applied to ReLU neural networks.
 - In both passive and active settings, they can learn by the neural network to achieve near minimax optimal label complexities, which gives a new perspective on nonparametric learning

Cons:
 - Their result is meaningful when the disagreement coefficient is well-bounded. However, they left the analysis of the disagreement coefficient for future work. The disagreement coefficient does not have an explicit expression, which makes it hard to judge how important their results are. 
questions:  - Their paper has a lot of results. Which one is the most significant result?
limitations:  - their result relies on the disagreement coefficient, which does not have explicit expression.
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 shows that active learning with neural networks can provably achieve the minimax label complexity, up to disagreement coefficient, and other logarithmic terms under the assumption that the neural network is obtained from $\alpha$-Sobolev space. Then the authors try to generalize the idea up to the Radon $BV^2$ space.

As claimed by the authors, the main contributions of the paper are **1)** to extend the understanding of how approximation affects active learning to achieve fast rates (e.g., under Tsybakov noise in Theorem 1) which corresponds to Theorem 6, and **2)** to identify conditions that greatly relax the (previous) approximation requirement in the learning with abstention setup (to develop Theorem 2) which corresponds to Theorem 7.

I think the key component of the paper is building a bridge by extending the active learning analysis in the parametric setting to the non-parametric DNN setting leveraging the universal approximation property of the ReLU activated neural networks.
strengths_and_weaknesses: ** Strength
1. This paper provides an extensive theoretical insight into how deep active learning could be successful in the binary classification problem.
2. This paper proves the exponential gain of the label complexity in deep active learning with the abstention option.

** Weakness
1. The paper focuses on the binary classification problem, which is the fundamental case to build necessary theoretical tools. Still, it doesn't seem to be straightforward how to generalize the insight to the multi-class classification problems when we apply the proposed algorithm in practice.
2. The presentation could be improved. The non-parametric setting mainly focuses on the $\alpha$-Sobolev space (weakly differentiable space up to $\alpha$-th order) in the main article. But after reading the whole paper including the supplementary material, Radon $BV^2$ space is a better function space to consider. Because the contents of the main article are heavily relying on the supplementary material, it might be better to re-organize the paper by focusing on the Radon $BV^2$ space instead of the $\alpha$-Sobolev space. Then all relevant results from $\alpha$-Sobolev can be moved to the supplementary material. 

** Minor points
1. At the footprint on page 3, "exponentially my sub-regions" should be "exponentially many sub-regions".
2. At Algorithm 2, $Pdim(\cdot)$ doesn't seem to be defined in the main article. I was able to locate it at L749 of Definition 6 in the supplementary material.
3. At L785, I cannot find the definition of $\mathcal{N}(\frac{\kappa'}{8L};\mathcal{X},\|\cdot\|_2)$. I understand it is the covering (or sphere-packing) number, but the definition seems to be missing.
4. At L793, balls of the radius $\frac{\kappa}{8L}$ should be $\frac{\bar{\kappa}}{8L}$.
5. At L807, Proposition 8 of Appendix D.1.3, the second condition should be $0$ if $f(x)\leq 0$ instead of $-1$ if $f(x)\geq 1$.
6. At L835 of Appendix D.2, $B_{1}^{d}$ should be $B_{r}^{d}$.
7. At L914 of Appendix D.4.2, $(a+b)^2\leq a^2+b^2$ should be $(a+b)^2 \leq 2(a^2+b^2)$.
8. At L1046 of Appendix E.2.2., the notation $\alpha$ is conflicting with the notion $\alpha$-Sobolev space. As far as I understand, this $\alpha$ in L1046 has nothing to do with $\alpha$-th order weak differentiability. Please reconsider using another letter in either case.
9. At L1057, $\bar{a}:=\frac{\gamma}{8M}$ should be $\bar{\alpha}:=\frac{\gamma}{8M}$.
questions: This paper contains a lot of materials from existing literature, so contains a long proof to digest. I still have some questions to clarify. Once questions are clarified, I would rather consider updating my rating. Thank you.

1. In algorithm 2, why $\beta_m$ is chosen to be adaptively decreasing? This implies that the abstention region seems to be adaptively changing(decreasing) as the epoch $m$ increases. How is this decreasing $\beta_m$ facilitating the exponential gain toward the label complexity in Algorithm 2? I was not able to grasp the full intuition.
2. How is the geometrically increasing query length contributing to the exponential gain of the label complexity? In other words, what's the motivation of the geometrically increasing query length? And how is it related to the decreasing $\beta_m$? I understand it is necessary for analysis, but the cost of the geometrically increasing query seems to be expensive (at least for making a decision if it is under abstention or not) unless it produces an exponentially small size of the non-abstention selection for a real label query. I see some relation at Lemma 10, but the decreasing abstention region (as described in Question 1 above) seems to be conflicting with the geometrically increasing number of points in the abstention region because of the geometrically increasing query length.
3. At L955 of Appendix D5, the condition described in the equation $(19)$ seems to be important as it is also used in the proof of Theorem 7. But I am not able to find where the condition $(19)$ has been established in the proof of Theorem 15. Can you elaborate on where the equation $(19)$ has been established/or used in the proof? (I suspect L965, but it's not sufficient.)
4. In practice, the diversification of point selection is essential to improve active learning performance.  As far as I see, the Tsybakov noise condition controls the number of ambiguous (and redundant) points in the input domain. For exponential speed up, in Theorem 7, the parameter $\beta$ does not appear anymore. It might be embedded somewhere in the proof, but I was not able to find it. Can you explain the relationship between the Tsybakov noise parameter $\beta$ and the number of queries in Theorem 7? Intuitively, if the redundant points are concentrated around **the outside of the abstention region** but still inside the query range, algorithm 2 might be failed. I was wondering where to avoid such a case.
5. At L858, I was wondering if $M_t(f)$ is still a martingale with abstention option. In other words, I want to understand the relationship between the martingale condition and the exponential gain of the label complexity. If it is a martingale, the active learning process is a fair game in some sense. How is it possible to achieve the exponential speed-up under this martingale regime?

---------------------------------------------------------------------------------------------------------------------------------------------------
After rebuttal, the authors clarified all my questions properly.

Because of the limited review process time, I cannot assure to confirm the whole correctness of the paper by myself.
However, as a collective effort to confirm the result, I do not see any serious issues or problems in this paper.
Accordingly, I updated my rating given that
- the closely related work [1] needs to be confirmed officially because I see lots of overlapped material with the paper [1] as cited by the authors,
- the authors revise the paper properly.

Thank you.

[1] Zhu, Yinglun, and Robert Nowak. "Efficient Active Learning with Abstention." arXiv preprint arXiv:2204.00043 (2022).
limitations: 1. In practice, geometrically increasing query length might be unrealistic (with/without abstention). Practical active learning typically assumes a constant size (or budget-constrained size) of the query for each epoch. I was wondering if there is a way to improve both the algorithm and the analysis with a constant query size.
2. As mentioned, it is not straightforward how to generalize the idea to the multi-class classification problem.
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: 
The authors investigate the label complexity guarantees for deep active learning from the nonparametric classification perspective. They first look into the RobustCAL algorithm which only queries data points lying in the region of disagreement and provides the near minimax optimal label complexity, bringing closer the gap between theory and practice of deep active learning. Next they replace the low noise condition with abstention and Chow’s excess error, which enables exponential speedups and leads to sharper concentration results. Last, they conclude with extensions from Sobolev/H\"{o}lder space to Radon BV^2 space.
strengths_and_weaknesses: The authors provide a detailed overview of related literature in the field. The presentation of the paper is clear and easy to follow. The contributions are theoretical. Theorem 6 provides near optimal label complexity up to disagreement coefficients and logarithmic factors. Theorem 7 provides good theoretical intuition for why abstention is efficient in practice.  
questions: I am not entirely familiar with the field, but I enjoy reading the paper. I wonder how the theorem can be carried over to implementation like how to decide whether to implement abstention, and like how to verify the conditions/assumptions of the theorems.
limitations: The current work mainly focuses on classification with binary labels. And the main theorems have dependence on the disagreement coefficient or Chow’s errors (the authors identify as well).
review_title: null

Meta-review: metareview: This paper presents two contributions in the area of deep active learning: 1) minimax optimal label complexity analysis (under low noise conditions), and 2) an exponentially improved label complexity without low noise conditions provided an abstention option is provided. 

This is a theory paper and all the reviewers agreed that this paper presents novel results and significant improvement over prior work. The paper is recommended for acceptance. However the authors should consider the reviewers' comments about improving the readability of the paper. 
confidence: Certain
Decision: Accept