Thank you very much for your constructive comments and suggestions. We are glad to provide the response to your questions.

Q: Difference from existing literature regarding the label-query decision-maker.

A: In the stream-based setting, the intuition behind the label decision-maker is similar to the bandit-based approach: We only query labels when we have low confidence to the neural network estimation. However, the crucial difference lies in the construction of confidence bound for the neural network estimation. Bandit-based approaches still adopt the technique in bandit optimization to construct the confidence bound, i.e., they only take the reward of the selected arm (class) for back-propagation and use the ridge regression in the RHKS spanned by NTK to build the ellipsoid confidence ball, causing a looser confidence bound. In contrast, our approach directly takes the label vector for the back-propagation of neural networks and we construct the generalization bound of online gradient descent as the confidence bound. Because our confidence bound is tighter, our label decision-maker is able to make more accurate decisions.

In the pool-based setting, our approach is the first label decision-maker based on the inverse gap weighting strategy to measure the uncertainty from both exploitation and exploration perspectives. In the related literature, their label decision-makers are based on gradient weight [6], gradient change [47], or core-set [42].

Thank you very much for your time and insightful comments again.

Thank you very much for your constructive comments and inspiring questions. We've updated the manuscript to address your concerns and we are glad to provide the response to your questions.

Q1: Originality.

A1: It might be a little lengthy and please allow us to summarize the novel aspects here for reviewers' convenience to capture the essence of this paper.

1. As pointed out by the reviewer, one novel contribution comes from the newly designed input and output of neural networks to reduce the input dimension to $d$. In addition to the empirical improvement, this design also brings theoretical improvement. This is because our approach can directly take the label vector for the back-propagation of neural networks, such that we can derive a tighter confidence bound for the estimation based on the generalization bound of online gradient descent. In contrast, [48] only takes the reward of the selected arm (class) for the back-propagation and adopts the technique in bandit optimization to build the confidence bound, which leads to the dependence of $L_{H}$ in their confidence bound.
2. Another novel contribution stems from the label-query decision-maker to minimize the label complexity in active learning. For example, in the proposed pool-based algorithm, we are the first to use the Inverse Gap Weighting strategy to select data points in active learning, to measure the uncertainty from both exploitation and exploration perspectives.
3. As pointed out by the reviewer, the third novel contribution comes from the theoretical analysis. Our proof technique is very different from previous work, and importantly, we are able to remove the dependence of the intractable complexity term $L_\mathbf{H}$, detailed improvement as follows in Q3.

Q2: More experimental runs.

A2: Thanks for the reviewer's suggestion. We've extended our experiments to 10 runs (Table 1 and Table 2). The new results are consistent with the previous results and conclusion.

Q3: Adapt the analysis to the varying $\alpha$.

A3: Thanks for the reviewer's suggestion. We've added the new theoretical results (Section F in the latest manuscript) adapting to the varying $\alpha$. Since the Mammen-Tsybakov noise $\alpha$ assumption and related work [48] only study the binary classification, we present the following results in the binary classification.

The results for our proposed algorithm:

\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 of ${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)$. Note that the main technical challenges lie in building the confidence bound for the neural network estimation rather than adapting the result to varying $\alpha$.

Thank you very much for your time and insightful comments again.

Thank you very much for your detailed and constructive comments and we are glad to provide the response to your questions.

Q1: Extend to other network structures.

A1: Yes, our analysis can be readily converted into many more advanced neural structures, because we only use the almost-convexity property of MLP in over-parameterized networks. Using the results of [3], our results can be directly extended to CNN and ResNet.

Q2: Value of S.

A2: We set $S =1$ in all the experiments (see implementation details on Page 14). Since we have the exploration hyper-parameter $\gamma$ which plays a similar role in tuning the exploration strength, we conducted the grid search for $\gamma$ in the experiments instead.

Q3: Cumulative population regret metric.

A3: We agree with the reviewer in that the population regret of the last round is also a promising regret metric. The cumulative population regret metric reflects the overall performance of each label query, which implies the average sub-linear decreasing error rate with respect to the number of queries $O(1/\sqrt{Q})$.

Q4: Advantages of using the exploration network.

A4: The main advantage of using the exploration network is to achieve adaptive exploration for "upward" exploration and "downward" exploration. The upward exploration is to describe the case when our model $f$ underestimates the expected reward (label value) $h$ and the downward exploration is to describe the case when $f$ overestimates $h$ (i.e., $f(x) > h(x)$). A motivating example is that, when $f(x)$ overestimates $h(x)$, the UCB-based method will further add a positive value to $f(x)$, making the deviation larger. Instead, the exploration network is able to add a negative value to $f(x)$ by learning and predicting the potential gain $h(x) - f(x)$, making the gap smaller.

The theoretical motivation for this exploration network and using the gradient as input is the statistical confidence bound. The confidence bound can be represented as follows: $|f(x) - h(x)| \leq \Phi(g(x))$, where $g(x)$ is the gradient of $f(x)$ and $\Phi$ represents the statistical form with respect to $g(x)$. Thus, instead of deriving a fixed form of $\Phi$, the exploration network uses a network to learn a form of $\Phi$, i.e., the mapping from $g(x)$ to $f(x) - h(x)$. In this way, the exploration network is able to learn a flexible form of $\Phi$ that adapts to different datasets. In contrast, the statistical form of $\Phi$ is fixed on any dataset. The reviewer may want to refer to [10] for more details.

Q5: Existence of $\theta^\ast$.

A5: $\theta^\ast$ always exists as long as the parameter space of the neural network is large enough (controlled by $m$). This comes from the universal approximation property of neural networks, i.e., given any $T$ data points, there exists at least a solution for the neural network to fit these $T$ data points. Therefore, $\theta^\ast$ always exists but will depend on the dataset, i.e., $\theta^\ast$ varies on different $T$ or different datasets.

Thank you very much for your time and insightful comments again.

Thank you very much for your constructive comments and we are glad to provide the response to your questions.

Q: Theoretical difference from existing methods.

A: Because the bandit-based approaches (e.g., [48]) transform each class to an arm, they only use the reward of the selected arm (one class) for the back-propagation of neural networks and use the bandit technique to build the confidence bound for the network estimation. To be specific, they build the ellipsoid confidence ball based on the ridge regression in the RKHS spanned by NTK, adopted from [56], which causes the dependence on $L_{\mathbf{H}}$. In contrast, our approach directly takes the label vector for the back-propagation of neural networks and we construct the generalization bound of online gradient descent as the confidence bound, which is distinct from the existing bandit-based approaches, removing the dependence on $L_{\mathbf{H}}$. We sincerely invite the reviewer to read our global response, where we provide detailed information regarding the performance improvement with varying $\alpha$.

Thank you very much for your time and insightful comments again.