Improved Algorithms for Neural Active Learning
Authors: Yikun Ban
Yuheng Zhang
Hanghang Tong
Arindam Banerjee
Jingrui He
Venue: NeurIPS 2022 Accept (2022)
Keywords: Active Learning
Neural Network
Deep Learning

Abstract: We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. In particular, we introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.  Then, the proposed algorithm leverages the powerful representation of NNs for both exploitation and exploration, has the query decision-maker tailored for $k$-class classification problems with the performance guarantee, utilizes the full feedback, and updates parameters in a more practical and efficient manner. These careful designs lead to an instance-dependent regret upper bound, roughly improving by a multiplicative factor $O(\log T)$ and removing the curse of input dimensionality. Furthermore, we show that the algorithm can achieve the same performance as the Bayes-optimal classifier in the long run under the hard-margin setting in classification problems. In the end, we use extensive experiments to evaluate the proposed algorithm and SOTA baselines, to show the improved empirical performance.

Improved Algorithms for Neural Active Learning
Yikun Ban", Yuheng Zhang", Hanghang Tong, Arindam Banerjee, and Jingrui He
University of Illinois Urbana-Champaigh [yikunb2, yuhengz2, htong, arindamb, jingruj @illinois.edu
Abstract
We improve the theoretical and empirical performance of neural-nettorkk(NN)) based active learning algorithms for the non- non-parametric streaming setting. particular, we introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work. Then, the proposed algorithm leverages the powerful representation NNs for both exploitation and exploration, has the query decision-maker tailored for k-class classification problems with the performance guarantee, utilizes the full feedback, and updates parameters in a more practical and efficient manner. These careful designs lead an instance-dependen regret upper bound, roughly improving by a multiplicative factor Ollog I') and removing the curse of input dimensionality. Furthermore, we show that the algorithm can achieve the same performance as the Bayes-ophe Bayes-optimal classifier in the long run under the hard-margin setting in classification problems. In the end, uate the proposed algorithm and SOTA baselines, to show the improved empirical performance.
extensive experiments to eval-
Introduction
The Neural Network (NN) is one of the indispensable paradigms in machine learning and is widely used multifarious supervisedlleaminnn
tasks [23]. As more and more complicated NNs are devel- oped, the requirement of the training procedure the labeled data grows, incurring significant cost of label annotation. Active learning investigates effective techniques on much smaller labeled data set while attaining the comparable generalization performance to passive learning (19]. In this paper, we focus on the classification problem in the streaming setting of active learning with NN models. At every round, the learner receives an instance and compelled to decide on- on-the-fly whether or not to observe the label associated with this instance. This problem seeks to maximize the generalization capability of learned NNs in sequence of rounds, such that the model has robust performance on the unseen data from the same distribution 40
In active learning, given access to the i.i.d. generated instances from distribution D, suppose there exist class functions FF that formulate the mapping from instances to theirs labels. In the parametric setting, i.e., has finite VC-dimension 25,, existing works 14 have shown that the active learning algorithms can achieve the convergence rate of Õ(1/ /)) the best population loss in F, where N is the number of label queries. In the non parametric setting, recent works AZ 35 provide the similar convergence results while suffering from the curse of input dimensionality. Unfortunately, most of NN-based approaches to active learning do not come with the performance guarantee, despite having powerful empirical results.
The first performance guarantee for neural active learning has been established in a recent work by 48, and the analysis is for ever-parameterized neural networks with the assistance of Neural Tangent Kernel (NTK). We carefully investigate the limitations of [4 which turn into the main
Both authors contribute equally.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

motivations of our paper. First, 43 transforms the classification problem into a aumt bandit problem [55]. minimize a pseudo regret metric. Yet, on the grounds that they seek to minimize the conditional population loss on sequence of given data, it is dubious that the pseudo regret used in 48] can explicitly measure the generalization capability of given algorithms (see Remark 2.J. Second, the training process for NN models is not efficient, as 48 uses vanilla gradient descent and starts from randomly initialized parameters in every round. Third, although [SS] removes the curse of input dimensionality d, the performance guarantee strongly suffers from another introduced term, the effective dimensionality d, which can be thought of as the non-linear dimensionalities of Hilbert space spanned by NTK. In the worse case, the magnitude of d can be an unacceptably large number and thus the performance guarantee collapses.
1.1 Main contributions
In this paper, we propose novel algorithm, I-NeurAL (Improved Algorithms for Neural Active Learning), to tackle the above limitations. Our contributions can be summarized as follows: (1) We consider the k-class classification problem, and we introduce two new regret metries to minimize the population loss, which can directly reflect the generalization capability of NN-based algorithms. (2) I-NeurAL has a neural exploration strategy with novel component to decide whether or not to query the label, coming with the performance guarantee. I-NeurAL. exploits the full feedback in active learning which subtle but effective idea. (3) I-NeurAL is designed to support mini- batch Stochastic Gradient Descent (SGD). In particular, at every round, I-NeurAL. does mini-batch SGD starting with the parameters of the last round, i.e., with warm start, which is more efficient and practical compared to
48 (4) Without any noise assumption on the data distribution, we provide an instance-dependent performance guarantee of AL for pver-parameterized neural networks. Compared to 48. we remove the curse of both the input dimensionality d and the effective
dimensionality d: Moreover, we roughly improve the regret by a multiplicative factor log(?"), where I'ss is the number of rounds. (5) under a hard-margh assumption on the data distribution, we provide that NN models can achieve the same generalization capability as Bayes-optimal classifier after (log 7') number of label queries; (6) we conduct extensive experiments on real-world data sets to demonstrate the improved performance of I-NeurAL over state-of ofe-----thhttete baselines including the closest work 48 which has not provided empirical validation of their proposed algorithms.
1.2 Related Work
Active learning has been extensively studied and applied to many essential applications 44 Bayesian active learning methods typically use a probabilistic regression model to estimate the improvement of each query 22 E. In spite of effectiveness on the small or moderate data sets, the Bayesian-based approaches are difficult to scale to large-scale data sets because of the batch sampling [43]. Another important class, margin algorithms or uncertainty sampling [33]. obtains considerate performance improvement over passive learning and is further developed by many practitioners [20 2 37 [5].
Margin algorithms are flexible and can be adapted to both streaming and pool settings. In the pool setting, a line of works utilize the neural networks in active learning to improve the empirical However, they do not provide performance guarantee
performance [56
for NN-based active learning algorithms. From the theoretical perspective, [5] 21
S 52 provide the performance guarantee with the specific classes of functions and 26 22 present the theoretical analysis of active learning algorithms with the surrogate loss functions for binary classification.
5.
However, their performance guarantce is restricted within hypothesis classes, i.c. the parametric setting. In contrast, our goal is to derive an NN-based algorithm in the non-paramttric setting that performs well both empirically and thcoretically. Neural contextual bandits 53 provide the principled method to balance between the exploitation and exploration transforms active learning into neural contextual bandit problem and obtains a performance guarantee, of which limitations are discussed above.
39
y 10 48
As 48 is the closest related work to our paper, we emphasize the differences of our techniques from throughout the paper. We introduce the problem definition and proposed algorithms in Section
4S
and Section respectively. Then, we provide performance guarantees Section D and empirical
results in Section 5 ending with the conclusion in Section X

---

2 Problem Definition
In this paper, we study the streaming setting of active learning in the k-class classification problem. Let A' denote the input space over R , {1.2. ...k k} represent the label space, and 'D be some unknown distribution over xx V. round E [T] {1.2, .., . an instance X; drawn from the marginal distribution Dx and accordingly Yr is drawn from the conditional distribution Dyjx.- Here, yr can be thought of as the index of the class that x, belongs to. Inspired by [48], we first transform into & context vectors representing the & classes respectively: Xr,1 (x .o...."'''' ,, Xt,2 (OT .......0 0
OT) ...... X (0) OT ,'....,,,] xT and Xt,i Rdk Vi E [k.. In accordance with context vectors, we construct the label vectors representing the A possible prediction: Vt,1 (1, ........0 0)T 2.. = (0, 1,...... 0)T ....,, YI. = (0, 0, .,. and Yt, E R E [k:]. Thus, Vt. is the ground-truth label vector for
Under the non-parametric setting of active learning, define unknown function h to formulate the conditional distribution Dy x + [0, 1], such that
Vi E [k), P(y ye.(xx) h(xe,))
(2.1)
which is subject to Σ ((x,,)) = 1. For simplicity, we consider the k-class classification problem with 0-1 loss. Given x,, i.e., Xt,i, [K;, let ė be the index of the class predicted by some hypothesis and thus y,, is the prediction. Then, we have the following loss:
L(y,, = Hy, * Nt.. 1),
(2.2)
where I is the indicator function.
Given the number rounds T, at each round E [T]. the learner receives an instance x, drawn i.i.d. from Dx. Then, the learner needs to make prediction Y..3, and at the same time, decide on-the-fly whether not to query the label Yt.y, where y/ is drawn i..d. from xy As the goal of active learning tasks often to minimize the population loss 40 we introduce the following two regret metrics.
Definition 2.1 (Latest Population Regret). Given the data distribution D, the number of rounds T, the Latest Population Regret is defined as
RT
E XT~Dx
99 Br~DSIK (LVT,T-TTT
E
E
[LyT,..
[x]]
Xy Dx
UT ~ Dylr
(2.3)
where yT is the prediction the Bayes-optimal classifier would make on instance xT, i.e., i arg [ax h(xT,;) ) for yT.".
Definition 2.2 (Cumulative Population Regret). Given the data distribution D, the number of rounds T, the Cumulative Population Regret is defined as:
T
RT
E
E De-DyIx
[Ly Vt.ge)
xi]
E
E
([Yy,," xil
1=1
(2.4)
where Yt,² is the prediction the Bayes-optimal classifier would make on instance Xt, i.e., i" arg max4e[)] h(xx.)) for yı,
Rr measures the performance at the last round T only, and Ry measures the overall performance in rounds combined. Therefore, the goal of this problem to minimize Ry or Ry, or both. At the same time, we also aim to minimize the following expected query cost:
N
Σ
E
L
xr),
(2.5)
XIDD
where I, is the indicator of the query decision in round such that 1 if ye is observed; I, 0. otherwise.
Remark 2.1. Minimizing Ry or Ry shows the generalization capability the learned hypothesis on the distribution D. However, the problem defined in 48 to minimize the cumulative conditional

---

population regret as follows:
RT
E DymDa
E M) Dy
[L(y : ((.)))x.)))
(2.6)
As Byn~Dyin x1 [L Nt.we Xi] the population loss conditioned on X unfortunately, Ry only measures the performance of the learned hypothesis on the collected data {xx) and Ry cannot directly measure the accuracy of the hypothesis on unseen data instances, Although Ry follows the regret definition in multi-armes bandits 55 it is fair to say that Ryy may not be good metric in active learning.
3 Proposed Algorithms
In this section, we elaborate on the proposed algorithm I-NeurAL (Algorithm D In contrast to the directly comparable work 4 I-NeurAL has the following novel and advantageous aspects: (I) I-NeurAL incorporates a neural-based exploration strategy (Line 6) inspired by recent advances in bandits [3] solve the
dilemma the decision for whether or not to query labels; (2) I-NeurAL includes a novel component (Line 11) to decide whether not to query labels the k-class classification problem; (3) I- infers and exploits the feedback all the contexts
(Lines 12-17), instead of only utiliziig the feedback of the chosen context in [48] ; (4) I-NeurAL
conducts mini-batch SGD based on the parameters of the last round (Algorithm 2 which is more
practical, opposed to conducting vanilla gradient descent from the initialization at every round in 48 Next, we will present the details of I-NeurAL.
Exploitation Network f1. Given Xt, E [K], to learn the unknown function & (Eq. fully-comnected neural network fi with L-depth and m-width:
2.1
we use
(x 0²) Wlo(WWL L-2 ( (W)X,,)))
(3.1)
where W! E Rm W! E Rmxm for S 1 S - 1, W E T Ixm 0 = [vec( (W)) ...., vec TTT E R", and a is the ReLU activation function oxx) = max (0, x}. In round t, given x... E [k], (x 0 is assigned to learn h(xt,)). Based on the fact natural regard Lyyt, Vt.y.) as the label for
f(xx,)) DyrDi
IE
[1 Lyy,,i, Vt.s.)) }..
training fi. Note that take the basic fully connectdd network as an example for the sake of analysis in over-vvvrre paremearamteri networks and fi can be easily replaced with more complicated models depending the tasks.
Exploration Network f2. addition to the network f1, we assign another network f2 to explore uncertain information contained in incoming instances. First, we carefully design the input of fa to incorporate the context vectors of the instance and the discrimination-ablle of fI, to learn the error between the Bayes-optimal probability h(xx,)) and the prediction fi (xt,;: e.).
Definition 3.1 DDrivative-Connext (DC) Embedding). Given the exploitation network fi(:: ((1)))
and an input context Xt, its DC embeding is defined as
|vec (V (Vx,, f1 07 1)
((x..))
X1,5
E 2dk
(3.2)
(22 /2/ V Vx,, (x1,; 1211
v2
where Vx., fi is the partial derivative of fi (x 0,-1) with respect to Xt,i-
Note that the input for f2 in is the gradient with respect to 01, denoted by V,, fi (xx,;; 1)-1) E R Its dimensionality much larger than Fi (xt,;; 0/-1) in Definition 3.1 may causing significant computation cost.
((x(,)) is normalized so that (lo(xx,))ll2
Given the input (x.,)). similarly, we choose the fully-connected network to build f2:
f2( 0²) ;
W ( - (Wi
(3.3)
where W E mm22kd W E m=m for 2 < S L 1, W Iixm and 0² [vec(W?)+ 7 ..... veo TI E R In round t, given Xt,,, Vi [4], fz is predict h(x,,))

---

Algorithm I-NeurAL
Input: T (number of rounds) fI, f2 (neural networks), 7h 72 (learning rate), (exploration parame-
ter), (batch size), (confidence level)
Initialize 0- 0g 0u 0 0, 0
2: Hi 0: Hgj 0
3: for 1. do
4: Observe instance X
R and build X1,i, Vi E [A]]
5: for each [k] do
6:
[(x,,15 02-1)
(fi (Xi,; 02-1)
fx((((x,)) ( Exploration Score
Exploitation Score
7:
end for
8:
arg max4e[4] [( ((x,, 02-1)
9:
1 argmax, ((AA)E a()) f(x,, 0.-1)
Predict y,3
11:
I 111f(x,, 11-1) fx 02-1)1 < 2% E {0,1); B. v 201
+
2231.
22
12:
I, then
Query x, and observe y/2
14:
for i [k] do
15:
r2, = L(y,,,, Vt...) (defined in E.q. 2.2
16:
ri. rt, fi (x 0)-1)
17:
end for
18:
else
19:
for
i
[k] do
20:
r2 = 1 L(y.,,,
21:
2 = rt,s -fi (i 0/-1)
22:
end for
23:
end if
H. H U ((x,,
[+]]
25:
H. = H.-1 U (x,,,, E [+]]
26:
00,0; 0 --in--Bttch-SSe Batch-SGD-Want Warm-Start ( (f1, f2, H,, H... b)
27:
end for
28: Return (0', 0²) uniformly from ((0), ..)
0/. 0,-1,07-1) 0
f (x 0)-1) for exploration. Because h(xe,s) - f1 (xr,s; 0:11) yi Dy-Dyls
[1 L(yt, Nt.u.)
fi (x 0/-1)), we regard L(y Nt.ye) ( 0%_1) as the label for training fz.
To sum up, in round t, given Xt.i, Vi E [k), the prediction 7 (y,,)) is made based on the sum of exploitation and exploration scores, i.e., fi (xt,;; 0/-1) fa(((x;))) 0z-1) (Lines 5-10).
Query Decision-makes (Line 11). label query is made when I-NeurAL is not confident enough to discriminate the Bayes-optimal class from other classes. 2y (B, is also defined in Lemma can thought of as a confidence interval for the distance between the optimal class and second optimal class, where 7 is the hyper-parameter
the sensitivity of the decision-maker in practice. Given any y 2 1,5 E (0, 1), with probability at least - 6, based on our analysis (Lemma 7.5). E(x..v.) [T 2,3 Vt.w.
E(x.)))D [Ly,,,,, when I, O, i.e., I-NeurAL suffers regret. Thus, use Y,, as the pseudo-label in this case and we have the following update rules.
Utilize Full Feedback (Lines 14-25). Different from the bandit setting where the learner can only observe the reward of the selected context, we can infer the rewards of all contexts in active learning, as we know the specific class of the current instance. Thus, for each Xt,i, i [K], r/. 1 L(yt, Vt.v.) regarded as the "reward" of Xt,s predicted by f1, and r², r/, fi (xx,;; 0²) ) is regarded as the "residual reward" of X1,5, predicted by fz. In summary, in round f, when I, 1, Ye. is observed to
5

---

Algorithm 2 Mini-Baich-SSGD-Wam---
( (/i, /2, H4, Hg,
Define Li[(x, r'): 0-| (r' fi 222/222
2: Uniformly draw a set Hi C s.b, [A]]
3: 0, -
-001111 + Σ VilLi r²); 0-1;
(x
4: Define L2((0(x), )) 0 (r2 f2(Ø(x); 02)
5: Uniformly draw a set Hi
C Hy, s.,., [7(2] b
- 22
6: 0, = 00-1-
22
Σ
VoiL2|(<(x))
EE)
7: 24 s4-1 U (
(0.00,) 8: Return (0), 0:) uniformly from S2
0,)
update rl, and r2 when 1 0, Nt,7 is regard as the pseudo-label to obtain ri, and r Vi [k]. Therefore, we have the training data HP for Si and Hl for f2-
Mini-Batch SGD with Warm-Start (Algorithm 5.. Unlike 488 that uses vanilla gradient descent from randomly initialized parameters in each round, causing unnecessarily expensive computation, extend the training procedure to mini-batch SGD with warm start, ie.. we incrementally train the parameters 0, starting from the parameters of the last round 0,-1 in each round t.
Algorithm | depicts the workflow of I-NeurAL. Lines 1-2 initialize the parameters where each entry of W, is drawn from the normal distribution N(0, (0,2/m) and each entry of W, is drawn from N (O, 1/m) for both fi and f2. Hb. H6 store the historical data for fi and f2 respectively. In each round Line 4 builds the & contexts for the observed instance Xx, and Lines 5-7 calculate the inooitattio-expllraaain score for each context. (Line 8) is the index of the and thus y..3 is the prediction. j (Line 9) is the index of the second optimal-predien predicteddddd class, which used to decide whether to make query. Line 11 is our decision component. When I, 1, shows that we are not confident enough about our prediction, so that we make a query for x; and observe the rewards for each context (Lines 12-17). When I O, based on our analysis, with high confidence, the prediction y,, matches the one predicted by the Bayes-optimal classifier. Hence, we consider y, y as the label and observe the reward for all contexts (Lines 18-23). In the end, we update the networks fi and f2, based on the collected data (Lines 24-26).
predicted class
4 Regret Analysis
In this section, provide the regret analysis of I-NeurAL in the everpparameterized neural networks. First, we need the standard normalization restricted to the input instances.
Assumption 4.1. For any t E [2], ||x||2 = 1.
Inspired by 16 we define the following function class. Given a constant v > 0, we define the following v-ball of 8² around the random initialization: B(0)) v) = (0 |@e - 0- - O )
}
Recall that 1, 1, f1(x fx 01_1) Let 0,-; represent the parameters trained on H using Algorithm with the Bayes-optimal classifier, where H1:; = {x,,.", rh. |==1 are the historical 2 rt.,- (x 0 Then, we provide the following regret bound that depends on the classification ability of exploration network class induced by B(0), v). Theorem
2
Bayes-optimal pairs. We define
4.1. Güven the number of rounds T, for any 5 E Appoly(T, k, L,v)),,) m
(0,
10,
0, suppose m 2
72
1
TTm
Ei ()) -2, & inf Σnn (f((0(x,,)) ); 0²)
inf 0² (E
<
8'EB(03,))
Then, with probability at least - 8 over the initialization of 0%, & there exist small enough

---

constant such that Algorithm !
achieves the following regret bound:
Rr S O (2 Serso(2vT
T6 + 4/1 + 2v 2L22log(((T))))) 0(1)
(4.1)
v2
and at the same time Nr - (T)). Suppose the Bayes-optimal classifier has zero classification errors, i.e., : Vt.u = 0, [T'. It holds that
6
4V4 2T
2 log (T(K)/))))
RT I O
+ +2V
(4.2)
T
Theorem 4.1 provides the regret bound of I-NeurAL. for Rr and Ry respectively, Ry S O Aog
and Ry S ( Tovoloog T). As 4S only provides the regret bound for Rr, to show the advantages of I-NeurAL, we also provide the following lemma for fair comparison.
suppose m Z Lemma 4.1. Given the number of rounds T, for any 6 E (0,1),7 1, (pool((T, k. (L, yn =
O ). and p. satisfies the conditions in Theorem 4.1 Then, with
probability at least - 5 over the initialization of 0, oz. these exists a small enough constant K such that Algorithm 7 can achieve the following regret bound:
6Tv + AV1
RT S O
VT + 2 (0)
(4.3)
V2
and at the same time NT S OIT).
Comparison with 488. Lemma 4.1 shows that I-NeurAL can achieve the regret bound of same complexity for Ry as Rr. Under the same assumption in the over-parameterized neural net- works, without any assumption
D. Theorem 1 in 48 (i.e., the lower-noise condition with exponent 0, and k = 2 is ignored in the binary classification) achieves the following re- gret bound: Rr s Olog det(I + H) ((log det + H) + 52)) where H is the NTK matrix 27 formed by received instances of all T rounds, S vh 'h-'h is a complexity term, and h (h(x,,)).... hxx,))) E R... Note that I-NeurAL and 48 have the same trivial label com-
plexity ((T) in this difficult case. According to the definition of effective dimension in 55 the
above regret bound obtained by can be represented by:
R1 Oddlog(1 + y T(ālog(1 T) + 52) and d log det(( + H)
(4.4)
log(1 + T)
Remark 4.1. The instance-dependent complexity term a reflects the possible minimal regression етгог on the data instances caused by the functions induced by B(0), v) controlled by v. Such complexity term is first introduced in [16]. When is small, the corresponding ball B(0), v/) is small, so fr tends to be large; Otherwise, when v is large, y tends to be small. In particular, when setting (1), Theorem 4.1 and Lemma 4. suggests that if the data can be learned by function in the function class formed by B(0 O(1) with the small training error, then I-NeurAL. will have the regret with order Õ(vT) Note that SS has the complexity term S as well, reflect the boundary of optimal parameters specific to the data.
Remark 4.2. Theorem 4.1 and Lemma 4.1 do not depend d. The effective dimension d was first introduced in 46 and then used in 155) which can be thought of as the non-linear dimensionalities
in the NTK kernel space. However, d can be m + mkd + m²
1) in the worst case, i.e., T (see details in Appendix 9). Eq. 4.4h has the term ((d) and thus the regret bound obtained
d >>>>>
by 4% can explode due to This is because the analysis of 48 closely depends on NTK, i.e., to apply Confidence Ellipsoid bound (Theorem 2 in (I) to the NTK approximation. This procedure inevitably bind their regret bound to the determinant of NTK that can have a very large magnitude. In contrast, Eq. 4.3) does not have the term d, because our analysis does not depend on the NTK approximation and I-NeurAL directly utilizes the property of over-parameterized neural networks, i.e., the convergence error and the generalization concentration bound (Lemma 7.6p. These two terms are independent of d, which paves the way for I-NeurAL remove the curse of d.
7

---

Remark 4.3. Theorem and Lemma 4.1
Improve the regret by multiplicative factor (log T) Note that the analysis of 4% built for binary classification and thus k 2 Theorem 4.1 This improvement stems from the different analysis workflow of I-NeurAL. from Again, our analysis does not rely on NTK approximation and is built on the convergence and
over
48
4.1
and Lemma
48
generalization bound of wide neural networks.
Remark 4.4. Our proof workflow of Theorem and Lemma 4.1 is inspired by 15
Compared
we provide the first regret bound supporting mini-batch SGD with warm-start and a more generic generalization bound (Lemma 7.3) that holds for every arm (class). Moreover, we carry out the performance analysis of query decision-maker (Lemma 7.5), which is
13,
addition.
For the label complexity, Nr has the trivial O(T) complexity which is the same as Theorem 1 in 48 (with the exponent a 0). Because we have consider the worst case where the unique Bayes-optimal class does not exist, i.e., given Xt,i, E [k], there does not exist i" such that h(xx,=) ) > (x),,,) Vi [k] {i*). Therefore, we provide the following analysis and show that RT and Nr can be upper bounded by constants as long as there exists a unique Bayes-optimal class for the input instances, described by the following mild margin assumption.
Assumption 4.2 (e-margin). In round E [T], given an instance x, and the label y/s, then X, has the e-Unique optimal class if there exists such that
Plyt.g Yt,a 1x,)
P(yr. Yt,e xx,) 2
(4.5)
where 1" = arg [a .) is the Bayes-optimal class and 1 = arg maxxe((MM))) ((x,,)) is the second Bayes-optimal class.
Given any E [k:, let be a fixed index, i.e., suppose there exist a policy T; which always select the i-th context (Xt,i, for every round E (T). Then, in round f, we have the collected data by
Q4: M4111
{xr,s, (,, 1.=1 Then, let 1. 0,-1 represent the parameters trained only on H, using
Algorithm with n. and r2. = = fx(xx 1,1
Theorem 4.2. Suppose the instances that are drawn from 'D satisfy Assumption 4.2 Then,
given the number of rounds T. for any E (0,1),7 > 1,e (0, > 0, suppose
m 2 (ppoly(T, k. I,, I,,V)), =12 = O( @(mm)) and l satisfies the conditions in Theorem 4.1
and max inf *E[A]
Σt= (12 (x Φ2)
Then, with probability at least 1 SI }
over the initialization of o O there exists small enough constant k, such that Algorithm I Machieves the following regret bound:
(
GL (6Lu+
Ry <2V2 -
(log(O((T))))
Nr IT
(4.6)
V2
where T= 12(x+1)) 2u490 20044000000+22000CCTTTT classification errors, i.e., L(y,,s, Nt.r) 0, e (T). it holds that
Suppose the Bayes-optimal classifier has zero
Rr < GLu+Ava
+ +2
O
if TTT
V2T
T
(4.7)
R1 = 0, else.
Remark 4.5. Theorem 4.2 provides the upper bound for Ry with order of Olog T)). When other
parameters are fixed, this indicates Ry is upper bounded by Olog T). Moreover, the analysis of Rt indicates that I-NeurAL can achieve the same performance as Bayes-optimal classifier with high confidence after (log T') number rounds (i.e. T T> T). Theorem [48] with the exponent
-> +00 equivalent to Assumption 4.2). Rr Oddlog(1 - -T)) (Tlog(1 + 7) + S2) that still is dependent on d because NTK depends on d.
8

---

Sandem Reaki: /
6000
Basdon
1000
3030
Wrad IITI
Regret
000
Regret
ALP
ALRA
600
600
600
Render
600
1500
Rede-ance
1000
200
ALF
200
300
2000
4000
5030
10000
2000
6000 Rounds
10000
2000
10000 12000
Rounds
Rounds
(a) Phishing
(b) LICNN
(c) Letter
1800
700
Marg's WTTC
1403
600
1400
Regret
500
1200
Rogie
1000
500
Raskas MALALHITO
200
100
2000
6000
6000 Rounds
a000
20000 12000
2000
6000
cos6 Bo08
10000
12010
2000
6360
c0so
5030
10000 12000
Rounds
Rounds
(d) Fashion
(c) MNIST
(f) CIFAR-10
Figure I: Regret comparison on six data sets I-NeurAL outperforms all baselines.
5 Experiments
In this section, we evaluate I-NeurAL on public classification data sets compared with state-of-the- art (SOTA) baselines. Due to the space limit, we only report the main results here and leave the implementation details and parameter sensitivity in the Appendix 10 Codes are available [T
We report the experimental results on the following six data sets: Phishing JJCNN 38 Letter [8] Fashion 40 MNIST 32 and CIFAR-I0 [1. In each round, one instance is randomly drawn from the data set and the algorithm is compelled to make prediction on it. Then, the regret is if the prediction does not match the label: the regret is O, otherwise. At the same time, if the algorithm decides to observe the label, it costs one query budget. As the algorithm may abusively make label queries, we restrict the query budget 3% of the total number of instances in the data set for fair comparison.
The compared baselines are described as follows. (1) Random:
The NN classifier queries the label with a fixed probability p until the query budget is exhausted; (2) Margin: The NN classifier queries the label when the predicted probability is lower than threshold. These two baselines are used in [22]. (3) NeuAL-NTK-E F (Algorithm 1 in 48] This model makes predictions based on the frozen NTK approximation coming with an
Conffience-BBuud(UUC --bsed exploration strategy. (4) NeuAL-NTK-D (Algorithm 3 in 48):: The prediction is made based on the NN classifier with UCB while the NTK is updated accordingly. (5) ALPS i Given class of pre-trained hypotheses, the hypothesis minimizing the logistic loss of labeled and pseudo-labeled data is chosen to make predictions and the label query is based on the disagreement of different hypotheses.
The regret comparison on six data sets is shown in Table and Figure I I-NeurAL consistently outperforms all baselines across all data sets. In particular, I-NeurAL surpasses the best baseline by 31.3%, .3,, 45.6%, 52.2% on IJCNN, MNIST, Fashion respectively. Since NeuAL- NTK-F uses frozen NTK approximation. the new knowledge of each round is barely utilized by the neural network and thus it turns into the worst baseline. NeuAL-NTK-D updates the network parameters with gradient descent and queries the label based on the uncertainty estimation. However, its upper confidence bound is still based on the confidence ellipsoid. Instead. I-NeurAL leverages the representation power of neural networks for both exploitation and exploration. ALPS maintains a class of pre-trained hypotheses and tries to make the best decisions based on these hypotheses. Nevertheless, the model parameters are fixed before the online active learning process. Hence, ALPS
Results.
http:///ghchubb.cc//aatttooo//// csie. .tu.

---

Phishing
UCNN
Letter
Fashion
MNIST
CIFAR-TO
Random
1095
845
3519
444
1599
1910
Margin
704
974
3164
247
1327
1474
NeuAL-NTK-F
4898
2684
6066
6001
6192
NeuAL-NTK-D
796
744
3410
742
1239
1700
ALPS
978
683
3108
379
1433
1662
I-NeurAL.
689 2.1%)
469(1 31.3%)
25 17.3%)
118(1
52.2%)
674(1 45.6%)
1372(1 6.9%)
Table 1: Total regret comparison.
able take the new knowledge obtained by queries into account and its performance highly restricted by the hypothesis class. Although Margin algorithm is simple and straightforward, it exhibits great empirical performance in practice. This observation is consistent with other studies [50] [22]. However. Margin algorithm does not incorporate the exploitation portion and the query criterion is not adaptive to difference instances, thus still outperformed by I-NeurAL.
6 Conclusion
In this paper, we introduce two regret metrics and propose a novel neural- algorithm (I-NeurAL) tailored for the streaming setting non-pas con-aaametrric active learning. We carefully design its explo- ration strategy, query socision-maker update rules, and training procedure, which lead to both the theoretical and empirical improvement compared SOTA 48 In the regret analysis, we provide an instance-dependent performance guarantee. On the other hand, we empirically show that I-NeurAL consistently achieves better accuracy under the same query budget than the strong baselines including the SOTA work
48
and 22
Acknowledgements
This work is supported by NSF (IS--1947203, IIS-2117902, IIS-2137468, IIS-2002540, DMS- 2134079, IIS-2131335, OAC-2130835, and (BI1-2011898) DARPA (IR001121CO11 ARO (W911NF21 10088), and C3.ai. The views and conclusions are those of the authors and should not be interpreted representing the official policies of the funding agencies or the government.
References
[1] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
[2] Z. Allen-Zhu. Y. Li. and Z. Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252. PMLR. 2019.
[3] S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, pages 8141-8150, 2019.
[4] Ash, S. Goel, A. Krishnamurthy, and S. Kakade. Gone fishing: Neural active learning with fisher embeddings. Advances in Neural Information Processing Systems, 34, 2021.
[5] J. T. Ash, C. Zhang, A. Krishnamurthy, J. Langford, and A. Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint UrXiv:1906.0338 2019.
[6] P. Awasthi, M. F. Balcan, and P. M. Long. The power localization for efficiently learning linear separators with noise. In Proceedings of the forty-sixth annual ACM symposium Theory of computing, pages 458, 2014.
[7] M.-F Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-88) 2009.
[8] M.-F. Balcan, A. Broder, and T. Zhang. Margin based active learning. International
Conference Computational Learning Theory, pages 35-50. Springer, 2007.
10

---

[9] Y. Ban and J. He. Generic outlier detection in multi armed bandit. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 913-923, 2020.
[10] Y. Ban and He. Local clustering in contextual multi-armed bandits. Proceedings of the Web Conference 2021, pages 2335-2346, 2021.
[11] Y. Ban, He, and C. B. Cook. Multi-face contextual bandits: A neural network perspective. In The 27th ACM SIGKDD Conference Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18. 2021, pages 35-45, 2021.
[12] Y. Ban, Y. Qi, T. Wei, and J. He. Neural collaborative filtering bandits via meta learning ArXiv abs/2201. 13395, 2022.
[13] Y. Ban, Y. Yan, A. Banerjee, and J. He. EE-net: Exploitation-exploratoo neural networks in contextual bandits. In International Conference on Learning Representations, 2022.
[14] A. Beygelzimer, S. Dasgupta, and J. Langford. Importance weighted active learning. In Proceedings of the 26th anmual international conference on machine learning, pages 49-56, 2009.
[15] K. Brinker. Incorporating diversity in active learning with support vector machines. In Pro- ceedings the the 20th international conference on machine learning (ICML-03), pages 66.66, 2003.
[16] Y. Cao and Q Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 32: 10836-168, 2019.
[17] G. Citovsky, G. DeSalvo, C. Gentile, L. Karydas, A. Rajagopalan, A. Rostamizadeh, and S. Kumar. Batch active learning scale. Advances in Neural Information Processing Systems, 34, 2021.
[18] G. Cohen, S. Afshar, Tapson, and A. Van Schaik. Emnist: Extending mnist handwritten letters. In 2017 international joint conference on neural networks (LJCNN), pages 2921-2926. IEEE, 2017.
[19] D. A. Cohn, Z. Ghahramani, and M. Jordan. Active learning with statistical models. Journal of artificial intelligence research, 4:129-145, 1996.
[20] A. Culotta and A. McCallum, Reducing labeling effort for structured prediction tasks. In AAAI, volume 5, pages 746-751, 2005.
[21] S. Dasgupta, A. T. Kalai, and C. Monteleoni. Analysis of perceptron-based active learning, In International conference on computational learning theory, pages 249-263. Springer, 2005.
[22] G. DeSalvo, C. Gentile, and T. S. Thune. Online active learning with surrogate loss functions. Advances Neural Information Processing Systems, 34, 2021.
[23] I. Goodfellow, Y. Bengio, and A. Courville. Deep learning. MIT press, 2016.
[24] S. Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th international conference on Machine learning, pages 353-360, 2007.
[25] S. Hanneke et al. Theory of disagreement- based active learning. Foundations and Trends@ in Machine Learning, 7(2-3):131 -009, 2014.
[26] S. Hanneke and L. Yang. Surrogate losses in passive and active learning. Electronic Journal of Statistics, 13(2)4646-44000 2019.
[27] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances neural information processing systems, pages 8571-8551 1-5800, 2018.

---

[28] A. J. Joshi, F. Porikli, and N. Papanikolopoulos. Multi-class active learning for image classifica- tion. In 2009 ieee conference on computer vision and pattern recognition, pages 2372-2379. IEFF, 2009.
[29] A. Kapoor, K. Grauman, R. Urtasun, and T. Darrell, Active learning with gaussian processes for object categorization. In 2007 IEEE 1 11th international conference on computer vision, pages 1-8. IEFE, 2007.
[30] Y.-Y. Kim, K. Song, J. Jang, and I.-c Moon. Lada: Look-ahead data acquisition via aug- mentation for deep active learning. Advances in Neural Information Processing Systems, 34, 2021.
[31] A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[32] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 36(11):2278-2324 1998.
[33] D. D. Lewis and W. A. Gale. A sequential algorithm for training text classifiers. In SIGIR 94, pages 3-12. Springer, 1994.
[34] A. Locatelli, A. Carpentier, and S. Kpotufe. Adaptivity to noise parameters in nonparametric active learning. In Proceedings of the 2017 Conference on Learning Theory, PMLR, 2017.
[35] S. Minsker. Plug-in approach to active learning. Journal of Machine Learning Research, 13(1).
2012.
[36] J. Moon, J. Kim, Y. Shin, and S. Hwang. Confidence-awwnn learning for deep neural networks. In international conference on machine learning, pages 7034-7044. PMLR, 2020.
[37] S. Mussmann and P. S. Liang. Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss. Advances in Neural Information Processing Systems, 31, 2018.
[38] D. Prokhorov. Ijenn 2001 neural network competition. Slide presentation in IJCNN, 1997)338,
2001.
[39] Y. Qi, Y. Ban, and J. He. Neural bandit with arm group graph. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '22, page 1379-1389, New York, NY, USA, 2022. Association for Computing Machinery.
[40] P. Ren, Y. Xiao, X. Chang, P.-Y. Huang, Z. Li, B. B. Gupta. X. Chen, and X. Wang. A survey of deep active learning, ACM Computing Surveys (CSUR), 54(9):1-40, 2021.
[41] N. Roy and A. McCallum. Toward optimal active learning through monte carlo estimation of error reduction. ICML, Williamstown, 2:441-44: 2001.
[42] C. Schröder and A. Nickler. A survey of active learning for text classification using deep neural networks. arXiv preprint arXiv:2008.07267, 2020.
[43] O. Sener and S. Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv: 00489, 2017.
[44] B. Settles. Active learning literature survey. 2009.
[45] W. Tan, L. Du, and W. Buntine. Diversity enhanced active learning with strictly proper scoring rules. Advances in Neural Information Processing Systems, 34, 2021.
[46] M. Valko, N. Korda, R. Munos, I. Flaounas, and N. Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv: 6869, 2013.
[47] H. Wang, W. Huang, A. Margenot, H. Tong, and J. He. Deep active learning by leveraging training dynamics. arXiv preprint /0.086/1 2021.
[48] 7. Wang, Awasthi, C. Dann, A. Sekhari, and C. Gentile. Neural active learning with performance guarantees. Advances in Neural Information Processing Systems, 34, 2021.
12

---

[49] H. Xiao, K. Rasul, and R. Vollgraf. Fashion mnist:: novel image dataset for benchmarking machine learning algorithms, 2017.
[50] Y. Yang and M. Loog. A benchmark and comparison of active learning for logistic regression. Pattern Recognition, 83:401-415,, 2018.
[51] C. Zhang. Efficient active learning of sparse halfspaccs.. In Conference on Learning Theory. pages 1856-1880. PMLR, 2018.
[52] C. Zhang, J. Shen, and P. Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. Advances Neural Information Processing Systems, 33:7184-7197, 2020.
[53] W. Zhang, D. Zhou, L. Li, and Q. Gu. Neural thompson sampling. In International Conference on Learning Representations, 2021.
[54] Y. Zhang, H. Tong, Y. Xia, Y. Zhu, Y. Chi, and L. Ying. Batch active learning with graph neural networks via multi-agent deep reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, 36:91 18 18-9126, 2022.
[55] D. Zhou, L. Li, and Q. Gu. Neural contextual bandits with babebased exploration. In Interna- tional Conference on Machine Learning, pages 1 11492-11 1502. PMLR, 2020.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [No]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] The random seed fixed to 42 in all the experiments. (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're
using/curating? [Yes]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "l9UmBD0eghd", "reviewer": "Reviewer_7AUC", "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. \n", "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.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- 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.\n- 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.\n\nWeaknesses\n- 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.\n- See questions.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XzDOQq_B-Ts", "reviewer": "Reviewer_KtaT", "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].\n\n[1] https://proceedings.neurips.cc/paper/2021/hash/3dcaf04c357c577a857f3ffadc555f9b-Abstract.html ", "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?\n* What are some key novelties relative to the EE-Net paper [2]?\n* 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", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n* The topic of active learning with provable guarantees, especially for neural networks, is of high importance and interest to the wider ML community\n* The contributions and improvements relative to [1] – as outlined in the summary above – are significant \n* The techniques and corresponding theoretical analysis seem sound \n* Empirical evaluations are presented that support the improved effectiveness of the proposed work over [1] and other state-of-the-art approaches\n\n## Weaknesses\n* 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]. \n* 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\n* 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\n\n[1] https://proceedings.neurips.cc/paper/2021/hash/3dcaf04c357c577a857f3ffadc555f9b-Abstract.html \n\n[2] https://arxiv.org/pdf/2110.03177.pdf \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "USlJMqY1ZS0", "reviewer": "Reviewer_d9Zc", "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.\n", "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.\n\nI am willing to raise my scores provided some of the above concerns about empirical results are addressed.", "limitations": "More or less suffcient.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The theoretical analysis is novel with stronger bounds over prior work. I find the theoretical results and the utilization of generalization bounds very interesting.\n2. Empirically, the authors conducted experiments over a wide range of datasets and the algorithm is computationally efficient in practice.\n\nWeaknesses:\n1. 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.\n2. 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.\n\nMinor Suggestion:\nAlthough 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2zDURxpA0U", "reviewer": "Reviewer_aMrL", "summary": "The paper addresses active learning, one of the field's essential problems.\nThis work extends EE-Net for active learning and provides its regret analysis.\nCompared with the closest work, the authors show a better regret bound.\nExperimental results also show the proposed algorithm outperforms previous work.\n", "questions": "Questions\n- Is there a difference between Derivative-Context (DC) Embedding (Definition 3.1) and the input of $f_2$ in EE-Net?\n- Although $\\beta_{t}$ is decreased as $\\sqrt(t)$ in Algorithm 1, how is $beta_t$ controlled in the experiments?\n- Is the grid search over all hyperparameters conducted for the same datasets in which the regret evaluations are conducted?\n- 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?\n\nMinor Comments\n- In equation (7.28), the end parentheses of f are missing.\n- typo: lesat -> least in the following sentence of equation (7.28).\n- 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.\n- In equation (7.78), a \\max seems to be \\min.\n- In Lemma 7.13, $\\theta_t^{(k)}$ is not used in the main text.\n- In Lemma 7.13, one of the equation number is missing.\n- 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}^*)$.\n- In Lemma 8.2, $\\cal{H}_{t-1}$ is not used in the main text.\n", "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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The regret analysis shows the regret bound improving by O(log T) and removing the curse of dimensionality and the complexity of the function.\n- This work provides theoretical justification for the proposed algorithm.\n- The empirical results also prove the advantage of the proposed method.\n\nWeaknesses\n- The proposed algorithm and the result of the regret analysis are a straightforward extension of EE-Net, so their novelty is a little limited.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept