Neural Active Learning with Performance Guarantees

Abstract:
We investigate the problem of active learning in the streaming setting in nonparametric 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.

heading: 1 Introduction
text: Supervised learning is a 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, as the complexity of current deep learning architectures grows, their requirement for labeled data increases significantly. The area of active learning aims to reduce this data requirement by studying the design of algorithms that can learn and generalize from a small carefully chosen subset of the training data [13, 40].
The two common formulations of active learning are pool based active learning, and sequential (or streaming) active learning. In the pool based setting [30], the learning algorithm has access to a 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 a distribution, and the algorithm must decide whether to query the label of a given point or not [14].
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 a pre-specified classH of functions such that the target function mapping examples to their labels
35th Conference on Neural Information Processing Systems (NeurIPS 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 is to query for a small number of labels and produce a hypothesis of low error.
In the parametric setting, namely, when the class of functionsH has finite VC-dimension (or finite disagreement coefficient) [21], the rate of convergence of active learning, i.e., the rate of decay of the regret as a function of the number of label queries (N ), is of the form ν N−1/2 + e− √ N , where ν is the population loss of the best function in class H. This simple finding shows that active learning behaves like passive learning when ν > 0, while very fast rates can only be achieved under low noise (ν ≈ 0) conditions. This has been worked out in, e.g., [19, 15, 5, 4, 6, 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 ν to close to 0). To address the above, there has also been considerable theoretical work in recent years on non-parametric active learning [10, 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 active learning (e.g., [37, 26, 39, 3, 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 possible in non-parametric 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-parametric active learning, we avoid fixing a function class a-priori. However, in order to achieve computational efficiency, we instead propose to use over-parameterized DNNs, where the amount of over-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 a DNN, followed by a 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 a linearization 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 a novel model selection algorithm inspired by recent works in model selection in multiarmed 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 a significant amount of budget on label queries.

heading: 2 Preliminaries and Notation
text: Let X denote the input space, Y the output space, and D an unknown distribution over 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 DY|x0 the conditional distribution of random variable y given x = x0. Moreover, given a function f (sometimes called a hypothesis or a model) mapping X to Y , the conditional population loss (often referred to as conditional risk) of f is denoted by L(f |x), and defined as L(f |x) = Ey∼DY|x [`(f(x), y) |x], where ` : Y × Y → [0, 1] is a loss function. For ease of presentation, we restrict to a binary classification setting with 0-1 loss, whence Y = {−1,+1}, and `(a, y) = 1{a 6= y} ∈ {0, 1}, 1{·} being the indicator function of the predicate at argument. When clear from the surrounding context, we will omit subscripts like “y ∼ DY|x" from probabilities and expectations.
We investigate a non-parametric setting of active learning where the conditional distribution of y given x is defined through an unknown function h : X 2 → [0, 1] such that
P(y = 1 |x) = h((x, 0)) P(y = −1 |x) = h((0, x)) , (1) where 0 ∈ X , (x1, x2) denotes the concatenation (or pairing) of the two instances x1 and x2 (so that (x, 0) and (0, x) are in X 2) and, for all x ∈ X we have h((x, 0)) + h((0, x)) = 1. We make no explicit assumptions on h, other than its well-behavedness w.r.t. the data {xt}Tt=1 at hand through the formalism of Neural Tangent Kernels (NTK) – see below. As a simple example, in the linear case, X is the d-dimensional unit ball, h(·, ·) is parametrized by an unknown unit vector θ ∈ Rd, and h((x1, x2)) = 1+〈(θ,−θ),(x1,x2)〉 2 , so that h((x, 0)) = 1+〈θ,x〉 2 and h((0, x)) = 1−〈θ,x〉 2 , where 〈·, ·〉 is the usual dot product in Rd. We consider a streaming setting of active learning where, at each round t ∈ [T ] = {1, . . . , T}, a pair (xt, yt) ∈ X × Y is drawn i.i.d. from D. The learning algorithm receives as input only xt, and is compelled to both issue a prediction at for yt and, at the same time, decide on-the-fly whether or not to observe yt. These decisions can only be based on past observations. Let Et denote the conditional expectation E[· |(x1, y1) . . . , (xt−1, yt−1), xt], and we introduce the shorthand
xt,a = { (xt, 0) if a = 1 (0, xt) if a = −1 .
Notice that with this notation E[`(a, yt) |xt] = 1− h(xt,a), for all a ∈ Y . We quantify the accuracy of the learner’s predictions through its (pseudo) regret, defined as
RT = T∑ t=1 ( Et[`(at, yt) |xt]− E[`(a∗t , yt) |xt] ) = T∑ t=1 ( h(xt,a∗t )− h(xt,at) ) ,
where a∗t is the Bayesian-optimal classifier on instance xt, that is, a ∗ t = arg maxa∈Y h(xt,a). Additionally, we are interested in bounding the number of labels NT the algorithm decides to request. Our goal is to simultaneously bound RT and NT with high probability over the generation of the sample {(xt, yt)}t=1,...,T . Throughout this work, we consider the following common low-noise condition on the marginal distributionDX (Mammen-Tsybakov low noise condition [32]): There exist absolute constants c > 0, and α ≥ 0 such that for all ∈ (0, 1/2) we have
P ( |h((x, 0))− 1
2 | <
) ≤ c α .
In particular, α =∞ gives the so-called hard margin condition P ( |h((x, 0))− 12 | < ) = 0. while, at the opposite extreme, exponent α = 0 (and c = 1) results in no assumptions whatsoever on DX . For simplicity, we shall assume throughout that the above low-noise condition holds for1 c = 1.
Our techniques are inspired by the recent work [45] from which we also borrow some notation. We are learning the class of functions {h} by means of fully connected neural networks
f(x, θ) = √ mWnσ(...σ(W1x)) ,
where σ is a ReLU activation function σ(x) = max{0, x}, m is the width of the network and n ≥ 2 is its depth. In the above, θ ∈ Rp collectively denotes the set of weights {W1,W2, . . . ,Wn} of the network, where p = m+ 2md+m2(n− 2) is their number, and the input x at training time should be thought of as some xt,a ∈ X 2. With any depth-n network and data points {xt,a}t=1,...,T, a=±1 we associate a depth-n NTK matrix as follows [24]. First, rename {xt,a}t=1,...,T, a=±1 as {x(i)}i=1,...,2T . Then define matrices
H̃(1) = [ H
(1) i,j ]2T×2T i,j=1
Σ(1) = [ Σ
(1) i,j ]2T×2T i,j=1
with H(1)i,j = Σ (1) i,j = 〈x (i), x(j)〉 ,
and then, for any k ≤ n and i, j = 1, . . . , 2T , introduce the bivariate covariance matrix
A (k) i,j =
[ Σ
(k) i,i Σ (k) i,j
Σ (k) i,j Σ (k) j,j ] 1A more general formulation requires the above to hold only for ≤ 0, where 0 ∈ (0, 1/2) is a third
parameter. We shall omit this extra parameter from our presentation.
by which we recursively define
Σ (k+1) i,j = 2E(u,v)∼N(0,A(k)i,j )[σ(u)σ(v)]
and H̃
(k+1) i,j = 2H̃ (k) i,j E(u,v)∼N(0,A(k)i,j )[ 1{u ≥ 0} 1{v ≥ 0}] + Σ (k+1) i,j .
The 2T × 2T -dimensional matrix H = 12 (H̃ (n) + Σ(n)) is called the Neural Tangent Kernel (NTK) matrix of depth n (and infinite width) over the set of points {xt,a}t=1,...,T, a=±1. The reader is referred to [24] for more details on NTK.
In order to avoid heavy notation, we assume ||xt|| = 1 for all t. Matrix H is positive semi-definite by construction but, as is customary in the NTK literature (e.g., [2, 9, 17]), we assume it is actually positive definite (hence invertible) with smallest eigenvalue λ0 > 0. This is a mild assumption that can be shown to hold if no two vectors xt are aligned to each other.
We measure the complexity of the function h at hand in a way similar to [45]. Using the same rearrangement of {xt,a}t=1,...,T, a=±1 into {x(i)}i=1,...,2T as above, let h be the 2T -dimensional (column) vector whose i-th component is h(x(i)). Then, we define the complexity ST,n(h) of h over {xt,a}t=1,...,T, a=±1 w.r.t. an NTK of depth n as ST,n(h) = √ h>H−1h . Notice that this notion of (data-dependent) complexity is consistent with the theoretical findings of [2], who showed that for a two-layer network the bound on the generalization performance is dominated by y>H−1y, where y is 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 y. Also observe that S2T,n(h) can in general be as big as linear in T (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,n(h) by the norm of h in the RKHS.
The complexity term ST,n(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 [12]), where a (tight) upper bound on ST,n(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 to active learning the regret balancing technique from [36, 35].
In what follows, we use the short-hand g(x; θ) = ∇θf(x, θ) and, for a vector g ∈ Rp and matrix Z ∈ Rp×p, we often write √ g>Zg as ||g||Z , so that ST,n(h) = ||h||H−1 .

heading: 2.1 Related work
text: 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 a 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 ν N−1/2 + e− √ N , 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 ν > 0, while fast rates can only be achieved under very low noise (ν ≈ 0) conditions. In this respect, relevant references include [20, 27] where, e.g., in the realizable case (i.e., when the Bayes optimal classifier lies inH), minimax active learning rates of the form N− α+1 2 are shown to hold for adaptive algorithms that do not know beforehand the noise exponent α. In non-parametric settings, a comprehensive set of results has been obtained by [31], which builds on and significantly improves over earlier results from [33]. Both papers work under smoothness (Holder continuity/smoothness) assumptions. In addition, [33] requiresDX to be (quasi-)uniform on X = [0, 1]d. In [31] the minimax active learning rateN− β(α+1) 2β+d is shown to hold for β-Holder classes, where exponent β plays the role of the complexity of the class of functions to learn, and d is the input dimension. This algorithm is adaptive to the complexity parameter β, and is therefore performing a kind of model selection. Notice that minimax rates in the
parametric regime are recovered by setting β →∞. Of a somewhat similar flavor is an earlier result by [27], where a convergence rate of the form N− α+1 2+κα is shown, being κ the metric entropy of the class (again, a notion of complexity). A refinement of the results in [31] has recently been obtained by [34] where, following [11], a more refined notion of smoothness for the Bayes classifier is adopted which, however, also implies more restrictive assumptions on the marginal distribution DX . 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-independent results (like in most of the papers we cited above) by, e.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 [23] for example. But such results are too embryonic in nature to allow us a full-fledged comparison.
Model selection of the scale of a Nearest-Neighbor-based active learning algorithm is also performed in [28], whose main goal is to 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 are not directly comparable to 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 over-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.

heading: 3 Basic Algorithm
text: Our first algorithm (Algorithm 1) 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 1 is 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 θ0 by independently sampling from Gaussian distributions of appropriate variance, and then uses θ0 to stick with a gradient mapping φ(·) which will be kept frozen from beginning to end. The algorithm also takes as input the complexity parameter S = ST,n(h) of the underlying function h satisfying (1). We shall later on remove the assumption of the prior knowledge of ST,n(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 non-parametric regimes.
At each round t, Algorithm 1 receives an instance xt ∈ X , and constructs the two augmented vectors xt,1 = (xt, 0) and xt,−1 = (0, xt) (intuitively corresponding to the two “actions" of a contextual bandit algorithm). The algorithm predicts the label yt associated with xt by maximizing over a ∈ Y an upper confidence index Ut,a stemming from the linear approximation h(xt,a) ≈√ m〈φ(xt,a), θt−1 − θ0〉 subject to ellipsoidal constraints Ct−1, as in standard contextual bandit algorithms operating with the frozen mapping φ(·). In addition, in order to decide whether or not to query label yt, the algorithm estimates its own uncertainty by checking to what extent Ut,at is close to 1/2. This uncertainty level is ruled by the time-varying threshold Bt, which is expected to shrink to 0 as time progresses. Notice that Bt is a function of γt−1, which in turn includes in its definition the complexity parameter S. Finally, if yt is revealed, the algorithm updates its least-squares estimator θt by a rank-one adjustment of matrix Zt and an additive update to the bias vector bt. No update is taking place if the label is not queried. The following is our initial building block.2
Theorem 1. Let Algorithm 1 be run with parameters δ, S, m, and n on an i.i.d. sample (x1, y1), . . . , (xT , yT ) ∼ D, where the marginal distribution DX fulfills the low-noise condition with exponent α ≥ 0 w.r.t. a function h that satisfies (1) and such that √ 2ST,n(h) ≤ S. If m = poly(T, n, λ−10 , log(1/δ)), then with probability at least 1− δ the cumulative regret RT and
2All proofs are in the appendix.
Algorithm 1: Frozen NTK Selective Sampler. Input: Confidence level δ, complexity parameter S, network width m, and depth n . Initialization:
• Generate each entry of Wk independently from N (0, 2/m), for k ∈ [n− 1], and each entry of Wn independently from N (0, 1/m); • Define φ(x) = g(x; θ0)/ √ m, where θ0 = 〈W1, . . . ,Wn〉 ∈ Rp is the (frozen) weight
vector of the neural network so generated; • Set Z0 = I ∈ Rp×p, b0 = 0 ∈ Rp .
for t = 1, 2, . . . , T Observe instance xt ∈ X and build xt,a ∈ X 2, for a ∈ Y = {−1,+1} Set Ct−1 = {θ : ‖θ − θt−1‖Zt−1 ≤ γt−1√ m }, with γt−1 = √ log detZt−1 + 2 log(1/δ) + S
Set
Ut,a = √ m max θ∈Ct−1 〈φ(xt,a), θ − θ0〉 = √ m〈φ(xt,a), θt−1 − θ0〉+ γt−1‖φ(xt,a)‖Z−1t−1
Predict at = arg maxa∈Y Ut,a Set It = 1{|Ut,at − 1/2| ≤ Bt} ∈ {0, 1} with Bt = Bt(S) = 2γt−1‖φ(xt,at)‖Z−1t−1 if It = 1
Query yt ∈ Y , and set loss `t = `(at, yt) Update
Zt = Zt−1 + φ(xt,at)φ(xt,at) >
bt = bt−1 + (1− `t)φ(xt,at) θt = Z −1 t bt/ √ m+ θ0
else Zt = Zt−1, bt = bt−1, θt = θt−1, γt = γt−1, Ct = Ct−1 .
the total number of queries NT are simultaneously upper bounded as follows:
RT = O
( L α+1 α+2
H
( LH + log(1/δ) + S 2 )α+1 α+2 T 1 α+2 + log(log T/δ) ) NT = O ( L α α+2
H
( LH + log(1/δ) + S 2 ) α α+2 T 2 α+2 + log(log T/δ) ) ,
where LH = log det(I + H), H being the NTK matrix of depth n over the set of points {xt,a}t=1,...,T, a=±1.
The above bounds depend, beyond time horizon T , on three relevant quantities: the noise level α, 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, LH measures instead the complexity of the NTK itself, hence somehow quantifying the complexity of the function space we rely upon in learning h. It 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 RT = O( √ T ), more precisely a bound of the form RT = O((LH + √ LHS) √ T ), with the trivial label complexity NT = O(T ). At the other extreme, when α → ∞ we obtain the guarantees RT = NT = O(LH(LH + S
2)). In either case, if h is “too complex" when projected onto the data, that is, if S2T,n(h) = Ω(T ), then all bounds become vacuous.
3 At the opposite end of the spectrum, if {h} is simple, like a class of linear functions with bounded norm in a d-dimensional space, and the network depth n is 2 then ST,n(h) = O(1), and LH = O(d log T ), hence recovering the rates reported in [16] for the linear case. The quantity LH is tightly related to the decaying rate of the eigenvalues of the NTK matrix H , and is poly-logarithmic in T in several important cases [42]. One relevant example is discussed in [43], which relies on the spectral characterization of NTK in [7, 8]: If n = 2 and all points x(i) concentrate on a d0-dimensional subspace of the RKHS spanned by the NTK, then LH = O(d0 log T ).
3The same happens, e.g., to the regret bounds in [45].
It is also important to stress that, via a standard online-to-batch conversion, the result in Theorem 1 can be turned to a compelling guarantee in a 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 L(f) = Ex∼DX [L(f |x)] exceeds the Bayes optimal population loss Ext∼DX [h(xt,a∗t )] = Ext∼DX [max{h(xt,1), h(xt,−1)}] by a vanishing quantity. Following [16], this online-to-batch algorithm will simply run Algorithm 1 by sweeping over the sequence {(xt, yt)}t=1,...,T only once, and pick one function uniformly at random among the sequence of predictors generated by Algorithm 1 during its online functioning, that is, among the sequence {Ut(x)}t=1,...,T , where Ut(x) = arg maxa∈Y maxθ∈Ct−1〈φ(x·,a), θ − θ0〉, with x·,1 = (x, 0) and x·,−1 = (0, x). This randomized algorithm enjoys the following high-probability excess risk guarantee:4
Et∼unif(T )[L(Ut)]−Ext∼DX [h(xt,a∗t )] = O
(( LH ( LH + log(1/δ) + S 2 )
T
)α+1 α+2
+ log log(T/δ)
T
) .
Combining with the guarantee on the number of labels NT from Theorem 1 (and disregarding log factors), this allows us to conclude that the above excess risk can be bounded as a function of NT as(LH(LH + S2)
NT
)α+1 2
, (2)
where LH(LH + S2) plays the role of a (compound) complexity term projected onto the data x1, . . . , xT at hand. When restricting to VC-classes, the convergence rate N −α+12 T is indeed the best rate (minimax rate) one can achieve under the Mammen-Tsybakov low-noise condition with exponent α (see, e.g., [10, 20, 27, 16]).
Yet, since we are not restricting to the parametric case, both LH and, more importantly, S2 can be a function of T . In such cases, the generalization bound in (2) can still be expressed as a function of NT alone, For instance, when LH is poly-logarithmic in T and S2 = O(T β), for some β ∈ [0, 1), one can easily verify that (2) takes the form N − (1−β)(α+1)2+βα T (again, up to log factors).
In Section A.3 of the appendix, we extend all our results to 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) = g(x; θ0)/ √ m will be replaced by φt(x) = g(x; θt−1)/ √ m, where θt is not the linear-least squares estimator θt = Z−1t bt/ √ m+ θ0, as in Algorithm 1, but the result of the DNN training on the labeled data {(xk, yk) : k ≤ t, Ik = 1} gathered so far.

heading: 4 Model Selection
text: 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 1, each member in the pool being parametrized by a pair of parameters (Si, di), where Si plays the role of the (unknown) complexity parameter ST,n(h) (which was replaced by S in Algorithm 1), and di plays the role of an (a-priori unknown) upper bound on the relevant quantity ∑ t∈T : it=i 1 2 ∧ It,iB 2 t,i that is involved in the analysis (see Lemma 5 and Lemma 7 in Appendix A.1). This quantity will at the end be upper bounded by a term of the form LH(LH + log(T/δ) + S2T,n(h)) whose components LH and S 2 T,n(h) are initially unknown to the algorithm.
Algorithm 2 maintains over time a setMt of active base learners, and a probability distribution pt over them. This distribution remains constant throughout a sequence of rounds between one change toMt and the next. We call such sequence of rounds an epoch. Upon observing xt, Algorithm 2 selects which base learner to rely upon in issuing its prediction at and querying the label yt, by drawing base learner it ∈Mt according to pt. Then Algorithm 2 undergoes a series of carefully designed elimination tests which are meant to rule out mis-specified base learners, that is, those whose associated parameter Si is likely to be smaller than ST,n(h), while retaining those such that Si ≥ ST,n(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
4Observe that this is a data-dependent bound, in that the RHS is random variable. This is because both LH and S may depend on x1, . . . , xT .
round t, any such test triggers, that is, when it happens that |Mt+1| < |Mt| at the end of the round, a new epoch begins, and the algorithm starts over with a fresh distribution pt+1 6= pt. 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 8 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-specification, thus we eliminate in pairwise comparison the base learner that holds the smaller Si parameter. The second test (“observed regret test") considers the regret behavior of each pair of base learners i, j ∈Mt on the rounds k ≤ t on which i was selected (ik = i) and requested the label (Ik,i = 1), but j would not have requested if asked (Ik,j = 0), and the predictions of the two happened to disagree on that round (ak,i 6= ak,j). The goal here is to eliminate base learners whose cumulative regret is likely to exceed the regret of the smallest well-specified learner, while ensuring (with high probability) that any well-specified base learner i is not removed from the pool. In a 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 Mt. Finally, the last test (“di test") simply checks whether or not the candidate value di associated with base learner i remains a valid (and tight) upper bound on LH(LH + S2T,n(h)).
Notice that the sampling distribution pt plays base learners with small di more often than learners with large di. Note also that di is exactly the (instance-dependent) 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 a consequence, the total cumulative regret of Algorithm 2 is at most M (number of base learners) times the regret of each base learner, and the best base learner in particular, which is a key property for achieving the guarantees in Theorem 2 below. Of course, this only works when the base learners are well-specified but the four tests in Algorithm 2 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 2 be run with parameters δ, γ ≤ α with a pool of base learnersM1 of size M on an i.i.d. sample (x1, y1), . . . , (xT , yT ) ∼ D, where the marginal distribution DX fulfills the low-noise condition with exponent α ≥ 0 w.r.t. a function h that satisfies (1) and having complexity ST,n(h). Let alsoM1 contain at least one base learner i such that √ 2ST,n(h) ≤ Si ≤ 2 √ 2ST,n(h) and di = Θ(LH(LH + log(M/δ) + S2T,n(h))), where LH = log det(I + H), being H the NTK matrix of depth n over the set of points {xt,a}t=1,...,T, a=±1. If m = poly(T, n, λ−10 , log(1/δ)), then with probability at least 1 − δ the cumulative regret RT and the total number of queries NT are simultaneously upper bounded as follows:
RT = O ( M ( LH ( LH + log(M/δ) + S 2 T,n(h) ))γ+1 T 1 γ+2 +M L(T, δ) ) NT = O ( M ( LH ( LH + log(M/δ) + S 2 T,n(h) )) γγ+2 T 2 γ+2 +M L(T, δ) ) ,
where L(T, δ) is the logarithmic term defined at the beginning of Algorithm 2’s pseudocode.
We run Algorithm 2 with the poolM1 = {(Si1 , di2)}, where Si1 = 2i1 , i1 = 0, 1, . . . , O(log T ) and di2 = 2
i2 , i2 = 0, 1, . . . , O(log T ), ensuring5 the existence of a pair (i1, i2) such that √
2ST,n(h) ≤ Si1 ≤ 2 √ 2ST,n(h)
and LH ( LH + log(M/δ) + S 2 T,n(h) ) ≤ di2 ≤ 2LH ( LH + log(M/δ) + S 2 T,n(h) ) . Hence the resulting error due to the discretization is just a constant factor, while the resulting number M of base learners is O(log2 T ).
Theorem 2 allows us to conclude that running Algorithm 2 on the above pool of copies of Algorithm 1 yields guarantees that are similar to those obtained by running a single instance of Algorithm 1 with
5Notice that the bounds in Theorem 2 become vacuous if either ST,n(h) or LH are Θ( √ T ), hence we are
only interested in making indices i1 and i2 reach a value which is at most logarithmic in T .
Algorithm 2: Frozen NTK Selective Sampler with Model Selection. Input: Confidence level δ; probability parameter γ ≥ 0; pool of base learnersM1, each identified with a pair (Si, di); number of rounds T . Set L(t, δ) = log 5.2 log(2t) 1.4 δ for t = 1, 2, . . . , T
Observe instance xt ∈ X and build xt,a ∈ X 2, for a ∈ Y = {−1,+1} for i ∈Mt
Set It,i ∈ {0, 1} as the indicator of whether base learner i would ask for label on xt Set at,i ∈ Y as the prediction of base learner i on xt Let Bt,i = Bt,i(Si) denote the query threshold of base learner i (from Algorithm 1)
Select base learner it ∼ pt = (pt,1, pt,2, . . . , pt,|Mt|), where
pt,i =  d −(γ+1) i∑ j∈Mt d −(γ+1) j , if i ∈Mt 0, otherwise
Predict at = at,it if It,it = 1
Query label yt ∈ Y and send (xt, yt) to base learner it Mt+1 =Mt Set Nt = {i ∈Mt : It,i = 0} // (1) Disagreement test for all pairs of base learners i, j ∈ Nt that disagree in their prediction (at,i 6= at,j)
Eliminate all learners with smaller S: Mt+1 = {m ∈Mt+1 : Sm > min{Si, Sj}} for all pairs of base learners i, j ∈Mt // (2) Observed regret test
Consider rounds where the chosen learner i requested the label but j did not, and i and j disagree in their prediction:
Vt,i,j = {k ∈ [t] : ik = i, Ik,i = 1, Ik,j = 0, ak,i 6= ak,j}
if ∑
k∈Vt,i,j
( 1{ak,i 6= yk}− 1{ak,j 6= yk}) > ∑
k∈Vt,i,j
(1∧Bk,i) + 1.45 √ |Vt,i,j |L(|Vt,i,j |, δ)
Eliminate base learner i: Mt+1 =Mt+1 \ {i} for i ∈Mt // (3) Label complexity test
Consider rounds where base learner i was played: Tt,i = {k ∈ [t] : ik = i} if ∑ k∈Tt,i Ik,i > inf ∈(0,1/2] ( 3 γ |Tt,i|+ 1 2 ∑ k∈Tt,i Ik,iB 2 k,i∧ 1 4 ) +2L(|Tt,i|, δ/(M log2(12t)))
Eliminate base learner i: Mt+1 =Mt+1 \ {i} for i ∈Mt // (4) di test
if ∑ k∈Tt,i( 1 2 ∧ Ik,iB 2 k,i) > 8di
Eliminate base learner i: Mt+1 =Mt+1 \ {i}
S = √
2ST,n(h), that is, as if the complexity parameter ST,n(h) were known beforehand. Yet, this model selection guarantee comes at a price, since Algorithm 2 needs to receive as input the noise exponent α (through parameter γ ≤ α) in order to correctly shape its label complexity test. The very same online-to-batch conversion mentioned in Section 3 can be applied to Algorithm 2. Again, combining with the bound on the number of labels and disregarding log factors, this gives us a high probability excess risk bound of the form
[LH (LH + S2T,n(h))] 3α+2α+2 NT  α+1 2 , (3)
provided γ = α. Following the same example as at the end of Section 3, when LH is poly-logarithmic in T and S2 = O(T β), for some β ∈ [0, 1), one can verify that (3) is of the form N− (1−β(α+1))(α+1) 2+βα T (up to log factors), which converges for β < 1/(α + 1). Hence, compared to (2) we can ensure convergence in 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.

heading: 5 Conclusions and Work in Progress
text: We have presented a rigorous analysis of selective sampling and active learning in general nonparametric 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 a 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 so, we borrowed tools and techniques from Neural Bandits [45, 43], selective sampling (e.g., [16]), and online model selection in 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-parametric 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:
1. We are trying to get rid of the prior knowledge of α in the model selection Algorithm 2. This may call for a slightly more refined balancing technique that jointly involves ST,n(h) and α itself.
2. Regardless of whether α is available, it would be nice to improve the dependence on γ = α in the regret bound of Theorem 2. This would ensure convergence of the generalization bound as NT →∞ when ST,n(h)2 = T β , for all β ∈ [0, 1). We conjecture that this is due to a suboptimal design of our balancing mechanism for model selection in Algorithm 2.
3. We are investigating links between the complexity measure ST,n(h) and the smoothness properties of the (Bayes) regression function h with respect to the NTK kernel (of a given depth n).

Review summaries:
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.

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.

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.

NB: The original submission contains an error. The supplementary material contains the fixed version of the submission.   This paper produces the first NTK based active learning method with provable guarantees.