Making Look-Ahead Active Learning Strategies Feasible with Neural Tangent Kernels
Authors: Mohamad Amin Mohamadi
Wonho Bae
Danica J. Sutherland
Venue: NeurIPS 2022 Accept (2022)
Keywords: active learning
neural tangent kernels
retraining

Abstract: We propose a new method for approximating active learning acquisition strategies that are based on retraining with hypothetically-labeled candidate data points. Although this is usually infeasible with deep networks, we use the neural tangent kernel to approximate the result of retraining, and prove that this approximation works asymptotically even in an active learning setup -- approximating ``look-ahead'' selection criteria with far less computation required. This also enables us to conduct sequential active learning, i.e.\ updating the model in a streaming regime, without needing to retrain the model with SGD after adding each new data point. Moreover, our querying strategy, which better understands how the model's predictions will change by adding new data points in comparison to the standard (``myopic'') criteria, 
beats other look-ahead strategies by large margins, and achieves equal or better performance compared to state-of-the-art methods on several benchmark datasets in pool-based active learning.

Making Look-Ahead Active Learning Strategies Feasible with Neural Tangent Kernels
Mohamad Amin Mohamadi' University of British Columbia lemohama@cs. ca
Wonho Bae" University of British Columbia whbae0cs ubc.ca
Danica Sutherland University of British Columbia Alberta Machine Intelligence Institute dsuthêcs ubc.
Abstract
We propose method for approximating active learning acquisition strategies that are based on retraining with hypothetically-labbke candidate data points. Although this usually infeasible with deep networks, we use the neural tangent kernel to approximate the result of retraining, and prove that this approximation works asymptotically even in an active learning setup - approximating selection criteria with far less computation required. This also enables us to conduct sequential active learning, needing to retrain the model with SGD after adding each new data point. Moreover, our querying strategy, which better understands how the model's predictions will change by adding new data points in comparison to the standard ("myopic") criteria, beats other look-ahead strategies by large margins, and achieves equal or better performance compared to oate-offthee-rt methods on several benchmark datasets in pool-based active learning.
ahead"
updating the model in streaming regime, without
Introduction
Deep learning has drastically advanced over the past decade along with a dramatic increase in the volume of available data. It is, however, consuming and expensive to manually annotate large datasets. Active learning attempts to alleviate this by allowing a model to "actively" request annotation of specific data points, with the expectation that model trained on informative points will learn a better prediction than one on a random, "passively" labeled set the same size.
The most common form of active learning is based on using acquisition function to measure the informativeness of potential data points or batches from some unlabeled pool. Many successful acquisition functions are based on the current model's uncertainty, such maximum entropy [1] and Bayesian Active Learning by Disagreement (BALD) [2]. These functions are based on the expectation that training on points about which the current model is uncertain will be effective at decreasing the future model's ' uncertainty about similar points. This assumption, however, often does not hold: uncertain points might be inherently difficult to predict (alcatoric uncertainty) or simply too difficult for the model to learn right now.
It would be helpful, then, to see how a new data point would change model, potentially with respect to other unseen data. One such strategy known as Expected Model Change, which approximates
"Tese authors contributed equally.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

how much a model's parameters will change when observing new hypothetically--abeeee data point [3, 4]. This approach, though. only considers the magnitude of change in parameters, not the model's actual outputs on the data distribution, and it only looks at the size of the first stochastic gradient (SGD) step with the new data point rather than considering the full trajectory of training.
We will refer to acquisition strategies which consider full retraining of a model based on hypothetical observations look-ahead criteria. Previous attempts to use look-ahead criteria based on the change in model output include Expected Error Reduction [5] and Expected Model Output Change [6]. These approaches have been used only with specialized models such as Naive Bayes and Gaussian processes, where retraining on every new candidate data point is feasible. These classes of models, however, tend to not work well as modern neural networks, meaning these approaches are outperformed by simpler acquisition functions on stronger models.
In this work, we propose algorithm that makes it feasible to conduct active learning with look- ahead acquisition strategies using general neural networks. More specifically, we approximate a network using its Neural Tangent Kernel (NTK) [7], which makes it possible obtain the behavior of retraining a network on a candidate data point without actually retraining the network. At each query step, we use the local approximation of the neural network as proxy compute a look-ahead acquisition function, from which we query a new data point. We prove that in the asymptotic regime where the width of the neural network goes to infinity, this approximation agrees with the result of actually retraining the network, even in an iterative setup such as in active learning. Our approximation decreases the wall-clock time more than 100 times compared naive computation of a look-ahead acquisition function, making them far more feasible in practice.
Our proposed method outperforms existing look-ahead strategies by large margins, and achieves equal or better performance compared to the state-of-the-ar methods on several benchmark datasets in pool-based active learning, including MNIST [8], SVHN [9], CIFARIO [10], and CIFARI00 [10]. The NTK approximation also makes it possible to decouple receiving new data labels and SGD training, unlike previous active learning methods, where knowing true labels does not add any information without SGD training. This is useful when annotation is fast (yet expensive) but model training is slow, since adding data to an existing NTK approximation far faster than retraining with SGD. Sequentially adding true labels of new data gives performance substantially better than more common batch setups.
2
Preliminaries
Active learning. In pool-based active learning, we have a labeled set L = ((((0))((0)) and
unlabeled set t/ (9) 1:4 where 2x5)s are inputs and () are corresponding labels. At each time step f, model f parameterized by 0 is trained on the labeled set L which we denoted as fc, and then a data point from the unlabeled set 2/ is selected to be labeled, according to an acquisition function A measuring the "information gain" of a potential data point x::
xx
argmax A(x, Sc. C, U).
(1)
reul
One of the most common choices of the acquisition function is maximum entropy, which computes the estimated entropy of the unknown label of ær denoted as Y: Aentropy (z, fc, C, U) == H(Y x; fz). Although the maximum entropy acquisition function often works well in practice, it does not consider how the model would change with new queried data point, and so can overly prioritize inherently difficult, uninformative points (e.g. outliers).
Expected gradient length [11] approximates the expected model change by how large the gradient of the loss becomes when adding that data point, E-y-pu(-1a))l
(I, (l) BADGE [4], a more recent variant, Nower-bound the gradient norm of the last layer induced by any possible label. These approaches do not consider how the change in a model actually interacts with the data distribution: large parameter changes might give relatively small changes in predictions on most data points. They also consider a single SGD update, only roughly approximating total change over training.
One approach to alleviate this limitation is expected error reduction [EER; 5J, given by
[21
AEER(E, (2, Sc, C, u)= == - E -Ey-pot--e
Σ H0 | |x(9; Sc+).
(2)
2

---

Here fc+ refers to the model trained on L {zz,))} and H(Y())20) fc+) is the (estimated) entropy of the unknown label of ((() in ti using that model. Maximizing AGER chooses the candidate point whose label has maximal mutual information to the labels of unlabeled data, I(Y; y) fc). fc is fairly good model and the problem is fairly difficult, the numerical value of AEER is likely dominated by the sum of irreducible (aleatoric) uncertanties over the data points; it thus might be prone to noise in estimation based on those large terms.
Freytag et al. [6] propose instead expected model output change (EMOC), based on the difference in model predictions as measured by distance 'D (e.g. the Euclidean distance between probability vectors). The acquisition function is defined as
12 AgMOC (z, Sc. 2,,,,,,,, U) := (- - Σ
Intuitively, we might hope that the change in outputs roughly cancels out the irreducible (aleatoric) uncertainty, leaving us to focus primarily on the decrease in model (epistemic) uncertainty [12]. Our techniques also apply to EER, but EMOC-like criteria performed better in our initial exploration.
Despite their advantages, look-ahead acquisition functions have been in practical reach only with certain types of models: EER has been applied to Naïve Bayes [5] and Gaussian random fields [13], and EMOC only to Gaussian processess [14, 15]. Neural networks generally outperform those models, but obtaining Je+ with SGD training for every candidate example in l/ is impractically expensive. In this work, we propose to approximate fe+ with a more computationally efficient proxy based on neural tangent kernels, making look-ahead acquisition functions feasible on neural networks.
Neural tangent kernels. Over the past few years, connections between infinitely wide neural networks trained by gradient descent and kernel methods have become increasingly clear. The NNGP approximation of Matthews et al. [16], building off a line of work stemming from Neal [17], shows that if network's parameters
initialized with appropriate Gaussian distribution and only the last layer is trained, the resulting function agrees with a Gaussian process with the kernel K(x,x') = Egg (x) fo())), where the expectation over initializations. Jacot et al. [7], building off several immediately preceding works on optimization of wide neural networks, show that infinitely wide fully-connected neural networks also follow Gaussian process behavior, with the kernel
{ (ofo(e) 0So(z') }
K(x,, x') Eo
(4)
0e
00
(derivatives here denoting Jacobians with respect to the vector of all parameters 0). The also show that this kernel remains constant over the course of training, so that these networks evolve like a linear
model under kernel gradient descent. Among many important follow-ups, Arora et al. [18] expand
the results to convolutional networks with finite but large widths, and Novak et al. [19] provide an implementation for nearly-arbitrary network structures. Yang [20] and Yang and Littwin [21] later showed that Jacot et al. [7]'s findings are architecturally universal, extending the domain from fully-connected networks to a large class of architectures including ResNets and Transformers.
Unfortunately, these infinite-widhe width versions of networks tend not to generalize as well as finite networks trained by SGD. Hence, we still want to conduct active learning for finite neural networks, rather than for pure NTK models. The infinite-widh NTK also tends to be mediocre proxy for the behavior of training a finite neural network, and so using as proxy for f'++ does not tend to work as well as we might hope (e.g. Figure lb). We will thus instead use a local linearized approximation of the neural network, based on the empirical neural tangent kernel, as introduced next.
3 Active Learning using NTKs
In this section, we first define a neural network, and the linear model which (in the infinite-wine limit) agrees with training that network. We will prove that in the ddfiitt-wwithh limit, sequentially retraining on increasing datasets as the active learning process - the same as if we had trained from scratch on the final dataset. In practical regimes, however, the infinite-width NTK does not tend to agree with fintte-width SGD very closely. We thus use a local linear approximation of the network, based on the empirical NTK, to approximate retraining in our look-ahead criteria.
3

---

Notation. We mostly use the same notation as Jacot et al. [7]. We define f as fully- fully-connected neural network with L hidden layers numbered from (input) Ap..... Ty neurons. This network has number of parameters P = Ei=o (my + 1)m(1:: each layer has a weight matrix W E [R=xx==+ and bias vector ((0) E = The network is defined as fa. 0/ and = ve (.()). We denote a labeled set L as defined in Section 2 and use X' = fa: (x, y) E [] and y {y (2r,)) E L) to denote its DiuDa, SD,UD, to mean that SDJUD, is trained using inputs and labels, respectively. We write fD, t=
(output), where each layer has
where ! collects all of the parameters:
gradient descent until convergence on the dataset D2, starting from FD.
Unless otherwise specified, the loss function associated with gradient descent training is assumed to be the squared loss, ((x) == 3 f(x)))l This allows for far more efficient usage of NTKs, but Hui and Belkin [22] demonstrate that, with the right learning rate, L2 loss is just as effective cross-entropy for many vision and natural language processing tasks.
Neural networks in the infinite width limit. Jacot et al. [7] show that in the infinite width limit, when the network o is trained using gradient descent with the squared loss a labeled set L, the outputs of the network on any arbitrary point x evolve as
f((x) = fo(z) + K(x, (C(,) x) (I -e
-0
(K(x)))( - fo(x)),
(5)
where K. is the NTK of (4), which stays constant during training. Here we treat inputs X' as matrix and labels as a vector in corresponding order.
Consider sequentially training a network on increasing datasets S C S2 C .... C Sc, warm-starting each time from the result of training on the previous dataset. We build on the results of Jacot et al. [7] to show that the final network from this process is asymptotically equivalent, in the infinite-width limit, training the same network from scratch (cold-start) on the last, biggest dataset Sc. This justifies our efficient approximation of the retrained network, even after we have gone through many iterations of active learning. See Appendix for a formal statement and proof.
Theorem 3.1 (Informal). Let S2,..... be C' datasets such that for all i > j. Sj C CS,, Let So be a randomly initialized network. Let fsia... be the network resulting from starting at fo and training f using gradient descent datasets S Sc sequentially until convergence:
fo
S1 fs.
fs.
S2 fs
Sc
fs.......
t=o0
t=
Also, let Sss be Jo Sc,, tmoe oo sequentially, we have for any arbitrary data point x that (s5((a) = -Jss....... (x)).
SSc. Assuming that J has L + 1 layers such that taking no: Th1 ,,,... TAL
NTK approximations of retrained networks. Armed with Theorem 3.1, the outputs a neural network from retraining. Suppose we have a labeled set and unlabeled set 2/ as defined in Section 2. A neural network fc (whose layers are assumed to be infinitely wide) has
now approximate
been trained on L as fo _,, fc- We are interested in characterizing the outcome after retraining t=o0
this neural network using each of the data points in U. In other words, for each x' E L with hypothetical label y' and L U (a', y²), we would like know what fc _ fer looks like. 1=00
According to (5), the outputs of fc for an arbitrary data point x can be formulated as fe(x) = [o( + K(x,, X X) -f(()')
(6)
Let x and y be inputs and labels of t Then, based on Theorem 3.1, we can conclude that fet (x) + X VC((** xxx) fo)
(7)
As K. remains constant in the infinite-width regime, most of the relevant quantities can be reused:
x)) K(X,x)))
K(x, = (K(x, x'),, K(Xx x(x+,x*)= = [(x', x()',x')
(8)
Remark 3.2. the infinite width limit, we can analytically obtain the predictions of a nearal network after retraining additional data points by augmenting its corresponding NTK using (8).

---

Several works have shown that while being an inspiring theoretical motivation, neural networks in the infinite width limit do not work as well as their finite-width counterparts [18, 23, 24]. Although Arora et al. [18] prove non-asymptotic bounds between these infinite width neural networks and their corresponding finite-width networks, empirical studies in [20, 25] have shown that this approximation may not be effective for practical network widths. (If it were, we wouldn't 't need network at all, and would simply do all our learning with a Gaussian process based on the NTK.) Thus, we would like to be able to efficiently characterize the outputs of finite neural network after retraining.
Lee al. [25] showed the first-order Taylor expansion of neural network around its initialization (a linearized neural network) has training dynamics converging to that of the neural network as the width grows. That is. let ft denote the network which has been trained with gradient descent for steps, and f the result of training the linearized network for steps. They prove that, under some regularity conditions and when the learning rate 1j less than a certain threshold,
sup -tt (z)]l2 sup | Oolls = 120
( /width
(9)
120
Informally, when f is wide enough, its predictions can be approximated by those of the lincarized network flin. This is attractive since f has simple training dynamics, converging
f (x) = fo(z) + Oo(z, X) ()(2( - fo((²))
(10)
where Og is the empirical tangent kernel of fo. Vo(r,y) = Vofo(z) Vofo(y)
In the infinite- wiith limit, the empirical NTK θ converges to the NTK K. almost surely, leading (10) to become equivalent to (6). In finite-width regimes, however, is intuitive to expect that the local approximation may still be able to handle local retraining, such as fc
Al((z.)))
t=20 foo(((.)))) even
when the correspondence to the fehnite-widthh limit K. is loose. We thus model retraining of finite network by augmenting the empirical NTK as in (8), as justified by Theorem 3.1 and Remark 3.2.
Specifically, we approximate the finite width network fc+ (x) defined by fc 2t fct using
fei (x) = f/ (x) = fc(x) O2(2, x0) xx)) (y+ - sc(xx)
(1I)
where O₂ is the empirical NTK obtained from the parameters of fc-
Efficient computation. To avoid computing the full empirical NTK with the shape of LC x LC where L is the size of the labeled set and C. is the number of classes, we use the "single- logit" approximation as explained in Wei et al. [26] (Section 2.3) in which we only compute the
corresponding NTK of the first logit of the network, i.e. O v) (z) (of() & Ic where (() (x:) refers the first neuron of the output of on the datapoint For kernel regression, we can take the kronecker product out, which decreases the memory and time complexity of computing
the NTK by an order of OCC²).
To compute (11), we must solve linear systems with Oc(x*t,x* This can also be done efficiently using the block structure of Oc(x+, X+); letting v = x=(,, (xxx and u Oc(x', ,x)
(c('''x))0((') x) 0
(x) fz (z) ( - - -v-(()((())) W fc(x')))
(12)
Thus, rather than inverting (2(X', xx+) for each x E U, we can invert Oc(X', only once, then use some matrix multiplications to find flin (x) for each query point.
Time complexity. We now provide the time complexity of the NTK approximation proposed in Equation (11) (using efficient block computation in Equation (12)). Let be the size of the labeled set, U of the unlabeled set, P the number of model parameters, and E' the number of training epochs. The computation of O2 (Ru, Xc), ( Xc), and (2(2,, Xx) take OLLUP). P and (I*) time, respectively. If we compute (12) for all EU, the matrix multiplication takes ( Putting altogether, the time complexity of the NTK approximation is OLUP + 1.P + 133 + UT2).. Since we assume > max(T., U) for overparameterized models, the time complexity can be simplified to OLLUP L'P).
5

---

on, but Algorithm 1: Active learning using NTKs
Input: Initialize model In. labeled pool Lo. and unlabeled pool Mo
Train fo on the initial labeled set Lo, using SGD, to obtain fCo
for t = 0 to --1 do
Compute Oc, (AK,, Xc.), (Kc., Xc,) and Oc (AC,, Xc,)
for x' in U4 do
Estimate the label for x' as y' argmax (x')
Approximate fe,u(r"as)) using (11) and (12) for faster computation
Track x² as the point with maximal AMıMoc(a' J Le; Ut) we've ve've seen far
end for
Obtain the label y" for x from the oracle
Update the labeled set L++1 = L. u {(2", yy)} and unlabeled set Ub+1 = \
Train fc. on Li+1, using SGD, to obtain fe..1
end for
The dominant term for naive SGD retraining is OLLUPE) whereas the proposed method using block structure is dominated by OLLUP) P) time if U > L, otherwise O(L2P) time. If > L. then the proposed method is faster by an order of OEE). In the other case, if L >> EU, one can use the conjugate gradient kernel regression solvers in Rudi al. [27] and Gardner et al. [28] that further reduce the time complexity of our proposed method to O(max(PLV L,, PU (U)) depending whether L > U or L U, which is faster than the naïve SGD training by order of O(UE/VL) or O(LE/VU).
MLMOC querying. Instead of the EMOC acquisition function (3), we define a new function more suitable for lincarized network, which we term Most Likely Model Output Change (MLMOC):
Amumocla's fe. Le, Ub)
Ellfc(() well
f(= (z))
(13)
where -- =U with 3/ argmax fz(x'). We only consider the most likely pseudo- label, instead of the expectation; this saves a significant amount of computation, by a factor of the number of classes, but empirically does not hurt accuracy. We also suspect that, when fc is already reasonably accurate, we can "trust" the most likely label more than we can trust accurate estimation of probabilities for oo--robayyility losses, especially when training networks with L2 loss. Algorithm I shows pseudo-code for the proposed algorithm.
Sequential query strategy. In the active learning literature, each query of new data points is essentially always followed by retraining the underlying model. This, however, may not be practical for the cases where annotation is quick but SGD training of large neural network is slow. Although there has been significant effort towards batch selection strategies based on finding diverse examples to query in a batch [e.g. 4, 29, 30J, which among other benefits can minimize the number of times we must retrain with SGD, they cannot fully take advantage of low-latency annotations if they are available. (This may be the case if, for instance, labeling tasks can be quickly pushed out to a pool of human labelers available for many such annotation tasks at once, or other cases where a limited number of queries are desired to avoid expense, damage to system being measured, those individual measurements can still taken promptly.)
Our proposed linearized network can take advantage of sequentially added annotations without requiring SGD retraining steps. Given an empirical NTK O, adding another training point (æ, y) requires nothing more than adding a row and column to the kernel. As result, computing f and following AMIMoc with an additional data point (x, v) is almost instant. This approximation can utilize the information from the label y directly while batch selection strategies cannot. (After adding a substantial number of points, we will want to retrain, but is not needed after every new data point.) We experimentally demonstrates the effectiveness of this sequential query strategy in Section 5.

---

4
Related Work
Two main approaches in pool-based active learning are uncertainty and representation- based methods. The general goal of the uncertainty-based methods is to query the most "informative" data points, thus, their acquisition functions vary depending on how to measure the informativeness of a data point. As simple but effective uncertainty-baser querying methods, posterior probability [31, 32], entropy [1]. margin sampling [33] and least confident [1]], have been widely used in practice. They do not, however, take into account how candidate data point would change a model, or how this change would interact with unseen examples. More advanced querying methods have thus been proposed as discussed in Section 2. There are also Bayesian uncertainty-bac -bssd methods, particularly Bayesian Active Learning by Disagreement (BALD) [2], which measures the mutual information between new data point and model parameters, which Gal et al. [34] propose to estimate efficiently with Monte Carlo dropout networks [35].
The goal of the representation-base methods is query examples that are the most "representative" among the unlabeled set U, hoping that doing well on those examples leads to doing well on the whole unseen dataset. Sener and Savarese [36] define a core set as batch of images that minimize the distance between unlabeled and labeled images if added to the labeled pool. Kirsch et al. [30] further expand BALD to batch setting using a greedy algorithm. Bıysk et al. [29] propose to use determinantal point processes to target diversity of the queried examples while maintaining informativeness. BADGE [4] measures the uncertainty using gradient norm but also encourage the diversity of queried images using k-means++ seeding [37].
Other approaches include that of Yoo and Kweon [38], who employ an additional loss prediction module to an existing neural network. However, the additional loss computation module can make training unstable (as we observed in some experiments). Tran al. [39] improves BALD by adding a variational autoencoder and auxiliary classifier generative adversarial network, from which a synthesized data point x' similar to the queried image x" generated.
Our proposed method is different from the previous works in that it "looks one step ahead" instead of relying on the current state of model. Perhaps the most similar proposal to ours is that of Borsos et al. [40], who propose using the infinite NTK to solve a bi-level optimization problem for semi-supervise supervisdd batch active learning. Aside from the difference in our objective functions, however, using the infinite NTK to approximate a neural network in active learning does not seem to be a good choice; as the size of training set increases, the error of the approximation can be quite large. We explore the difference between infinite and empirical NTKs experimentally in Section 5.
5 Experiment Results
Datasets. To demonstrate the effectiveness of the proposed method, we provide experimental results on three benchmark datasets for classification tasks: MNIST [8], SVHN [9], CIFARIO [10], and CIFARI00 [10]. MNIST consists of 10 hand-written digits with 60, 000 training and 10, 000 test images, at size 28 28. SVHN also consists of 10 digit numbers with 73, 257 training and 26, 032 test images, size 32> 32; it is more challenging than MNIST, containing images from pictures of house numbers, with much more variation and many distractions present. CIFAR10 10 contains 50, 000 training and 10, 000 test images, also 32 x 32 and equally split between 10 classes like airplane, frog, and truck. CIFAR100 is the same as the CIFAR10, 10, except it has 100 classes; the resolution is still 32 x 32, and images are equally split between 100 classes. The 100 classes are grouped with 20 super-classes, but we use only the 100 sub-classes in this work.
Implementation. We implement pipeline for the proposed method using PyTorch [41] and Jax [42]; our neural networks f are implemented in PyTorch, whereas the linearized models fon are implemented in Jax with the seural-tangent library [43]. We employ ResNet18 [44] and WideResNet [45] with one or two layers and maximum width of 640, which is wide enough for a linearized neural network to be good approximation, while still being powerful enough for these datasets. As we will see in our experiments, even for narrower networks, the proposed method outperforms random acquisition strategy by large margins.
As mentioned earlier, we use Ta loss, rather than cross-entropy; this allows for a faster NTK approximation, in the formulas of Section 3, rather than requiring differential equation solvers.
7

---

NN NIK
NN 1-Spp
GP
Naive
NTK Block
NTK
INNNK
(Random)
(Raddmm)
98
3hr
96
94
Acc (%)
Acc (%)
92
Time
17min
90
88
86
84
2min
82
5 Cycle
4
6
0
5 Cycle
4
7
8
(a) Naïve look-ahead acquisition versus NTK approximation. Bars show runtime per cycle.
(b) ML.MO. various models, along with madoom-acquiitton baselines.
Figure 1: Comparisons of several related approaches on MNIST.
Methods
NN NTK
NN 1-step
NN Inf NTK
GP
NN NTK
1.0000
0.0109
0.0093
0.0014
NN 1-step
0.0109
1.0000
0.6863
0.0422
NN Inf NTK
0.0093
0.6863
1.0000
0.0742
GP
0.0014
0.0422
0.0742
1.0000
Table I: The p-values of the post-hoc paired t-test.
Appropriately tuned L2 loss is as effective as cross-entropy [22]. To ensure that the empirical NTK of the training data (XCg) positive semidefinite, batch normalization layers, we freeze the current running statistics. We implement LL4AL [38] and BADGE [4] based on their publicly available code. provide anonymous code for the full pipeline the supplementary material.
Query scheme. Following active learning literature, for each query step, we randomly draw a subset from unlabeled set, and query fixed number of examples from the subset. To build batch, we take points with the highest AMTMOC scores, which we found to perform well without any batch diversity requirements. At each cycle, query 20, 1 1000, 000, and 1 000 new data points on MNIST, SVHN, CIFAR1O, and CIFAR 100 from the subset 4 400, 6 000, 6000, and 000 unlabeled data points, and initialize the labeled set L with 100, 1 000, 000, and 10 000 data points.
Making look-ahead acquisitions feasible. In Figure 1a, demonstrate the NTK approximation indeed makes it feasible to use look-ahead acquisition functions. We run the MLMOC acquisition function with naive SGD retraining (Naive) and proposed NTK approximation with (NTK) and without (NTK w/o Block) block computation in (12) on MNIST. For the naïve version, we retrain the neural network for 15 epochs using SGD. The line plots represent accuracy whereas bar plots represent wall-clock time to query data, using a NVIDIA V GPU. The NTK approximation is not only computationally efficient (more than 100 times faster than Naïve) but also yields significantly more accurate models. Although one might expect that Naïve is an upper bound for the NTK approximation, it actually "looks ahead," " in reality is hard to retrain neural network until convergence for every candidate data point; "proper" look-ahead method should perhaps look at an ensemble of several training runs, with different learning rate schedules. etc.
Comparison look-ahead acquisitions. Having seen that the empirical NTK effectively approxi- mates (even outperforms) the Naïve look-ahead acquisition function, we now show the superiority of the empirical NTK over existing look-ahead methods. In Figure 1b, we provide four look-ahead methods using MLMOC acquisition function along with their corresponding random baselines (Ran- dom). NN refers to a neural network-based. model whereas GP refers a model based on Gaussian process. Instead of using empirical NTK propose (denoted as NN NTK, bluc), Borsos et al.

---

MTW Randors
BADGE Estrupy
Marçoo LLAAL
NTX
BAD-EE
Margin
NTX
BADCE Entropy
Margin
Sandom
Eatrupy
Randum
2
Acc (96
A Aco
Acc
90
01
11
93%%
-1
11
66
55
16
-2
5 Cycle
Cycle
Cycle
(a) SVHN: 1-aayer Wet (h) CIFARIO: 2-layer WideResNet
(c) CIFARIOON 100: ResNet18
Figure 2: Comparison of the-state-of-the-ar active learning methods various benchmark datasets.
Vertical axis shows difference from random acquisition, whose accuracy is shown in text.
[40] use infinite NTK (NN Inf NTK, orange). Käding et al. [14] approximate SGD retraining using only one-step SGD update (NN I-step, green) whereas Käding et al. [15] exactly compute look-ahead acquisition using GP for regression problems. We modify their model for classification tasks, use an infinite NTK, and denote it as GP (purple). As shown in Figure Ib, ours is the only of these methods to outperform random baselines here. Neither infinite NTK nor 1-step approximation good approximation for retraining steps, especially as more data points are added. Also, although GP [15] works well on regression tasks, it struggles on classification tasks.
To validate the difference between different look-ahead strategies, we conduct Friedman's 's test followed by post-hoe paired t-test on the existing look-ahead strategies in Figure 1b: NN NTK, NN 1-step, NN Inf NTK, and GP. Friedman's 's test is nan-aarametric statistical test. The null hypothesis in our case is that the population mean of the performance of each look-ahead strategy is the same and the alternative hypothesis is that at least one population mean is different from the rest of look-ahead strategies. The p-value of the Friedman's 's test is 0.0045 (< 0.05). Hence, we reject the null hypothesis. As means at least one population mean is different from the rest of look-ahead strategies, we further conduct the post-hoc paired t-test check where the significant difference is coming from. The result of the post-hoc paired t-test is shown in Table 1. Here, the null hypothesis for each pair is that the population mean of two methods is the same. As all the p-values between ours (NN NTK) and the other methods are less than the conventional significance level (0.05), we conclude that our proposed method is significantly better than the other look-ahead strategies.
Comparison with state-of-the-art. In Figure 2, we compare the proposed NTK active learning to state-of-the- -hette- methods- - Random, Entropy, Margin sampling (Margin) [46], BADGE [4], and LL4AL [38] - on SVHN, CIFARIO, and CIFAR100 with different architectures; we provide additional results in Appendix B. For clarity, we show the difference between each method and Random. The numbers below Random line give the accuracies of Random at each cycle. As mentioned earlier, training LL4AL is often unstable due to loss computation module; in particular, it performs too poorly to show on the same plot for Figure 2b and Figure 2c. We show the instability of training LL4AL with varying learning rate in Appendix C. Each experiment is run for six different seeds; lines show the mean performance, and shading shows a 95% confidence interval for the mean. Figure 2(a) shows that the NTK method outperforms all the state-of the-art methods throughout training SVHN. A similar pattern is observed on CIFARIO 10 and CIFAR NTK is consistently comparable to or better than the best competitor methods, far outperforming existing look-ahead approaches.
Sequential query strategy. As mentioned in Section one great advantage of the NTK approxi- mation is that it can exploit additional annotations without needing to run SGD training for a neural network, which cannot be done existing active learning methods for neural networks. On MNIST, Figure 3a compares sequential NTK where the oracle provides true label for every new queried data point, to batch NTK where annotation done batch-wise as with a normal active learning setting. Sequential NTK outperforms batch NTK; especially, sequential NTK reaches more than 94% in one cycle, and in cycle 3, has already reached 96% accuracy, where batch NTK plateaus. We expect the sequential NTK can be useful in practice when annotation is much faster than SGD training.

---

W- 192
W.
640
1920
WW-320
W- 1290
(%0
5. (%6
2
0
2
6
6
100
120
140
160
180 Cycle
200
229
249
250
250
3
Cycle
Cycle
(a) Sequential vs. batch querying. (b) Performance with varying width.
(c) Diff. look-ahead strategics.
Figure 3: Further comparisons of algorithm variants MNIST.
Varying model widths. As shown in Equation (9), the NTK approximation gets closer to the dynamics of neural network as the width of the neural network increases. But, since very wide networks are computationally expensive in practice, is important to empirically demonstrate that the NTK approximation works even with reasonably narrow networks. To this end, vary the maximum width of the WideResNet with one block layer we use for the experiments as shown in Figure 3b. We observe that regardless of the maximum width, the NTK method significantly outperforms Random strategy until convergence, indicating that the NTK approximation is good enough for the purpose of active learning.
Comparison of different acquisition strategies. We compare different look-ahead acquisition functions in Figure 3c. As mentioned with Equation (13) in Section 3, MLMOC and EMOC not significantly different. As MLMOC is computationally cheaper than EMOC proportional to acquisition function. But note that,
the number of classes,
MLMOC over EMOC the proposed NTK approximation is applicable to any look-ahead acquisition functions including MLMOC, EMOC and EER. Thus, hope that method would provide framework for other researchers to build upon and propose various look-ahead active learning methods or enhance the look-ahead approximation help further tackle the problem of pool-based active learning.
6 Conclusion
We propose an algorithm to make look-ahead acquisition strategies feasible for active learning with fairly general neural network architectures. We prove that the outputs wide enough neural networks can be efficiently approximated using linearized network using empirical neural tangent kernels. We empirically show that this approximation of look-ahead strategies, while even being more accurate. Armed with this approximation, we significantly outperform previous look-ahead strategies, and achieve equal or better performance compared to the state-of-tt tftte-of-theaaat tht-he-rrt art methods on four widely used benchmark datasets in active learning regime. We also propose a new sequential active learning algorithm that decouples querying and SGD training for the first time.
least 100 times faster than naïve computation
One limitation of the NTK approximation is that it is still slower than common "myopic" active learning methods such as entropy and BADGE. Compared to our proposed method where it takes O(mxx(PLVL PU (U) using conjugate gradient kernel regression solvers, entropy requires O(PU) time (using notations in Section 3). Improving time complexity of the NTK approximation would be an interesting future work along with devising better look-ahead acquisition functions that improve performance.
Acknowledgments and Disclosure of Funding
This research was enabled in part by support, computational resources, and services provided by the Canada CIFAR Chairs program, the Natural Sciences and Engineering Research Council of Canada, Advanced Research Computing at the University of British Columbia, WestGrid, Calcul Québec, and the Digital Research Alliance of Canada. We would like to specifically thank Roman Baranowski for helping us with our computational requirements.
10

---

References
[1] Dan Wang and Yi Shang. "A New Active Labeling Method for Deep Learning." IJCNN. 2014,
pp. 112-119.
[2] Neil Houlsby, Ferene Huszár, Zoubin Ghahramani, and Máté Lengyel. "Bayesian Active Learning for Classification and Preference Learning" (2011), arXiv: 1112.5745.
[3] Burr Settles, Mark Craven, and Soumya Ray. "Multiple-instanee Active Learning." 2007,
pp. 1289-1296.
[4] Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. "Deep batch active learning by diverse, uncertain gradient lower bounds." ICLR (2020).
[5] Nicholas Roy and Andrew McCallum. "Toward Optimal Active Learning through Monte Carlo Estimation of Error Reduction." ICML. 2001.
[6] Alexander Freytag, Erik Rodner, and Joachim Denzler. "Selecting Influential Examples: Active Learning with Expected Model Output Changes." " ECCV. 2014, pp. 562-577.
[7] Arthur Jacot, Franck Gabriel, and Clément Hongler. "Neural Tangent Kernel: Convergence and Generalization in Neural Networks." NeurlPS, 2018.
[8] Li Deng. "The Mnist Database of Handwritten Digit Images for Machine Learning Research."
IEEE Signal Processing Magazine (2012), pp. 141-142.
[9] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. "Reading Digits in Natural Images with Unsupervised Feature Learning." NIPS Workshop
Deep Learning and Unsupervised Feature Leurning. 2011.
[10] Alex Krizhevsky. "Learning Multiple Layers of Features from Tiny Images" (2009).
[11] Burr Settles. "Active Learning Literature Survey" (2009).
[12] Vu-Linh Nguyen, Sébastien Destereke, and Eyke Hüllermeier. "Epistemic Uncertainty Sam-
pling." ICDS. 2019.
[13] Xiaojin Zhu, John Lafferty, and Zoubin Ghahramani. "Combining Active Learning and Semi- supervised Learning Using Gaussian Fields and Harmonic Functions." ICMLW. Vol. 3. 2003.
[14] Christoph Käding, Erik Rodner, Alexander Freytag, and Joachim Denzler. "Active and Contin- uous Exploration with Deep Neural Networks and Expected Model Output Changes" (2016).
[15] Christoph Käding, Erik Rodner, Alexander Freytag, Oliver Mothes, Björn Barz, Joachim Denzler, and Carl Zeiss AG. "Active Learning for Regression Tasks with Expected Model Output Changes." " BMVC. 2018, 103.
[16] Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard E Turner, and Zoubin Ghahramani. "Gaussian Process Behaviour in Wide Deep Neural Networks." ICLR. 2018.
arXiv: 1804.1127
[17] Radford M Neal. "Priors for Infinite Networks." Bayesian Learning for Neural Networks. 1996.
[18] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. "On Exact Computation with Infinitely Wide Neural Net." NeurIPS. 2019.
[19] Roman Novak, Lechao Xiao, Jiri Hron, Jaehoon Lee, Alexander A Alemi, Jascha Sohl- Dickstein, and Samuel Schoenholz. "Neural Tangents: Fast and Easy Infinite Neural Net- works in Python." ICLR. 2020.
[20] Greg Yang. Tensor Programs II: Neural Tangent Kernel for Any Architecture. 2020. arXiv: 2006. 14548.
[21] Greg Yang and Etai Littwin. Tensor Programs Ilb: Architectural Universality of Neural Tangent
Kernel Training Dynamics. 2021. arXiv: 2105 03703.
[22] Like Hui and Mikhail Belkin. "Evaluation of Neural Architectures Trained with Square Loss Cross-entrop in Classification Tasks." ICLR (2021).
[23] Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. "Enhanced Convolutional Neural Tangent Kernels" (2019). arXiv: 1911. 00809.
[24] Eran Malach. Pritish Kamath, Emmanuel Abbe, and Nathan Srebro. "Quantifying the Benefit of Using Differentiable Learning over Tangent Kereels." ICML. 2021. arXiv: 2103. 01210.
[25] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. "Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent." NeurIPS, 2019.

---

[26] Alexander Wei, Wei Hu, and Jacob Steinhardt. More Than Toy: Random Matrix Models Predict How Real- World Neural Representations Generalize. 2022, arXiv: 2203.06176.
[27]
Alessandro Rudi, Luigi Carratino, and Lorenzo Rosasco. "Falkon: An optimal large scale
kernel method." 2017.
[28] Jacob Gardner, Geoff Pleiss, Kilian Q Weinberger, David Bindel, and Andrew G Wilson. "GPyTorch: Blackbox matrix-matric Gaussian process inference with GPU acceleration."
NeurIPS. 2018.
[29] Erdem Brysk, Kenneth Wang, Nima Anari, and Dorsa Sadigh. "Batch Active Learning Using Determinantal Point Processes." NeurlPS (2019).
[30] Andreas Kirsch, Joost Van Amersfoort, and Yarin Gal. "Batchbald: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning." " 2019, pp. 7026-7037.
[31] David D Lewis and Jason Catlett. "Heterogeneous Uncertainty Sampling for Supervised Learning." Machine learning proceedings 1994. 1994, pp. 148-156.
[32] David D Lewis and William A Gale. "A Sequential Algorithm for Training Text Classifiers." SIGIR. 1994, pp. 3-12.
[33] Tobias Scheffer, Christian Decomain, and Stefan Wrobel. "Active Hidden Markov Models for Information Extraction." ISIDA. 2001.
[34] Yarin Gal, Riashat Islam, and Zoubin Ghahramani. "Deep Bayesian Active Learning with Image Data." " ICML. 2017, pp. 1 118--1192.
[35] Yarin Gal and Zoubin Ghahramani. "Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning." " ICML. 2016, pp. 1050-1059.
[36]
Ozan Sener and Silvio Savarese. "Active Learning for Convolutional Neural Networks: A Core-set Approach." ICLR (2018).
[37]
David Arthur and Sergei Vassilvitskii. "K-means++: the Advantages of Careful Seeding." SODA. Philadelphia, PA, USA, 2007, pp. 1027-1035.
CVPP. [38] Donggeun Yoo and In So Kweon. "Learning Loss for Active Learning." " CVPR. 2019, pp. 93- 102.
[39] Toan Tran, Thanh-Toue Do, Ian Reid, and Gustavo Carneiro. "Bayesian Generative Active Deep Learning." ICML. 2019, pp. 6295-6304.
[40] Zalán Borsos, Marco Tagliasacchi, and Andreas Krause. "Semi-supervised Batch Active Learning via Bilevel Optimization." ICASSP. IEEE. 2021.
[41] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin. Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary Vitoto, Martin Raison, Alykhan Tejani. Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. "Py'Torch An Imperative Style, High-Peeformance Deep Learning Library." NeurIPS. 2019, pp. 8024 8035.
[42] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman and Qiao Zhang. JAX: composable transformations of Python+NumPP programs. Version 0.2.5.
2018. URL.: http:/ //ttt:: com/ google/jax.
[43] Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A. Alemi, Jascha Sohl- Dickstein, and Samuel Schoenholz. "Neural Tangents: Fast and Easy Infinite Neural Net- works in Python." ICLR. 2020.
[44] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. "Deep Residual Learning for Image Recognition." CVPR. 2016.
[45] Sergey Zagoruyko and Nikos Komodakis. "Wide Residual Networks." BMVC (2016).
[46] Dan Roth and Kevin Small. "Margin-based Active Learning for Structured Output Spaces." European Conference on Machine Learning. Springer. 2006, pp. 413-424.
[47] Leslic N Smith and Nicholay Topin. "Super-convergence: Very fast training of neural networks using large learning rates." Artificial intelligence and machine learning for operations applications. 2019. arXiv: 1708. 071100.
[48] Yufan Zhou, Zhenyi Wang, Jiayi Xian, Changyou Chen, and Jinhui Xu. "Meta-learning with neural tangent kernels." NewrIPS (2021).
12


Reviews:
[{"review_id": "lvZunJpnWp", "reviewer": "Reviewer_ywhB", "summary": "The paper proposes an active learning method for neural networks that leverages neural tangent kernels to approximate the network. The proposed approach leverages lookahead to predict the expected NN output change when it is retrained with a specific input pair. The paper further proposes an acquisition function, Most Likely Model Output Change (MLMOC). The authors compare the proposed approach with state-of-the-art methods on three benchmark datasets for classification tasks and show that it either outperforms existing methods or performs equally well.", "questions": "**a)** Why is your acquisition function more suitable for a linearised network?\n\n**b)** In algorithm 1 (you should add line numbers) you mention an oracle, but I don't see any mention to it anywhere else. Where does the oracle come from?\n\n**c)** You mention lookahead but it is not clear to me if it is lookahead of: a) 1 point/label; b) n points/labels; c) 1 batch; d) n batches?\n\n**d)** What is the meaning of T in algorithm 1?\n\n**e)** Are there non-NN active learning baselines? How would your method fare against them?\n\n**f)** Why do you only use MLMOC in Figure 1.b)? Why not test also with different acquisition functions? Also, in this experiment, why do you modify the models to \"use an infinite NTK\" (line 305-206) when you know that infinite NTK perform worse? You should aim to beat the strongest baselines, not the weakest.\n\n**Comments:**\n- Line 104: typo \"the\" also show => \"they\" also show", "limitations": "Authors address some limitations of their work (time complexity). Is this method only applicable to classification tasks? How does it generalize to regression tasks?", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality:** Related work seems to be adequately cited and the differences between the paper and previous work are explained.\n\n**Quality:** The claims are somewhat well supported. For example, in line 210 it is stated that \"empirically does not hurt accuracy\" however I did not see a comparison between the acquisition functions.\n\n**Clarity:** The paper makes a good job at introducing the active learning setting however it then starts getting confusing, particularly the introduction to the lookahead setting lacks details. For instance, in Section 3, the contribution and insights of the paper are too diluted with existing work. Specifically, having subsections would be useful to distinguish the different steps more clearly: 1) sequential training of the network (theorem 3.1); 2) approximating the retrained network. I felt that the part on \"NTK approximations of retrained networks\" after remark 3.2 was diluting your conclusions with those of related work. Here perhaps you could start by discussing the limitations/conclusions of related work, explaining how you build on them. \n\n**Significance:** It is likely that other researchers will use the ideas presented in the paper or build on them.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "i1g8wHdyv8l", "reviewer": "Reviewer_xjB7", "summary": "To reduce the computational cost during active learning process, this paper proposed an interesting active learning algorithm that utilizes look-ahead strategies by large margins and approximate neural network using neural tangent kernel. So that the look-ahead strategies that can be easily adopted in classical ml tasks like EER, EMOC, could also be implemented in deep learning tasks. The authors proved that the outputs of very wide NNs can be approximated using a linearized network wit neural tangent kernels. Compared with naive computation of look-ahead strategies, this approximation is of 100 times faster and has better performance.\n", "questions": "I have several questions about this paper:\n\n1. Figure 2 with $\\Delta acc$ is really hard to read, can author just show accuracy-cycle(labeling cost) curves?\n\n2. For implementation of LL4AL, it is very strange that LL4AL perform so bad on SVHN, CIFAR10 and CIFAR100 datasets, although the author mentioned that this is because the unstably training during AL training processes, but according to [3], the LL4AL (named LPL in [3]) perform well on SVHN, CIFAR10 and CIFAR100 datasets with ResNet18 as basic learner. I wonder did the author correctly re-implemented the LL4AL with proper way, i.e., the original version <https://github.com/seominseok0429/Learning-Loss-for-Active-Learning-Pytorch> or the re-implemented version <https://github.com/Mephisto405/Learning-Loss-for-Active-Learning>.\n\n**I will give score 4 first and I hope the author could answer the question 2 properly. I will increase my score if I can be persuaded.** \n\n[3] Zhan X, Wang Q, Huang K, et al. A comparative survey of deep active learning[J]. arXiv preprint arXiv:2203.13450, 2022.\n\n", "limitations": "The author addressed the limitations but I didn't find the discussions about potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: this paper is well-written with abundant proofs/experiments to theoretically/empirically demonstrate the effectiveness of their proposed models of look-ahead strategies with large margin.\n\nWeaknesses: using NTK for approximation itself is not new in active learning, [1] use NTK approximation that construct a suitable neural embedding that determines the feature space in active learning with model selection. [2] use active learning to speed-up up the convergence for SSL deep learning algorithms, is also inspired by NTK, when the eigenvalues of the NTK are large, the convergence rate is faster. \n\n[1] Wang Z, Awasthi P, Dann C, et al. Neural active learning with performance guarantees[J]. Advances in Neural Information Processing Systems, 2021, 34: 7510-7521.\n\n[2] Kong S T, Jeon S, Lee J, et al. Relieving the Plateau: Active Semi-Supervised Learning for a Better Landscape[J]. arXiv preprint arXiv:2104.03525, 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZnSDiL4cJ5", "reviewer": "Reviewer_gpbw", "summary": "This work proposes a new method for approximating active learning acquisition strategies. Specifically, it uses the neural tangent kernel to approximate the result of retraining, namely it linearly approximates the network and mimics the new output of adding a new sample. Then it compares the network output without training on the sample (x) and the linearly approximated network with training on (x), and accordingly selects (x). ", "questions": "Please see the above questions. ", "limitations": " the authors did not well discuss the limitations, and did not discuss potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: \nUsing the neural tangent kernel to approximate the result of retraining greatly reduces the training cost and improves the efficiency of active learning, compared with the previous one. \n\nThe authors provide some experimental results to support its effectiveness. \n\n\nCons:\nUsing the neural tangent kernel method to approximate a network is actually very hard. This is also mentioned by the authors. Although the authors use a local NTK which may improve the accuracy, I still think there is a big gap between NTK network and the vanilla one, since the width is not huge in practice. So how do the authors guarantee the quality of this local NTK? For example, do the authors have some theory to guarantee or have compared vanilla network output and this new NTK network output?\n\nEfficiency: in algorithm 1, for each epoch, one needs to pass the whole unlabelled dataset to select proper samples. For each sample selection, one further needs to use eqn (12) to compute the NTK output. But when the lablled dataset is large, e.g. imagenet 1K, NTK kernel Theta would be very large. So computing its inverse may be expensive. In this way, it seems it is hard to scale this method to the large-scale dataset.\n\nThis labeled data plus unlabelled data is actually a semi-supervised setting. So it is necessary to compare with some classical semi-supervised methods, e.g. fixmatch, paws, etc. It is very valuable to see 1 ) whether there is performance improvement or drop compared with classical semi-supervised methods; 2) whether the proposed active learning can greatly improve the training efficiency of classical semi-supervised methods. For performance, it seems the results on CIFAR10 reported in this work is much lower than the vanilla fixmatch method.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BXN4tpQXUxW", "reviewer": "Reviewer_nYBt", "summary": "The work introduces a new active learning technique, that aims to use the model uncertainty over the pool of unlabeled data, after the model is retrained on a new additional point on the pool (so not a myopic strategy - but they call this a \"look ahead strategy\"). To make the strategy computationally feasible, approximations based on the neural tangent kernel are used. ", "questions": "7) In Figure 1b; how can it be that GP (Random) is performing better than GP? This must be wrong... It seems like the baseline was modified - were these modifications sensible? Would it be possible to run the experiments with the original GP for the classification tasks? I actually wonder how that would compare... It is \n\n8) In the figures, there is a shaded region indicating variability, but it is not explained how this is calculated or what this is? How many runs were used? Is this the standard error or standard deviation? Are the differences between the methods significant?  Since it is claimed that \"existing look-ahead strategies by large margins,\" I would expect to see some significant p-values from a paired t-test comparing methods pairwise (as a posthoc test after a Friedman test). \n\n9) The query scheme, I don't understand... First of all, the figures mention \"Cycles\" - why not just indicate the amount of training data available? It makes it unclear. Second, the cycles seem only defined up to 4 or 5. What happens after that? This is not specified in the \"query scheme\" (line 280). On the y-axis sometimes is given \"\\Delta Accuracy\"; what is that and how is that defined? \n\n10) The analysis and derivation of equations 6-8 seems to share many similarities with the derrivation of the EMOC strategy itself. What are the similarities? Was your work inspired by their work? Please indicate the similarities and give proper credit. \n\n", "limitations": "Please see above. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) The work introduces a technique based on an idealized criteria, which is then approximated to make it computationally feasible. However, the approximations are changed in such a way, that the idealized criteria is not being approximated anymore. This weakens the story, as we cannot explain what the active learning strategy is doing, and why it works. The performance boost seems now to come from somewhere else, but the reasoning is unclear why this is the case. Various heuristics are implemented but there is not a careful ablation study to verify where the performance gains are coming from. \n\n2) It is claimed the proposed look ahead strategy MLMOC improves matters. However, a detailed comparison with other already published lookahead strategies is missing, such as the original EMOC strategy. It is claimed that EMOC didn't work well, but no experiments are given to back up this claim. Similarly, several ad-hoc changes are made (line 208-210), which are claimed to \"empirically not hurt accuracy\" but this is not shown in the paper. Why are these results withheld? \n\n3) Some other claims that are made; which are not backed up by evidence: \n3a) \"We also suspect that, when ... is already reasonably accurate, we can “trust” the most likely label more than we can trust accurate estimation of probabilities for low-probability losses, especially when training networks with...\" (line 210).  Can we not check this?\n3b) \"These classes of models, however, tend to not work as well as modern neural networks, meaning these approaches are outperformed by simpler acquisition functions on stronger models.\" Can we check this with a Gaussian Process classification baseline with a GP acquisition strategy? E.g. compare with [5] or [6]? (line 38)\n3c) \"Sequentially adding true labels of new data gives performance substantially better than more common batch setups\" [line 58] Source? I think actually, the batch strategies can sometimes outperform sequential strategies, especially for myopic strategies that do not take diversity into account, while a batch adaptation usually does check this. \n\n4) Since the approximation allows (I think) various variants of the EMOC criteria, I was expecting to also see a comparative study on this aspect, for example GP-impact, EMOC, and some of the other baselines in from [5,6]. \n\n5) The experimental setup is not carefully described and not using the standards of the active learning field (e.g. check Settles). Check q9 for more detail. \n\n6) Strength: the approximations introduced to make look-ahead strategies feasible using the Neural Tangent Kernel, which I think is an important contribution, since it can be used to design various new active learning strategies. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept