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: The paper proposes a neural network-based algorithm for active learning in the k-classification setting. The algorithm improves upon previous state of the art by removing a log T factor and the data-dependent complexity term in the regret bound, and using a more efficient method for updating parameters. Under a hard-margin assumption, the algorithm performs as well as the Bayes-optimal classifier in the long run. Finally, experiments show that the algorithm has better empirical performance than baselines. 

strengths_and_weaknesses: Strengths
- The algorithm’s regret guarantee doesn’t have data-dependent complexity terms that can be large in the worst case, and the parameter update method is more efficient.
- The paper is clearly written; however, I find some paragraphs to be a little repetitive. For example, the comparison with [45] is reiterated several times.

Weaknesses
- My impression is that the algorithm’s use of neural networks for exploration and exploitation is quite similar to EE-net, and given results in [2] and related works on the theory of deep learning, the guarantees are not very surprising.
- See questions.

questions: Under the overparameterized regime, the width of the network has to be extremely large. It would be helpful if the authors could provide justifications for why this requirement is reasonable and doesn’t impede the usefulness of the guarantees.
limitations: Yes.
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 presents an active learning algorithm based on contextual bandits for deep learning with regret guarantees. The main contribution of this work lies in certain algorithmic contributions that improve the theoretical guarantees and empirical effectiveness of prior work [1], which was the first work in this line of research. These contributions include improved regret bounds, applicability to k-classification problems (relative to binary restriction in [1]), simplicity of the method (no complex model selection), and practical efficiency (no training from scratch). The authors provide empirical evidence that the proposed approach works better than comparison methods, including the predecessor algorithm of [1].

[1] https://proceedings.neurips.cc/paper/2021/hash/3dcaf04c357c577a857f3ffadc555f9b-Abstract.html 
strengths_and_weaknesses: ## Strengths
* The topic of active learning with provable guarantees, especially for neural networks, is of high importance and interest to the wider ML community
* The contributions and improvements relative to [1] – as outlined in the summary above – are significant 
* The techniques and corresponding theoretical analysis seem sound 
* Empirical evaluations are presented that support the improved effectiveness of the proposed work over [1] and other state-of-the-art approaches

## Weaknesses
* There is a significant amount of overlap with prior work that is not appropriately cited. Moreover, a large number of the improvements relative to [1] are directly thanks to the work of [2], but this is not made entirely clear. For example, Definition 3.1 appears in the EE-Net paper [2] (top of page 7), but it is presented as a novelty without a citation. Theorem 4.1 is very reminiscent of Theorem 1 of [2]. The removal of the log and input and effective dimension factors and the purposeful avoidance of NTKs appear as Remarks 1 and 2 of [2]. 
* There is no information regarding the number of trials that the results were averaged over and no error bars are present for the results in Sec. 5
* The parameter \gamma seems to be a very important parameter for the algorithm as it dictates the number of queries that algorithm makes, but an appropriate setting of it requires a hyper-parameter search before deployment. It is not clear how this can be tuned in an application specific basis in active learning. Additionally, the algorithm uses constants c_1 and c_2, but there is no mention of the values used for these constants in the empirical studies conducted. The batch size (b) parameter is also not used in Algorithm 1. It is also not reported what the value of \delta was used for the algorithm

[1] https://proceedings.neurips.cc/paper/2021/hash/3dcaf04c357c577a857f3ffadc555f9b-Abstract.html 

[2] https://arxiv.org/pdf/2110.03177.pdf 

questions: * Is there any way to mathematically tune the constant \gamma prior to deployment without having to conduct ablation studies? What are the constants c_1 and c_2 used in the algorithm and how should they be set by the practitioner? What were their values for the experiments shown in the paper?
* What are some key novelties relative to the EE-Net paper [2]?
* Given that the work of [1] is restricted to binary classification as the paper claims, how was it applied in practice to the scenarios evaluated in Sec. 5, which include data sets with multiple labels?
limitations: Yes
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 deep active learning under the streaming setting. Unlike prior work that utilizes NTK approximation bounds, this paper proposes its algorithm based on generalization bounds of overparameterized neural networks. The analysis presents several novelties and advantages over SOTA theoretical bounds including the independence from effective dimension, and the elimination of unknown complexity terms in prior work. The paper also proves an interesting theorem that the algorithm achieves zero-regret over bayes-optimal classifier over a fixed amount of rounds independent from T. The authors also conducted experiments over different datasets.

strengths_and_weaknesses: Strengths:
1. The theoretical analysis is novel with stronger bounds over prior work. I find the theoretical results and the utilization of generalization bounds very interesting.
2. Empirically, the authors conducted experiments over a wide range of datasets and the algorithm is computationally efficient in practice.

Weaknesses:
1. The experiment section measures total regret, which is not a standard metric and is rarely used in practice. Under limited budget and time horizon, the total regret (described in lines 282-283) seem to favor an aggressive exploration strategy, where the model should become accurate as early as possible. I believe presenting either the latest population regret or simply the population loss at T is a more appropriate metric. Moreover, the authors restricted the labeling budget to be 3% of the dataset, which needs more justification. Usually, it takes at least 50% of the labels in datasets like FashionMNIST or CIFAR10 to reach a solid accuracy.
2. The authors in their analysis presents generalization bounds and advertise their work for its guarantee to generalize to unseen data. Therefore, I think test accuracies at time T should also be included.

Minor Suggestion:
Although the authors mentions their utilization of generalization bounds of overparameterized neural networks [10] in remarks 4.2 and 4.3, I think these technics deserves a highlight in the introduction or abstract.
questions: Overall, I think the paper has strong theoretical guarantees. As a result, I believe the standard of "outperforming every baseline empirically" is not necessary in this case for an accept. Therefore, I strongly encourage the authors to present results using more practical evaluation metrics and under more realistic experiment settings (sufficiently high labeling budget), even though the results may not be as ideal.

I am willing to raise my scores provided some of the above concerns about empirical results are addressed.
limitations: More or less suffcient.
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 paper addresses active learning, one of the field's essential problems.
This work extends EE-Net for active learning and provides its regret analysis.
Compared with the closest work, the authors show a better regret bound.
Experimental results also show the proposed algorithm outperforms previous work.

strengths_and_weaknesses: Strengths
- The regret analysis shows the regret bound improving by O(log T) and removing the curse of dimensionality and the complexity of the function.
- This work provides theoretical justification for the proposed algorithm.
- The empirical results also prove the advantage of the proposed method.

Weaknesses
- The proposed algorithm and the result of the regret analysis are a straightforward extension of EE-Net, so their novelty is a little limited.
questions: Questions
- Is there a difference between Derivative-Context (DC) Embedding (Definition 3.1) and the input of $f_2$ in EE-Net?
- Although $\beta_{t}$ is decreased as $\sqrt(t)$ in Algorithm 1, how is $beta_t$ controlled in the experiments?
- Is the grid search over all hyperparameters conducted for the same datasets in which the regret evaluations are conducted?
- Although 3% of the total number of instances in the data set had been used as a budget in the experiments, do you see the same trend with other budgets?

Minor Comments
- In equation (7.28), the end parentheses of f are missing.
- typo: lesat -> least in the following sentence of equation (7.28).
- In equation (7.38), (7.39), (8.12), (8.13), (8.14), (8.15), $x_t$ and $y_t$, the subscripts of the expectations, seem to be $x_{\tau}$ and $y_{\tau}$, respectively.
- In equation (7.78), a \max seems to be \min.
- In Lemma 7.13, $\theta_t^{(k)}$ is not used in the main text.
- In Lemma 7.13, one of the equation number is missing.
- In the 9th statement of equation (8.2), $f(x_{t,i^*};\theta_{t-1}^*)f(x_{t,i^*};\theta_{t-1})$ should be $f(x_{t,i^*};\theta_{t-1}^*)-f(x_{t,i^*};\theta_{t-1}^*)$.
- In Lemma 8.2, $\cal{H}_{t-1}$ is not used in the main text.

limitations: Since the paper shows theoretically strong results, I would like to know the practical consideration for implementing the proposed method.  For example, I think it is not provided how the budget size affects the performance of the active learning method.
review_title: null

Meta-review: metareview: The paper has two main contributions:

1. It builds upon a recent theoretical work on providing regret bounds for active learning using neural networks. The current paper presents a better regret analysis thereby removing the explicit dependence on the effective dimensionality term and also does not have hard to estimate terms (such as the 'S' term), as was the case in prior work.

2. The paper presents a practical implementation via mini-batch SGD and presents a strong set of empirical results.

All the reviewers agree on the technical novelty and the quality of the experimental work. During the discussion phase the authors also clarified questions regarding the comparison of their results with other prior works. Overall the reviewers agree that this is a submission worthy of acceptance.
confidence: Certain
Decision: Accept