Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work tackles the problem of active learning for non-parametric classifiers and streaming data, where data points arrive sequentially and, after providing its prediction, the active learning strategy must decide whether to observe the true label or not. Performance of active learning strategies under this setting is evaluated using the difference between the cumulative sum of expected loss incurred by the strategy and the cumulative sum of expected loss incurred by a Bayesian-optimal classifier, which relates to the pseudo-regret in stochastic multi-armed bandits. The authors propose the first computationally efficient algorithm for active learning using Deep Neural Networks (DNNs) (contribution 1), which is achieved using over-parameterized DNNs. By relying on the theory of Neural Tangent Kernel (NTK) approximation, they provide a theoretical analysis of the proposed strategy (contribution 2) and show that one can leverage recent works in model selection to design a novel model selection algorithm (contribution 3). More specifically, they provide high-probability upper-bounds on the pseudo-regret and on the amount of data required for the bound to hold.
main_review: This paper leverages recent advances in contextual bandit using DNNs with theoretical guarantees for the specific task of active learning under the streaming setting.

[+] The paper is clearly written, well organized, and very easy to follow. Notation and preliminaries are clear and provide all the important information for understanding the paper.

[+] The setting tackled in this work has two components: non-parametric and streaming. It seems novel to provide a method with theoretical guarantees on sample complexity under these two conditions, most of the work in the non-parametric setting focusing on the pool-based situation (rather than streaming).

[-] Alg. 1 is an adaptation of a recent contextual bandit strategy. Application to the active learning streaming setting is natural due to the streaming process. Previous usage of (contextual) bandit methods for active learning are missing from the related work and should be discussed, e.g. Bouneffouf, Laroche, Urvoy, Féraud, and Allesiardo (2014). Contextual bandit for active learning: Active Thompson sampling. In International Conference on Neural Information Processing (pp. 405-412).

[+] By removing the typical assumption (in the contextual bandit setting) that the function complexity is known, Alg. 2 could inspire the development of new methods in the bandit community.

[-] Although the related work section is exhaustive, the second paragraph (lines 153-170) reads like a listing of historical facts. It would benefit from 1-2 sentences highlighting the novelty of the current work compared with the listed works. From what I understand, the current work uses less restrictive assumptions on the marginal distribution -- this should be clarified.

[-] The paper currently lacks experiments to confirm that the proposed method behaves as expected given the theory and that there is indeed an advantage in using it compared with existing approaches. The theoretical arguments seem sound, but it is difficult to assess their relevance and impact without an empirical evaluation. However, I understand that this could be due to the limited space (space is currently used for detailed explanations and discussions of the theoretical results, which is very good).

Disclaimer: I didn't review the proofs in the Appendix.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Using a combination of the Neural Tangent Kernel (NTK) approximation and contextual bandit approaches, the paper first derives a neural active learning algorithm for the streaming setting where the data points come sequentially and the algorithm has to decide whether to query for the label of each data point. A second similar algorithm is developed for model selection so that the model complexity does not have to be known beforehand. Both algorithms have counterparts which train the neural networks with stochastic gradient descent. The goal of the algorithms is to balance the regret and the number of queried data points. Using the mentioned theoretical frameworks, joint bounds on the regret and the number of queries are derived.
main_review: **Originality**: According to the authors, guarantees on efficient non-parametric active learning algorithms did not exist before their work. 

The proposed approach is an adaptation of NeuralUCB [1] to active learning and thus borrows a lot from it. From that point of view, this adaptation is the one of the main contributions of the paper. The other main contribution is the model selection algorithm, while inspired from existing approaches, also seems novel and provides a really nice approximation of the complexity parameter. This latter contribution is essential to the paper as it ties loose ends of the first algorithm.

In relation to related works, the authors noted:

> We emphasize that most of these works, that heavily rely on approximation theory, are not readily comparable to ours, since our goal here is not to approximate h through a DNN on the entire input domain, but only on the data at hand.

However, while I am not knowledgeable of the field, it seems weird to me that comparisons cannot be made even just to highlight the reasons why the proposed approach or the existing approaches cannot be adapted to one setting or the other.

**Quality**: By lack of knowledge of the previous works, I did not verify the proofs and barely understood the main theorems. However, proofs are short, straight to the point and divided into lemmas, which can ease up their understanding.

**Clarity**: The paper is well written for readers already knowledgeable of the three fields it is borrowing from (NTK, contextual bandits and model selection in bandits) in addition to the active learning theory field. If one is not knowledgeable in one of the fields, it might be hard to fully understand the whole. I think adding a paragraph explaining on how all these fields tie together in this paper could improve clarity a lot. 

For the order of the sections, I’m not sure why the section Related work goes in Preliminaries and Notation. It should be a section on its own after the introduction.

**Significance**: The results are important in the field of theoretical active learning. It provides theoretical guarantees for using neural networks in active learning with the NTK framework. However, even though the algorithms seem implementable (i.e. not just of theoretical interest), no experiments were done to quantify the practicality of the bounds. One could thus conclude that the bounds are probably vacuous and not of use in practice.

**Ways to improve the paper**: One way to improve would be to do experiments showing how the approach empirically performs. Another way would be to compare the approach to other approaches in similar settings as mentioned in the originality paragraphs.

[1] Zhou, D., Li, L., & Gu, Q. (2020, November). Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning (pp. 11492-11502). PMLR.

limitations_and_societal_impact: I would say that the main limitation of the paper is the setting to which it is constrained.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: NB: The original submission contains an error. The supplementary material contains the fixed version of the submission. 

This paper produces the first NTK based active learning method with provable guarantees. 
main_review: The paper is an extension of the work in Neural Contextual Bandits with UCB-based Exploration (which the authors freely acknowledge), where in moving to an active learning framework the authors had to augment the existing bandit algorithm to account for two key differences:
1) In the bandit algorithm the reward is always seen for free, whereas in active learning the algorithm must decide whether to see the reward. 
2) There is a data dependant complexity term which is a required input to the algorithm. 

To account for these, the authors first derive a selection algorithm under frozen MLP weights and known complexity. They then deal with the issue of unknown complexity by using a pool of versions of the first algorithm, with various elimination rules for pruning that pool. Additionally in the appendix, they provide versions of both these methods where the MLP weights are not frozen, but are updated by the data as well. For all methods they also provide simultaneous bounds high probability bounds on both the number of examples queried, and the regret 
limitations_and_societal_impact: The concepts and notation used here are very challenging to follow for someone not familiar with NTK. This is not a criticism of the authors or their work, but it makes the paper very challenging to read. 

The content of the paper is clearly theoretical, but it would be useful to include at least a few (even very simple) experiments to show that:
1) There are regimes where the active learning method actually outperforms random sampling when using the same NTK estimator in the Algorithms (or even just Algorithm 1, with a known and correct complexity).
2) There are regimes where using these NTK estimators with active learning is better than just training a DNN in a standard way without active learning. 

Even a toy example which is built specifically for the method (with explanation for why the method works well on this example) would help readers better understand. 

nits:
- L165: parametric should be non-parametric
- Beyond the first page, \mathcal{Y} = {-1, 1}, correct (at least for exposition). Is this why x_{t, a} \in \mathcal{X}^2? For a multiclass problem we would have x_{t, a} \in \mathcal{X}^k right? If so it would be clearer to replace \mathcal{Y} with {-1, 1} throughout, but especially in Algorithm 1, where x_{t, a} \in \mathcal{X}^2 and so the method is already specialized to binary classification.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents algorithms for active learning in the non-parametric regimes, through NTK approximation. The resulting algorithm matches the minimax rates for active learning in certain regimes. It also studies the model selection problem with respect to unknown parameters, which is missed in previous analysis with NTK approximation.
main_review: This paper converts contextual bandit algorithms into active learning algorithms with statistical learning guarantees. Such an approach looks novel and interesting to me. The paper is well-written and easy to follow. Although I didn't have time to carefully check the proofs, the derived results make sense to me (except for some specific questions as follows).

1. Is there any particular reasons to present the "frozen version" of the algorithm in the main body of the paper? The "frozen version" essentially goes back to a linear bandit algorithm to me. Seems to me that the "trained version" of the algorithm is more interesting. Does the "trained version" requires more assumption or lead to a worse bound?

2. Based on my understanding of the model selection algorithm, e.g., Carrol-type of algorithms, they usually cannot achieve regret smaller than \sqrt{T} even with some known rates (see Thm 6.1 in citation [35]). However, it seems that the guarantee of Theorem 2 surpass that limit (let's say just set \gamma = \alpha). Can you provide some explanations for that?

3. It would be nice to provide some intuitions for the sampling distribution defined in Alg2, and how it helps Alg2 to achieve its guarantees.


limitations_and_societal_impact: Limitations of the paper are mentioned in Section 5. The results are mainly theoretical; to me, it didn't lead to negative societal impacts in the foreseeable future.
review_title: null

Meta-review: In the context of streaming data, this paper addresses active learning through a neural contextual bandit and derives theoretical guarantees by relying on the theory of Neural Tangent Kernel (NTK) approximation.The contributions (novel algorithm and its theoretical analysis) are original and relevant. Most of the questions from the reviewers were addressed during the rebuttal. There are still a few concerns about related works and experimental works that the authors are kindly asked to take into account when preparing the final version. 
Decision: Accept (Poster)