Neural Active Learning with Performance Guarantees
Authors: Zhilei Wang
Pranjal Awasthi
Christoph Dann
Ayush Sekhari
Claudio Gentile
Venue: NeurIPS 2021 Poster (2021)
Keywords: Active learning
Deep Neural Networks
Neural Tangent Kernel
Selective Sampling
theoretical guarantees

Abstract: We investigate the problem of active learning in the streaming setting in non-parametric regimes, where the labels are stochastically generated from a class of functions on which we make no assumptions whatsoever. We rely on recently proposed Neural Tangent Kernel (NTK) approximation tools to construct a suitable neural embedding that determines the feature space the algorithm operates on and the learned model computed atop. Since the shape of the label requesting threshold is tightly related to the complexity of the function to be learned, which is a-priori unknown, we also derive a version of the algorithm which is agnostic to any prior knowledge. This algorithm relies on a regret balancing scheme to solve the resulting online model selection problem, and is computationally efficient. We prove joint guarantees on the cumulative regret and number of requested labels which depend on the complexity of the labeling function at hand. In the linear case, these guarantees recover known minimax results of the generalization error as a function of the label complexity in a standard statistical learning setting.

Neural Active Learning with Performance Guarantees
Zhilei Wang New York University
Pranjal Awasthi
Google Research
New York, NY 10012 zhilei zhileivang92@mmil..c
New York, NY 10011
pranjalawasthi @ google.com
Christoph Dann
Ayush Sekhari
Claudio Gentile Google Research New York, NY 1001
Google Research New York, NY 10011
Cornell University Ithaca, NY 14850
chrisdann @ google.com
ayush.sekharic gmail.com
geentle@@ooglc..o
Abstract
We investigate the problem of active learning in the streaming setting in non- parametric regimes, where the labels are stochastically generated from class functions which make assumptions whatsoever. We rely recently proposed Neural Tangent Kernel (NTK) approximation tools to construct a suitable neural embedding that determines the feature space the algorithm operates on and the learned model computed atop. Since the shape of the label requesting threshold tightly related to the complexity of the function be learned, which is a- a-priori unknown, we also derive a version of the algorithm which is agnostic to any prior knowledge. This algorithm relies on a regret balancing scheme to solve the resulting online model selection problem, and is computationally efficient. We prove joint guarantees on the cumulative regret and number of requested labels which depend on the complexity of the labeling function at hand. In the linear case, these guarantees recover known minimax results of the generalization error as a function of the label complexity in a standard statistical learning setting.
Introduction
Supervised learning is fundamental paradigm in machine learning and is at the core of modern breakthroughs in deep learning (29]. A machine learning system trained via supervised learning requires access to labeled data collected via recruiting human experts, crowdsourcing, or running expensive experiments. Furthermore, the complexity of current deep learning architectures grows, their requirement for labeled data increases significantly. The area active learning aims to reduce this data requirement by studying the design of algorithms that can learn and generalize from small carefully chosen subset of the training data [13 [4)].
The two common formulations of active learning pool based active learning, and sequential (or streaming) active learning. the pool based setting [30], the learning algorithm has access to large unlabeled set of data points, and the algorithm can ask for a subset of the data to be labeled. In contrast, in the sequential setting, data points arrive in a streaming manner, either adversarially or drawn i.i.d. from distribution, and the algorithm must decide whether to query the label of given point or not [4]
From a theoretical perspective, active learning has typically been studied under models inspired by the probably approximately correct (PAC) model of learning [41]. Here one assumes that there is pre-specified class H of functions such that the target function mapping examples to their labels
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

either lies in H. or has a good approximation inside the class. Given access to unlabeled samples generated i.i.d. from the distribution, the goal query for a small number of labels and produce a hypothesis of low error.
In the parametric setting, namely, when the class of functions H has finite VC-dimension (or finite disagreement coefficient) [21], the rate of convergence of active learning, i.c., the rate of decay of the regret as function of the number of label queries (N), is of the form v/ N + e- VNV where is the population loss of the best function in class H. This simple finding shows that active learning behaves like passive learning when O, while very fast rates can only be achieved under low noise
(V R 0) conditions. This has been worked out in, e.g.. 19 15 5
38
While the parametric setting comes with methodological advantages, the above shows that in order to unleash the true power of active learning, two properties are desirable: (1) A better interplay between the input distribution and the label noise and, (2) a departure from the parametric setting leading us to consider wider classes of functions (so as to reduce the population loss v to close to 0). To address the above, there has also been considerable theoretical work in recent years on non non- para-aeatttic active learning [00 33 31]. However, these approaches suffer from the curse of dimensionality and do not lead to computationally efficient algorithms. A popular approach that has been explored empirically in recent works is to use Deep Neural Networks (DNNs) to perform 44) ). While these works empirically demonstrate the power of the DNN-based approach to active learning, they do not come with provable guarantees. The above discussion raises the following question: Is provable and computationally efficient active learning
active learning (e.g.. (37 26 39
possible in non pon-paaaettric settings?
We answer the above question in the affirmative by providing the first, to the best of our knowledge, computationally efficient algorithm for active learning based on Deep Neural Networks. Similar to non conamaaamttric active learning, we avoid fixing function class a- a-priori. However, in order to achieve computational efficiency, we instead propose to use wver-parameterized DNNs, where the amount of over-parr parameterization depends on the input data at hand. We work in the sequential setting, and propose a simple active learning algorithm that forms an uncertainty estimate for the current data point based on the output of DNN, followed by gradient descent step to update the network parameters if the data point is queried. We show that under standard low-noise assumptions 32 our proposed algorithm achieves fast rates of convergence.
In order to analyze our algorithm, we use tools from the theory of Neural Tangent Kernel (NTK) approximation 24 2 18 that allows us to analyze the dynamics of gradient descent by considering lincarization of the network around random initialization. Since we study the non- parametric regime, the convergence rates of our algorithm depend on a data-dependent complexity term that is expected to be small in practical settings, but could be very large in worst-case scenarios. Furthermore, the algorithm itself needs an estimate of complexity term in order to form accurate uncertainty estimates. We show that one can automatically adapt to the magnitude of the unknown complexity term by designing novel model selection algorithm inspired by recent works in model selection in multi- armed bandit settings [36 (35. Yet, several new insights are needed to ensure that the model selection algorithm can simultaneously achieve low generalization error without spending significant amount of budget on label queries.
2 Preliminaries and Notation
Let X' denote the input space, y the output space, and D an unknown distribution over X' x y. We denote the corresponding random variables by x and y. We also denote by Dx the marginal distribution of 'D over X, and by Dylm the conditional distribution of random variable given I Zg. Moreover, given function f (sometimes called a hypothesis or a model) mapping X' y. the conditional population loss (often referred to as conditional risk) of f is denoted by L(f zz), and defined as [[f x>) [
y) xz). where E: y x y -> [0, 1] is loss function. For ease of presentation, we restrict to binary classification setting with 0-1 loss, whence y = [11,+1}, and {(a, y) = Ia + y} E {0. 1). 1[-} being the indicator function of the predicate at argument. When clear from the surrounding context, we will omit subscripts like "y ~ Dylz" " from probabilities and expectations.
2

---

We investigate a non- parapaamettrcc setting of active learning where the conditional distribution of given x is defined through an unknown function h X [0. 1] such that
Ply 1 x)) h((2,, 0))
(P = -
h((O,=)),
where 0 E X, T2) denotes the concatenation (or pairing) of the two instances 21 and 22 (so that (x,0) and (0,z) r) are in X²) and, for all x E X we have (( 0)) + h((0, x)) = 1. We make no explicit assumptions on h. other than its well-behavedness w.r.t. the data { i= at hand through the formalism of Neural Tangent Kernels (NTK) see below. As simple example, in the linear case, X' is the d-dimensional unit ball, h(;;)) :) is parametrized by unknown unit vector O E Rd, and h((21, x2)) 1-((0- (((0)-)))(01.))))) so that (((x, 0)) = (+(0.m)) and h((0,z)) (9,a)) where (.,
2
2
is the usual dot product in R
We consider streaming setting of active learning where, at each round E [T]] {l...., T). a pair (x,, y1) E X' x y is drawn i.i.d. from D. The learning algorithm receives as input only zt, and is compelled to both issue a prediction a, for Y and, at the same time, decide on-the-fly whether not to observe yt- These decisions can only be based on past observations. Let E, denote the conditional expectation [ (æ1, 31) (Zt-1, 11-1), 22), and we introduce the shorthand
(Iz, 0)
if =0=1
Ft,a
(0,
if f-a=1l
[11] = 1 h(zr,a), for all E V. We quantify the accuracy of the learner's predictions through its (pseudo) regret, defined as
Notice that with this notation E[E(a, y1)
RT = ) (Ble(aa 91) æd 1B 31) 2il) = Σ (h(z1a;)) h(Zr,a))
where or is the Bayesian-optimal classifier on instance Vt. that is, oj arg max.ey h(Tr,.). Additionally, we are interested in bounding the number of labels Ny the algorithm decides to request. Our goal is to simultaneously bound Rr and Nr with high probability over the generation of the sample {(Te, yt) 3t]]ti.....
Throughout this work, we consider the following common low-noise condition on the marginal distribution Dx (Mammen- (Mammen-Tsybakov Tsybakov low noise condition 32)): There exist absolute constants >
and a 2 0 such that for all E (0, 1/2) we have
((IN((2,)) 0)) - 1 <<) Sc
In particular, a oo gives the so-called hard margin condition (() at the opposite extreme, exponent a = 0 (and = 1) results in no assumptions whatsoever on Dx For simplicity, we shall assume throughout that the above low-noise condition holds o 1.
while,
Our techniques are inspired by the recent work [45) from which we also borrow some notation. We learning the class of functions {h} by means of fully connected neural networks
() wmw, (W..
where a is ReLU activation function (z)) max 2), m is the width of the network and > 2 is its depth. In the above, 0 E IR collectively denotes the set of weights {Wi, W2,..., W.) of the network, where p + 2md + m2 2) is their number, and the input x at training time should be thought of as some o E X²2
With any depth-n network and data points (Ir,a Its.... a= associate a depth-n NTK matrix as follows [24] First, rename (zr,a)t=1,....2 ". a=#1 (x(1) /i= Then define matrices
11) and then, for any & < n and i,j = 1,...,,? 2T, introduce the bivariate covariance matrix
H (1)
xTx i-==
[(1)
(1)
xTx2T
with --=
(z x00))
i.j=1
- = (1)))
A more general formulation requires the above to hold only for e S co. where ca E (0, 1/2) is a third parameter. We shall omit this extra parameter from our presentation.
3

---

by which we recursively define
(k+1) 2E (o. Dij
and
A(k+ 2H (v.0) ( [1u 2 0) 11 2 01} - (k+11
2.
The 2T: x 2T-ddmeesionnll matrix H- ((H()) ()
E(() is called the Neural Tangent Kernel (NTK)
matrix of depth n (and infinite width) over the set of points (It..tt.....T..== The reader is referred to [24) for more details on NTK.
In order to avoid heavy notation, we assume || = for all t. Matrix H is positive semi-definite by construction but, is customary in the NTK literature (e.g., 9 [7]), assume it is actually positive definite (hence invertible) with smallest eigenvalue Ag > 0. This is a mild assumption that can be shown to hold if no two vectors F, are aligned to each other.
We measure the complexity of the function at hand way similar to 45 Using the same rearrangement of (=r,))ttl..,, a==1 into {zx(0) [==()))=1...022) :==,....27 as above, let h be the 2T -imdiimnsio (column) vector whose i-th component is (1)) Then, we define the complexity ST. of h over "tt....t w.r.t. an NTK of depth n as ST (h) vh - Notice that this notion of (data-dependent) complexity is consistent with the theoretical findings of 22. who showed that for two-layer network the bound on the generalization performance is dominated by y H where the vector of labels. Hence if y is aligned with the top eigenvectors of H the learning problem becomes easier. In our case, vector h plays the role of vector Also observe that (T,n(h) (h) can in general as big as linear in (in which case learning becomes hopeless with our machinery). In the special case where h belongs to the RKHS induced by the NTK, one can upper bound ST,, (h) by the norm of h in the RKHS.
The complexity term ST.:(h) is typically unknown to the learning algorithm, and it plays a central role in both regret and label complexity guarantees. Hence the algorithm needs to learn this value as well during its online functioning. Apparently, this aspect of the problem has been completely overlooked by 45 (as well as by earlier references on contextual bandits in RKHS, like [22,, where a (tight) upper bound on ST. (h) is assumed to be available in advance. We will cast the above as a model selection problem in active learning, where we adapt and largely generalize active learning
the regret balancing technique from [36 35
In what follows, we use the short-hand g(a;;) 0) Val(a, and, for vector g RP and matrix Z E RPx, we often write Vg Zg as ||g| Iz, so that (h) = ||h| -
2.1 Related work
The main effort in theoretical works in active learning is to obtain rates of convergence of the population loss of the hypothesis returned by the algorithm as a function of the number N of requested labels. We emphasize that most of these works, that heavily rely on approximation theory, are not readily comparable to ours, since our goal here is not to approximate h through DNN on the entire input domain, but only on the data at hand.
As we recalled in the introduction, in the parametric setting the convergence rates of the regret are of the form 1/2 + --VN where is the population loss of the best function in class H. Hence, active learning rates behave like the passive learning rate N-1/2 when > O, while fast rates can only be achieved under very low noise (v 0) conditions. In this respect, relevant references include 20 27 where, c.g., in the realizable case (i.c.. when the Bayes optimal classifier lies in H), minimax active learning rates of the form N - are shown to hold for adaptive algorithms that do not know beforehand the noise exponent a. In non-parametric settings, a comprehensive set of results has been obtained by [3I], which builds on and significantly improves over earlier results from (33 Both papers work under smoothness (Holder continuity/mmoothnss) assumptions. In addition,
requires Dx to (qnfsi-) on = [0, 1]d. In (31 the minimax active learning rate N T2 is shown to hold for 3-Holder classes, where exponent & plays the role of the complexity of the class of functions to learn, and d the input dimension. This algorithm is adaptive to the complexity parameter B, and is therefore performing a kind of model selection. Notice that minimax rates in the

---

parametric regime are recovered by setting 8 - oc. Of a somewhat similar flavor is an earlier result by (27, where a convergence rate of the form N - is shown, being &t the metric entropy of the class (again, a notion of complexity). A refinement of the results in [3]] has recently been obtained by [4]] where, following [.. a more refined notion of smoothness for the Bayes classifier adopted which, however, also implies more restrictive assumptions on the marginal distribution Dx.
T=
As opposed to those bounds, our bounds are data-dependent, in that all relevant quantities appearing in the bounds will be random variables depending on the data at hand (which are themselves random). One may attempt to turn these into data-ind -nstedindeeedent results (like in most of the papers we cited above) by. c.g., establishing bounds on that hold in expectation or with high probability over the random draw of the data, but this theory is currently unavailable in the NTK literature (as far as we know). Very recently some results have appeared for certain special cases, see (33 for example. But such results are too embryonic in nature to allow us full- flldefleged comparison.
Model selection of the scale of a Nearest-Neighhor- based active learning algorithm is also performed in (88), whose main goal is achieve data-dependent rates based on the noisy-margin properties of the random sample at hand, rather than those of the marginal distribution. Their active learning rates not directly comparable ours and, unlike our paper, the authors work in a pool-based scenario, where all unlabeled points are available beforehand. Finally, an interesting investigation in active learning for pere-parametrized and interpolating regimes is contained in [25]. The paper collects a number of interesting insights in active learning for 2-layer Neural Networks and Kernel methods, but it restricts to either uniform distributions on the input space or cases of well-clustered data points, with no specific regret and query complexity guarantees, apart from very special (though insightful) cases.
3 Basic Algorithm
Our first algorithm (Algorithm I uses randomly initialized, but otherwise frozen, network weights (a more refined algorithm where the network weights are updated incrementally is described and analyzed in the appendix). Algorithm jis an adaptation to active learning of the neural contextual bandit algorithm of [45) and shares similarities with an earlier selective sampling algorithm analyzed in [16] for the linear case. The algorithm generates network weights 8g by independently sampling from Gaussian distributions of appropriate variance, and then uses fg to stick with a gradient mapping <(-) which will be kept frozen from beginning to end. The algorithm also takes as input the complexity parameter = ST... (h) of the underlying function h satisfying (T). We shall later on remove the assumption of the prior knowledge of ST... (h). In particular, removing the latter, turns out to be quite challenging from a technical standpoint, and gives rise to a complex online model selection algorithms for active learning in parpaaametric regimes.
At each round t, Algorithm ! receives an instance I, E X, and constructs the two augmented vectors It, = (Iz, 0) and -t = (0,Iz) (intuitively corresponding to the two "actions" " of a contextual bandit algorithm). The algorithm predicts the label yı associated with 24 by maximizing over a y an upper confidence index Una stemming from the linear approximation h(zz,a) z (m 0 0o) subject to ellipsoidal constraints C.-1, as in standard contextual bandit algorithms operating with the frozen mapping e(.). In addition, in order to decide whether or not to query label yr. the algorithm estimates its own uncertainty by checking to what extent Ur,, is close to 1/2. This uncertainty level is ruled by the time-varying threshold B, which is expected to shrink to O as time progresses. Notice that B, is function of 7- which in turn includes in its definition the complexity parameter S. Finally, if yt is revealed, the algorithm updates its least-squares estimator 0, by a rank-one adjustment of matrix Z, and an additive update to the bias vector br. No update is taking place if the label is not queried. The following is our initial building block
Theorem 1. Let Algorithm D be run with parameters 8, S, m. and n. on an i.id. sample (x1, v1)...,, YT) ~ D, where the marginal distribution Dx fulfills the low-noise condition with exponent a 2 0 w.r.. a function that satisfies ( and such that V2ST (h) < S. If m = poly(T, n, Ao logg(1) (1/8)). then with probability at least 8 the cumulative regret Ry and
2 All proof's are in the appendix.
5

---

Algorithm 1: Frozen NTK Selective Sampler.
Input: Confidence level complexity parameter S, network width m, and depth ni Initialization:
Generate each entry of W independently from (0,, 2/m), for k E [n - 1], and each entry of W,, independently from (1,
Define ((x) - g(æ; 0o)/ Vm, where 0o- (Wi,.... Wn) E R the (frozen) weight vector of the neural network so generated;
Set Zu = E RPXP, by = 0 E
for t 1.2.....
Observe instance ia E X' and build Deaa X2, for E < [-1,+]
Set C,-1 (0: |00 0e-1llz-11 S kmn with W- Vlog det Zz-1 + log S
Set
Ula m max (0( 0o) Vm( - Oo) + 7 + DECi-1
Predict 0, arg my U
Set I, = 1((UVra, - 1/2 < B1} E (0,1)
with
B. = BB(S) = 2 22
I =1
Query E V, and set loss l, = A10e, Wc) Update
Zi = Zi-1 + ((Ir,,))((z,,))
b, b (1 f (I)
0: Zi bt/vm + 0o
else
Ze 7 bt b 0, 01- 1, ?t = 7t-,, Ct Ct-1
the total number of queries NT are simultaneously upper bounded as follows:
Pr RT= 00=0
Lij
a+1 a+2
(L + log(1/0) 52)
0+2 Totz + (og(logT/o)
NT =
LH
0+2
LH + log(1/0) + S2) at2
T Taiz + log(log
where Lu = log de + H), H being the NTK matrix of depth n over the set of points {II,a "tl,,,,,,....Taa a-11
The above bounds depend, beyond time horizon T, on three relevant quantities: the noise level a, the complexity parameters S and the log-determinant quantity LH. Notice that, whereas S essentially quantifies the complexity of the function h to be learned, Lu measures instead the complexity of the NTK itself, hence somehow quantifying the complexity of the function space we rely upon learning h. is indeed instructive to see how the bounds in the above theorem vary as a function of these quantities. First, as expected, when 0 we recover the usual regret guarantee R O(VT), more precisely a bound of the form Rr O([ VTzS) /T), with the trivial label complexity Nr = OT)). At the other extreme, when a - Do we obtain the guarantees RT = Nr = O(LH + 52)). In either case, if f is "too complex" when projected onto the data, that is, if (h. = QTT), then all bounds become vacuous At the opposite end of the spectrum, [h} is simple, like a class of linear functions with bounded norm in d-dimensional space, and the network depth n is 2 then ST (h) O(1), and L O(d T), hence recovering the rates reported in [6] for the linear case. The quantity I, is tightly related to the decaying rate of the eigenvalues of the NTK matrix H. and is logaithgaii in T in several important cases 422 One relevant example is discussed in [43], which relies on the spectral characterization of NTK in 7 [
If n = and all points (i) concentrate on dg dimieennso subspace of the RKHS spanned by the NTK, then Lи (dg log T).
TThe same happens, e.g., the regret bounds in 45

---

It is also important to stress that, via a standard online-to-beln conversion, the result in Theo- rem Il can be turned a compelling guarantee in traditional statistical learning setting. where the goal is to come up at the end of the T rounds with a hypothesis f whose population loss [(f) = Ex [T.[ [x)] exceeds the Bayes optimal population loss D [((())))) by a vanishing quantity. Following [T6], this online-to-batch
Ex [max((((xr,), h(),,))()))))))))))))))))))))))) bb
algorithm will simply run Algorithm | by sweeping over the sequence {(2,, (e),, be) only once, and pick one function uniformly at random among the sequence of predictors generated by Algorithm [ during its online functioning, that is, among the sequence (U)(r))e....)) where (+(z) = arg maxagy maxsec.-1 (a)
0 - Oo). with x;, = (x, 0) and x (0, This
randomized algorithm enjoys the following high- probbabiibiii excess risk guarantee
((
LH La log(1/0) + 5²)
o42
log log log (T/8)
(i- =
T
T
Combining with the guarantee on the number of labels Nr from Theorem I (and disregarding log factors), this allows us to conclude that the above excess risk can be bounded as a function of Nr as
Lu (Ln + 8²) NT
a+1
where (In + 52) plays the role of a (compound) complexity term projected onto the data
C1...., 2T at hand. When restricting to VC-classes, the convergence rate Nr 2+1
is indeed the best rate (minimax rate) one can achieve under the Hammen-Tsybaken low-noise condition with exponent 16)..
(see, c.g. [10 20
Yet, since we are not restricting to the parametric case, both Lи and, more importantly, S can be a function of T. In such cases, the generalization bound in 2 can still be expressed as function of Nr alone, For instance, when L, is poly- logarithiti in and 5 = O)T", for some 8 E [0, 1),
(1-))++1)
one can easily verify that (2) takes the form Nr
2-
(again, up to log factors).
In Section the appendix, we extend all our results the case where the network weights are not frozen. but are updated on the fly according to a gradient descent procedure. In this case, in Algorithm| 1 the gradient vector x(x) = (2x; 0o)/ /m will be replaced by (e(x)) = g(r; (// //mm where 6₂ not the linear-least squares estimator 0₂ = Z b He/ym + lo, as in Algorithm but the result of the DNN training on the labeled data {(zk, yk) k I t, I 1} gathered so far.
4 Model Selection
Our model selection algorithm is described in Algorithm 2 The algorithm operates on a pool of base learners of Frozen NTK selective samplers like those in Algorithm [ each member in the pool being parametrized by a pair of parameters (St, d.), where S; plays the role of the (unknown) complexity parameter ST,, (h) (which was replaced by S in Algorithm D. and d; plays the role of an (a-priori unknown) upper bound on the relevant quantity Σ GeTT:h= A Te, BB, that is involved in the analysis (see Lemma and Lemma 7 in Appendix I... This quantity will at the end be upper bounded by term of the form LH (LH + log(T/0) + (h)) whose components LH and S7 (h) are initially unknown to the algorithm.
Algorithm 2 maintains over time set M, of active base learners, and a probability distribution Pa over them. This distribution remains constant throughout a sequence of rounds between one change to .M, and the next. We call such sequence of rounds an epoch. Upon observing 2t, Algorithm 2 selects which base learner rely upon in issuing its prediction a, and querying the label y:. by drawing base learner i, E M, according to Pt-
Then Algorithm 2 undergoes series of carefully designed elimination tests which are meant rule out mis-specified base learners, that is, those whose associated parameter S; is likely to be smaller than (T, while retaining those such that S, > (h),.h). These tests will help keep both the regret bound and the label complexity of Algorithm 2 under control. Whenever, at the end of some
'Observe that this is data- dependent bound, in that the RHS is random variable. This is because both L and S may depend on 21, Bis..e TT.
7

---

round t, any such test triggers, that is, when it happens that |Me+1l < [Mi] at the end of the round, a new epoch begins, and the algorithm starts over with a fresh distribution Pr+1 # P::
The first test ("disagreement test") restricts to all active base learners that would not have requested the label if asked. As our analysis for the base selective sampler (see Lemma in Appendix A.1 shows that a well-specified base learner does not suffer (with high probability) any regret on non-queried rounds, any disagreement among them reveals mis- piisspecifiiation, thus we eliminate in pairwise comparison the base learner that holds the smaller S; parameter. The second test ("observed regret test") considers the regret behavior of each pair of base learner j. E MM, on the rounds & I on which i was selected (1 i) and requested the label ( 1), but j would not have requested if asked (fk.j = 0), and the predictions of the two happened to disagree on that round (ag,s # ok.)) The goal here is to eliminate base learners whose cumulative regret is likely to exceed the regret of the smallest well- seee--peefied learner, while ensuring (with high probability) that any well-specified base learner i is not removed from the pool. In similar fashion, the third test ("label complexity test") is aimed at keeping under control the label complexity of the base learners in the active pool Mr. Finally, the last test ("d, test") simply checks whether or not the candidate value d; associated with base learner remains a valid (and tight) upper bound on L (LH + (,,,()))
Notice that the sampling distribution Pt plays base learners with small d, more often than learners with large dj Note also that dj is exactly the finstncc-ddependen factor in the cumulative regret and label complexity bounds for base learners that are well-specified. This means that base learners with lower regret are chosen more frequently than base learners that accumulate regret quicker (and similarly for label complexity). In fact, the sampling distribution is chosen so that the total contribution to the cumulative regret of each base learner is roughly equal. As consequence, the total cumulative regret of Algorithm i at most M (number of base learners) times the regret of each base learner, and the best base learner in particular, which is key property for achieving the guarantees in Theorem below. Of course, this only works when the base learners are well cell-specffied but the four tests in Algorithm@ ensure that all other learners are eventually eliminated.
We have the following result, whose proof is contained in Appendix A.2
Theorem 2. Let Algorithm run with parameters 6, 7 S a with a pool of base learners M1 size M on an i...d sample (I1, (01,,1),.... .., (xT,yr) ~ 'D where the marginal distribution Dx fulfills the low-noise condition with exponent a 2 O w.r.f. a function h that satisfies ( and having complexity
ST (h). Let also Mi contain at least one base learner such that v2ST. (h) Σ S, S 2//2T (h) and d; (LH + log(M/5) ( + S7,,, where LH = log det(1 + H), being H the NTK matrix of depth over the set of points {xt, "t=l,.,,,a==t If poly(TT, n, Any .log(//)),, then with probability at least 1-6 the cumulative regret RT and the total number of queries Ny are simultaneously upper bounded as follows:
RT 0r=00am (0 (LH (LH + log(M/8)+ + st,na(t)) 7+1 T + +ML(T.8)
NT = O M (LH + log( + (()(l) 2t Tri + M M(
where L(T, is the logarithmic term defined at the beginning of Algorithm 2 pseudocode.
We run Algorithm 2 with the pool M₁ = {(S dr,)), ). where S, = -2 i1 = 1,,...., Ollog T)
and di, = 2',, b2 0. Olog T), ensuring the existence of a pair (21, such that
V2Sr.n (h) < Si < 22
and
LH (L + log(M/8) + (1)) de S 2 (LH + log(M/8)+ + (t)). Hence the resulting error due to the discretization is just a constant factor, while the resulting number M of base learners is Olog22 T).
Theorem allows to conclude that running Algorithm 2 on the above pool of copies of Algorithm y guarantees that are similar to those obtained by running a single instance of Algorithm I with
'Notiee that the bounds in Theorem 2 become vacuous if either Sr.,. (h) or LH are O hence we are only interested in making indices i and 12 reach value which is at most logarithmic in T.
8

---

Algorithm 2: Frozen NTK Selective Sampler with Model Selection.
Input: Confidence level 8; probability parameter 0; pool of base learners Mi, each identified with pair d,); number rounds T.
Set [1,, 6) = log 5.2 (og(2)))
for 1.2....7
Observe instance E X' and build Tt,a for i E M₁
Set I,, {0, 1) the indicator of whether base learner i would ask for label Set dr, E 3 as the prediction base learner on Ie
Let B,,, (S, denote the query threshold of base learner i (from Algorithm Select base learner i ~ Pt (Pt,1, 2t.2,, PP..MM)))) where
d. (7)1)
i E M₁
Ptá Ejem, d friays
0,
otherwise
Predict ar. at
1e.t =1 Query label E y and send (It, 3r) to base learner is
M Me
// (1) Disagreement test for all pairs of base learners i,j N₁ that disagree in their prediction (Q,,; # a.,))
=
=0;
|
Eliminate all learners with smaller S: MM+11 = {m E MM+1: : Sm. > min
for all puirs of base learners j, M, Consider rounds where the chosen learner requested the label but j did not, and and j disagree in their prediction:
// (2) Observed regret test
Vesu = (u E [t] in Iusi = 1, = 0, axes + ax.s)
if Σ (11(ax, * yk) - Makss # yx))>
Σ (1ABr,) + 1.45 PenalL((VL,a)
kEV.... Eliminate base learner i: M41 Me+1 \ {i}
REV.
for i E Mr Consider rounds where base learner was played: Ty, (k: [[]: =
// (3) Label complexity test
if
1 3e (T.sl 2
Σ BR, 4) + ( 8/(M loga (12))))
inf <E(0.1/2)
RET Eliminate base learner d:
kETs.
M1+1 = Met1 \ (i}
for M, if ( Eliminate base learner i:
11 (4) d, test
Sd;
M M44 \ (i)
s= (h), that as the complexity parameter Sr were known beforehand. Yet, this model selection guarantee comes at a price, since Algorithm needs to receive as input the noise exponent a (through parameter 7 a)) in order correctly shape label complexity test.
The very same online-to-batee -btch conversion mentioned in Section 3 can be applied to Algorithm Again, combining with the bound on the number of labels and disregarding log factors, this gives high probability excess risk bound of the form
2
LH (LH + S7 (h))
(3)
NT

---

provided = a. Following the same example as at the end of Section 3 when Lи is poly-logarithmic
(1 B-a 1 11)
in T and 5² O ) for some / E [0, 1), one can verify that 3 of the form N.
(up to log factors), which converges for B < 1/(a + 1). Hence, compared to we can ensure convergence a more restricted set of cases.
Section A.3 in the appendix contains the extension of our model selection procedure to the case where the network weights are themselves updated.
Conclusions and Work in Progress
We have presented a rigorous analysis of selective sampling and active learning in general non- parametric scenarios, where the complexity of the Bayes optimal predictor is evaluated on the data at hand as a fitting measure with respect to the NTK matrix of a given depth associated with the same data. This complexity measure plays central role in the level of uncertainty the algorithm assigns to labels (the higher the complexity the higher the uncertainty, hence the more labels are queried). Yet, since this is typically an unknown parameter of the problem, special attention is devoted to designing and analyzing a model selection technique that adapts to this unknown parameter.
In doing we borrowed tools and techniques from Neural Bandits
45 43 selective sampling (e.g.. [6]), and online model selection contextual bandits 36 35 and combined them together in an original and non-trivial manner.
We proved regret and label complexity bounds that recover known minimax rates in the parametric case, and extended such results well beyond the parametric setting achieving favorable guarantees that cannot easily be compared to available results in the literature of active learning in non non-maraet settings. One distinctive feature of our proposed technique is that it gives rise to efficient and manageable algorithms for modular DNN architecture design and deployment.
We conclude by mentioning a few directions we are currently exploring:
2 This may call for slightly more refined balancing technique that jointly involves Sr (h) and a itself.
We are trying to get rid of the prior knowledge of a in the model selection Algorithm
2. Regardless of whether a is available, it would be nice to improve the dependence on 7 = a in the regret bound of Theorem 2 This would ensure convergence of the generalization bound as Ny + oo when Sy,, (h) - = T for all | E [0, 1). We conjecture that this is due a suboptimal design of our balancing mechanism for model selection in Algorithm 2
3. We are investigating links between the complexity measure ST., (h) and the smoothness properties of the (Bayes) regression function h with respect to the NTK kernel (of given depth nt).
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 24, pages 2312-2320. Curran Associates, Inc., 2011.
[2] S. Arora, S. S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
[3] J. T. Ash, C. Zhang, A. Krishnamurthy, J. Langford, and A. Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds, arXiv preprint arXiv:1966.0367) 2019.
[4] M. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-89 2009.
[5] N. Balcan, Hanneke, and J. Wortman. The true sample complexity of active learning. In COLT, 2008
10

---

[6] A. Beygelzimer, S. Dasgupta, and J. Langford. Importance weighted active learning. In ICML, 2009.
[7] A. Bietti and Mairal. On the inductive bias neural tangent kernels. In Advances Neural Information Processing Systems. Curran Associates, Inc., 2019.
[8] Y. Cao, Z. Fang, Y. Wu, D. Zhou, and Q. Gu. Towards understanding the spectral bias of deep learning. In arXiv:
2019.
(9] Y. Cao and Q. Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
[10] R. Castro and R. Nowak. Minimax bounds for active learning. IEEE Transactions on Information Theory, 54(5):2339-2355) 2008.
[11] K. Chaudhuri and S. Dasgupta. Rates of convergence for nearest neighbor classification. In Advances in Neural Information Processing Systems, pages 3437-3445, 2014.
[12] S. R. Chowdhury and A. Gopalan. On kernelized multi-armed bandits. In Proceedings of the 34th International Conference on Machine Learning, 2017.
[13] D. Cohn, L. Atlas, and R. Ladner. Improving generalization with active learning. Machine learning, 15(2)2201-221, 1994.
[14] I. Dagan and S. P. Engelson. Committee-based sampling for training probabilistic classifiers. In Machine Learning Proceedings 1995, pages 150-157. Elsevier, 1995.
[15] S. Dasgupta, D. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. In Advances Neural Information Processing Systems, 2007.
[16] O. Dekel, C. Gentile, and K. Sridharan. Selective sampling and active learning from single and multiple teachers. J. Mach. Learn. Res., 13(1), 2012.
[17] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. International Conference on Machine Learning, page 1675-1685, 2019.
[18] S. Du, J. Lee, Y. Tian, A. Singh, and B. Poczos. Gradient descent learns one- one-hidder Madden-llaeer CNN: Don't be afraid of spurious local minima. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1348. PMLR, 2018.
[19] S. Hanneke. A bound the label complexity of agnostic active learning. In ICML, 2007.
[20] S. Hanneke. Adaptive rates of convergence active learning. In Proc. of the 22th Annual Conference on Learning Theory, 2009.
[21] S. Hanneke et al. Theory of disagreement- based active learning. Foundations and Trends@ in Machine Learning, 7(2-3):131 -09,, 2014.
[22] S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sckhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. arXiv preprint arXiv:1810.0824/ 2018.
[23] D. Hsu, C. Sanford, R. Servedio, and E. V. Vlatakis Gkaragkounis. On the approximation power of two-layer networks of random relus. arXiv preprint arXiv: 2102.02336, 2021.
[24] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kemnl: convergence and generalization in neural networks. In Advances in neural information processing systems, page 8571-8580. MIT Press, 2018.
[25] M. Karzand and R. Nowak. Maximin active learning in overparameteriize model classes. In arXiv: /905. 228222. 2020.
[26] A. Kirsch, J. Van Amersfoort, and Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning, arXiv preprint 1906.0890008853 2019.

---

[27] V. Koltchinskii. Rademacher complexities and bounding the excess risk of active learning. Journal of Machine Learning Research, 11:2457-2485, 2010.
[28] A. Kontorovich, S. Sabato, and R. Umnr. Active nearest-neighbor learning in metric spaces, In Advances in Neural Information Processing Systems, pages 856-864, 2016.
[29] A. Krizhevsky, I. Sutskever, and G. Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
[30] D. D. Lewis and W. A. Gale. A sequential algorithm for training text classifiers. In SIGIR 994, pages 3-12. Springer, 1994.
[31] C. A. Locatelli A. and S. Kpotufe. Adaptivity noise parameters in nonparametric active learning. In Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1383-1416, 2017.
[32] E. Mammen and A. Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 2786);1808 1999.
[33] S. Minsker. Plug-in approach to active learning. Journal of Machine Learning Research, 13:67-90, 2012.
[34] B. Njike and X. Siebert. Nonparametric adaptive active learning under local smoothness condition. In arxiv: 2102.11077. 2021.
[35] A. Pacchiano, C. Dann, G. C., and P. Bartlett. Regret bound balancing and elimination for model selection in bandits and RL. arXiv preprint arXiv:2012. 13045, 2020.
[36] A. Pacchiano, M. Phan, Y. Abbasi Yadkori, A. Rao, J. Zimmert, Lattimore, and C. Szepesvari. Model selection in contextual stochastic bandit problems. In Advances in Neural Information Processing Systems, volume 33, pages 10328-10337 Curran Associates, Inc., 2020.
[37] R. Pop and P. Fulop. Deep ensemble bayesian active learning: Addressing the mode collapse issue in monte carlo dropout via ensembles. arXiv preprint arXiv: /811. 1.03897, 2018.
[38] M. Raginsky and A. Rakhlin. Lower bounds for passive and active learning. In Advances in Neural Information Processing Systems, 2011.
[39] O. Sener and S. Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv: /00.:/700.000000 00489, 2017.
[40] B. Settles. Active learning literature survey. 2009.
[41] L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11: 1984.
[42] M. Valko, N. Korda, R. Munos, I. Flaounas, and N. Cristianini. Finite-time analysis of kernelised contextual bandits. In arxiv:/300 6869, 2013.
[43] W. Zhang, D. Zhou, L. Li, and Q. Gu. Neural thompson sampling. In arxi2220000000 2020.
[44] Zhdanov. Diverse mini-batch active learning. arXiv preprint 1901 2019.
[45] D. Zhou, L. Li, and Q Gu. Neural contextual bandits with ucb-based exploration. In Proceedings of the 37th International Conference on Machine Learning, 2020.
12


Reviews:
[{"review_id": "zVvC8OcwVCk", "reviewer": "Reviewer_DHHc", "summary": "Using a combination of the Neural Tangent Kernel (NTK) approximation and contextual bandit approaches, the paper first derives a neural active learning algorithm for the streaming setting where the data points come sequentially and the algorithm has to decide whether to query for the label of each data point. A second similar algorithm is developed for model selection so that the model complexity does not have to be known beforehand. Both algorithms have counterparts which train the neural networks with stochastic gradient descent. The goal of the algorithms is to balance the regret and the number of queried data points. Using the mentioned theoretical frameworks, joint bounds on the regret and the number of queries are derived.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Originality**: According to the authors, guarantees on efficient non-parametric active learning algorithms did not exist before their work. \n\nThe proposed approach is an adaptation of NeuralUCB [1] to active learning and thus borrows a lot from it. From that point of view, this adaptation is the one of the main contributions of the paper. The other main contribution is the model selection algorithm, while inspired from existing approaches, also seems novel and provides a really nice approximation of the complexity parameter. This latter contribution is essential to the paper as it ties loose ends of the first algorithm.\n\nIn relation to related works, the authors noted:\n\n> We emphasize that most of these works, that heavily rely on approximation theory, are not readily comparable to ours, since our goal here is not to approximate h through a DNN on the entire input domain, but only on the data at hand.\n\nHowever, while I am not knowledgeable of the field, it seems weird to me that comparisons cannot be made even just to highlight the reasons why the proposed approach or the existing approaches cannot be adapted to one setting or the other.\n\n**Quality**: By lack of knowledge of the previous works, I did not verify the proofs and barely understood the main theorems. However, proofs are short, straight to the point and divided into lemmas, which can ease up their understanding.\n\n**Clarity**: The paper is well written for readers already knowledgeable of the three fields it is borrowing from (NTK, contextual bandits and model selection in bandits) in addition to the active learning theory field. If one is not knowledgeable in one of the fields, it might be hard to fully understand the whole. I think adding a paragraph explaining on how all these fields tie together in this paper could improve clarity a lot. \n\nFor the order of the sections, I’m not sure why the section Related work goes in Preliminaries and Notation. It should be a section on its own after the introduction.\n\n**Significance**: The results are important in the field of theoretical active learning. It provides theoretical guarantees for using neural networks in active learning with the NTK framework. However, even though the algorithms seem implementable (i.e. not just of theoretical interest), no experiments were done to quantify the practicality of the bounds. One could thus conclude that the bounds are probably vacuous and not of use in practice.\n\n**Ways to improve the paper**: One way to improve would be to do experiments showing how the approach empirically performs. Another way would be to compare the approach to other approaches in similar settings as mentioned in the originality paragraphs.\n\n[1] Zhou, D., Li, L., & Gu, Q. (2020, November). Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning (pp. 11492-11502). PMLR.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I would say that the main limitation of the paper is the setting to which it is constrained.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "sieEOcV364y", "reviewer": "Reviewer_BX5E", "summary": "NB: The original submission contains an error. The supplementary material contains the fixed version of the submission. \n\nThis paper produces the first NTK based active learning method with provable guarantees. ", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is an extension of the work in Neural Contextual Bandits with UCB-based Exploration (which the authors freely acknowledge), where in moving to an active learning framework the authors had to augment the existing bandit algorithm to account for two key differences:\n1) In the bandit algorithm the reward is always seen for free, whereas in active learning the algorithm must decide whether to see the reward. \n2) There is a data dependant complexity term which is a required input to the algorithm. \n\nTo account for these, the authors first derive a selection algorithm under frozen MLP weights and known complexity. They then deal with the issue of unknown complexity by using a pool of versions of the first algorithm, with various elimination rules for pruning that pool. Additionally in the appendix, they provide versions of both these methods where the MLP weights are not frozen, but are updated by the data as well. For all methods they also provide simultaneous bounds high probability bounds on both the number of examples queried, and the regret ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The concepts and notation used here are very challenging to follow for someone not familiar with NTK. This is not a criticism of the authors or their work, but it makes the paper very challenging to read. \n\nThe content of the paper is clearly theoretical, but it would be useful to include at least a few (even very simple) experiments to show that:\n1) There are regimes where the active learning method actually outperforms random sampling when using the same NTK estimator in the Algorithms (or even just Algorithm 1, with a known and correct complexity).\n2) There are regimes where using these NTK estimators with active learning is better than just training a DNN in a standard way without active learning. \n\nEven a toy example which is built specifically for the method (with explanation for why the method works well on this example) would help readers better understand. \n\nnits:\n- L165: parametric should be non-parametric\n- Beyond the first page, \\mathcal{Y} = {-1, 1}, correct (at least for exposition). Is this why x_{t, a} \\in \\mathcal{X}^2? For a multiclass problem we would have x_{t, a} \\in \\mathcal{X}^k right? If so it would be clearer to replace \\mathcal{Y} with {-1, 1} throughout, but especially in Algorithm 1, where x_{t, a} \\in \\mathcal{X}^2 and so the method is already specialized to binary classification. \n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2-3"}, "extra_text": {}}, {"review_id": "eXjteEa0Gs", "reviewer": "Reviewer_FuZA", "summary": "This work tackles the problem of active learning for non-parametric classifiers and streaming data, where data points arrive sequentially and, after providing its prediction, the active learning strategy must decide whether to observe the true label or not. Performance of active learning strategies under this setting is evaluated using the difference between the cumulative sum of expected loss incurred by the strategy and the cumulative sum of expected loss incurred by a Bayesian-optimal classifier, which relates to the pseudo-regret in stochastic multi-armed bandits. The authors propose the first computationally efficient algorithm for active learning using Deep Neural Networks (DNNs) (contribution 1), which is achieved using over-parameterized DNNs. By relying on the theory of Neural Tangent Kernel (NTK) approximation, they provide a theoretical analysis of the proposed strategy (contribution 2) and show that one can leverage recent works in model selection to design a novel model selection algorithm (contribution 3). More specifically, they provide high-probability upper-bounds on the pseudo-regret and on the amount of data required for the bound to hold.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper leverages recent advances in contextual bandit using DNNs with theoretical guarantees for the specific task of active learning under the streaming setting.\n\n[+] The paper is clearly written, well organized, and very easy to follow. Notation and preliminaries are clear and provide all the important information for understanding the paper.\n\n[+] The setting tackled in this work has two components: non-parametric and streaming. It seems novel to provide a method with theoretical guarantees on sample complexity under these two conditions, most of the work in the non-parametric setting focusing on the pool-based situation (rather than streaming).\n\n[-] Alg. 1 is an adaptation of a recent contextual bandit strategy. Application to the active learning streaming setting is natural due to the streaming process. Previous usage of (contextual) bandit methods for active learning are missing from the related work and should be discussed, e.g. Bouneffouf, Laroche, Urvoy, Féraud, and Allesiardo (2014). Contextual bandit for active learning: Active Thompson sampling. In International Conference on Neural Information Processing (pp. 405-412).\n\n[+] By removing the typical assumption (in the contextual bandit setting) that the function complexity is known, Alg. 2 could inspire the development of new methods in the bandit community.\n\n[-] Although the related work section is exhaustive, the second paragraph (lines 153-170) reads like a listing of historical facts. It would benefit from 1-2 sentences highlighting the novelty of the current work compared with the listed works. From what I understand, the current work uses less restrictive assumptions on the marginal distribution -- this should be clarified.\n\n[-] The paper currently lacks experiments to confirm that the proposed method behaves as expected given the theory and that there is indeed an advantage in using it compared with existing approaches. The theoretical arguments seem sound, but it is difficult to assess their relevance and impact without an empirical evaluation. However, I understand that this could be due to the limited space (space is currently used for detailed explanations and discussions of the theoretical results, which is very good).\n\nDisclaimer: I didn't review the proofs in the Appendix.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "XPtsvVw96bG", "reviewer": "Reviewer_iCf1", "summary": "This paper presents algorithms for active learning in the non-parametric regimes, through NTK approximation. The resulting algorithm matches the minimax rates for active learning in certain regimes. It also studies the model selection problem with respect to unknown parameters, which is missed in previous analysis with NTK approximation.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper converts contextual bandit algorithms into active learning algorithms with statistical learning guarantees. Such an approach looks novel and interesting to me. The paper is well-written and easy to follow. Although I didn't have time to carefully check the proofs, the derived results make sense to me (except for some specific questions as follows).\n\n1. Is there any particular reasons to present the \"frozen version\" of the algorithm in the main body of the paper? The \"frozen version\" essentially goes back to a linear bandit algorithm to me. Seems to me that the \"trained version\" of the algorithm is more interesting. Does the \"trained version\" requires more assumption or lead to a worse bound?\n\n2. Based on my understanding of the model selection algorithm, e.g., Carrol-type of algorithms, they usually cannot achieve regret smaller than \\sqrt{T} even with some known rates (see Thm 6.1 in citation [35]). However, it seems that the guarantee of Theorem 2 surpass that limit (let's say just set \\gamma = \\alpha). Can you provide some explanations for that?\n\n3. It would be nice to provide some intuitions for the sampling distribution defined in Alg2, and how it helps Alg2 to achieve its guarantees.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the paper are mentioned in Section 5. The results are mainly theoretical; to me, it didn't lead to negative societal impacts in the foreseeable future.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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