Neural Active Learning Beyond Bandits

Summary

The paper investigates active learning strategies using neural networks for both stream-based and pool-based scenarios. It addresses the challenge of mitigating the adverse impacts of the number of classes ($K$) on active learning performance. The authors propose two algorithms that incorporate neural networks for exploration and exploitation in active learning, providing theoretical performance guarantees. Experiments demonstrate that these algorithms consistently outperform existing baselines.

Strengths

The paper is well written and easy to follow. The paper studies an important and interesting problem of how to do active learning in two settings. The proposed algorithms based on exploitation-exploration NN have some novelty. I checked parts of the proof and feel they should be correct. While I am not familiar with this line of theoretical work, I would refer to other reviewers' opinions for evaluation.

Weaknesses

I have no major concern on the current manuscript. On minor issue: I feel it is better if the authors could explain how your work and the previous literature (e.g. bandit-based algorithms) decide whether to observe the label for each sample in detail. How your work is different from the existing literature on this problem?

Questions

Please refer to the above Weaknesses section.

Rating

6: marginally above the acceptance threshold

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Summary

This paper studies active learning using newly designed exploration and exploitation neural networks. Instead of transforming the instance into $K$ arms and then calculating scores for them, they directly input the original instance into the network, hence avoiding the cost of $K$ time forward-propagation and dimension multiplication due to embedding. As a result, they present theoretical guarantees with a slower error-growth rate, concerning $K$. Besides, extensive simulation results are presented.

Strengths

# Origionality - The idea of exploration-exploitation networks is not so novel but related works are covered in detail. It originates in [10] and is then adopted by [11], which is one of the works this paper is compared to. - The idea of reducing the dimension to $d$ is novel considering the literature starting from [10]. # Quality - The theoretical proofs seem to be concrete. - The experiments are extensive and detailed. They validate the performance and computation efficiency claimed. # Clarity - The paper is in general well-written and smooth to follow, with the exception of some proofs in the supplementary material. # Significance - The proposed algorithms are of interest as the input is more coherent and the performance is great.

Weaknesses

- The main originality seems to be theoretical proofs rather than network structures. However, the proofs heavily depend on NTK techniques. - The experiments were conducted only five times, which could potentially impact the reliability of the results. I would appreciate seeing outcomes derived from a greater number of runs. - The theoretical results are only for the setting where the Tsybakov noise $\alpha = 0$, making it less comparable to existing literature, except when compared to [48] indirectly as $\alpha \rightarrow \infty$.

Questions

- May I ask the reason behind limiting the experiments to five iterations? Was it influenced by computational constraints or other considerations? - What's the main difficulty of analyzing settings other than $\alpha = 0$? What do the authors expect different levels of $\alpha$ to influence the theoretical results intuitively?

Rating

6: marginally above the acceptance threshold

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Summary

This paper builds on prior work by Wang et al., 2021 on neural active-learning with performance guarantees. As in that work, the authors construct two neural networks -- an exploitation network and an exploration network which is trained to fit the residuals (noise) of the exploitation network -- and sum their outputs to estimate the expected loss of each class given the context. On the applied side, what makes this work different from Wang et al.'s is that the neural proposed in this paper jointly predicts the expected losses for all actions (classes) simultaneously. Whereas Wang et al. apply their neural networks to a context+action vector for each class individually. This makes inference K times faster for the authors' new method, where K is the number of classes. Additionally, the inputs to the neural network are K times shorter than in Wang et al. because they don't need to use a kronecker product construction to encode the chosen action (class) on the input side. And the smaller dimensionality also makes everything more efficient. The authors then propose and analyze two algorithms for active learning which both utilize the signal & noise trained neural networks. The first algorithm is for the stream-based setting in which one example arrives at a time and the learner can either can either request a label or not, and there is a budget imposed on how many labels can be requested. The second algorithm applies to the pool-based setting where a set of examples is presented at each instance and the learner can request a label for one example in the set. For both settings the authors aim to minimize the population cumulative regret, which is the regret of the true / out-of-sample model performance of the learned model accumulated over the course of learning, minus the same for the Bayes optimal classifier. On the theory side, the authors utilize the neural tangent kernel framework to derive lower and upper bounds on the cumulative population regret for two regimes of Mammen-Tsybakov noise: the hard margin regime and the unrestricted regime. The derived bounds improve those of Wang et al., 2021 by a factor of as much as O(md) where "m" is the network width and "d" is the input dimensionality. The authors also provide regret and label complexity bounds for the case where a unique Bayes optimal classifier exists. All bounds depend on a quantity related to the underlying dimension of the neural tangent kernel and another quantity related to the data. Finally, the authors present experiments comparing their active learning algorithms (NeurOnAL-S and NeurOnAL-P) for the stream and pool-based settings on several UCI datasets and FashionMNist against other neural active learning methods. The methods they compare against are: I-NeurAL (Wang et al., 2021), ALPS, BADGE, ALBL, CoreSet, DynamicAL. NeurOnAL-S/P generally outperform all others in terms of both test accuracy and running time, making for compelling empirical results.

Strengths

The theoretical bounds for the proposed method are quite an improvement over those for the method presented in Wang et al. 2021. The empirical wins, both on increased test set accuracy and decreased running time, for the stream and pool-based settings also demonstrate siginificant improvement over multiple prior approaches.

Weaknesses

One weakness of the proposed method is that it is demonstrated with a particular neural network structure (an MLP) and the authors do not state whether it can be used with arbitrary network structures, and if it can, then how the bounds might change (I realize this would be very difficult analysis). But some discussion around how general the approach is would make this paper much less niche/narrow. A related weakness is that the bounds are in terms of quantities (S and L_H) that are difficult for practitioners to quantify or trade off in order to find the network architecture for their problem. In the experiments, I did not see stated which subsets of data were used to tune hyperparameters. One might therefore worry that hyperparameters were tuned to give good test performance.

Questions

For the pool-based setting, I am interested to know why the authors chose cumulative population regret as their subject of analysis rather than the simple regret? With pool based learning, one typically doesn't care about the performance of the intermediate models constructed during training, only the last model. I'm also curious about the use of the exploration and exploitation networks and why they are better able to model the signal and the noise. In particular, using the gradients of the exploitation network as inputs to the exploration network -- why does this work? Is there any theoretical explanation (not just intuition) that justifies how this helps fit the noise? Finally, I am trying to understand the statement in section 5 that h(x_t)[k] = <Grad f(x_t, theta*)[k], theta* - theta1>. Is this an assumption or does such a theta* always exist? And if it always exists, is it the same theta* for all "t" and "k"?

Rating

8: accept, good paper

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Summary

The paper presents two algorithms for active learning using neural network approximations, specifically designed for stream-based and pool-based scenarios. The goal of these algorithms is to address the challenges posed by the number of classes (K) in bandit-based approaches, such as performance degradation and increased computational costs.

Strengths

The paper is both intuitive and theoretically sound. It introduces a new exploitation network and exploration network that take the original instance as input and simultaneously output the predicted probabilities for K classes. This approach eliminates the need to transform the instance into DK long vectors. The paper provides theoretical performance guarantees, showing a slower error-growth rate as K increases. Furthermore, it demonstrates that the proposed algorithms achieve the optimal active learning rate under different noise conditions.

Weaknesses

From a theoretical perspective, the core difference between existing methods that transform instances into DK long vectors is not clear.

Questions

See Weaknesses

Rating

6: marginally above the acceptance threshold

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Global Response: Updates of Manuscript

We really appreciate all reviewers' constructive feedback and time in reviewing our paper. Here, we would like to provide the summary regarding the updates of the manuscript: **(1) Experiments**: Per Reviewer Jpt8's suggestion, we've extended our experiments from 5 runs to 10 runs (Table 1 and Table 2). The new results are consistent with the previous results and conclusion. **(2) Theoretical analysis**: We've added a new theorem in Section F to show the complexity of regret and label queries with varying $\alpha$ in binary classification. The results are listed as follows. Our results: \begin{aligned} \mathbf{R}\_{stream}(T) \leq \widetilde{\mathcal{O}}( (S^2 )^{\frac{\alpha+1}{\alpha+2}} T^{\frac{1}{\alpha + 2}}), \\\\ \mathbf{N}(T) \leq \widetilde{\mathcal{O}}( (S^2 )^{\frac{\alpha}{\alpha+2}} T^{\frac{2}{\alpha + 2}}). \end{aligned} For comparison, the results in [48]: \begin{aligned} \mathbf{R}\_{stream}(T) & \leq \widetilde{\mathcal{O}} \left ( {L_{\mathbf{H}}}^{\frac{2(\alpha +1)}{\alpha+2}} T^{\frac{1}{\alpha +2}} \right) + \widetilde{\mathcal{O}} \left( {L_\mathbf{H}}^{\frac{\alpha +1}{\alpha+2}} (S^2)^{\frac{\alpha+1}{\alpha+2}} T^{\frac{1}{\alpha +2}} \right), \\\\ \mathbf{N}(T) &\leq \widetilde{\mathcal{O}} \left ( {L_\mathbf{H}}^{\frac{2\alpha}{\alpha+2}} T^{\frac{2}{\alpha +2}} \right) + \widetilde{\mathcal{O}} \left( {L_\mathbf{H}}^{\frac{\alpha}{\alpha+2}} (S^2)^{\frac{\alpha}{\alpha+2}} T^{\frac{2}{\alpha +2}} \right). \end{aligned} For the regret $\mathbf{R}\_{stream}(T)$, compared to [48], our result removes the term $\widetilde{\mathcal{O}} \left ( {L_{\mathbf{H}}}^{\frac{2(\alpha +1)}{\alpha+2}} T^{\frac{1}{\alpha +2}} \right)$ and further improves the regret upper bound by a multiplicative factor $ {L_\mathbf{H}}^{\frac{\alpha +1}{\alpha+2}}$. For the label complexity $\mathbf{N}(T)$, compared to [48], our result removes the term $\widetilde{\mathcal{O}} \left ( {L_\mathbf{H}}^{\frac{2\alpha}{\alpha+2}} T^{\frac{2}{\alpha +2}} \right)$ and further improves the regret upper bound by a multiplicative factor of $ {L_\mathbf{H}}^{\frac{\alpha}{\alpha+2}}$. It is noteworthy that $L_\mathbf{H}$ grows linearly with respect to $T$, i.e., $L_\mathbf{H} \geq T \log (1 + \lambda_0)$.