Deep Active Learning by Leveraging Training Dynamics
Authors: Haonan Wang
Wei Huang
Ziwei Wu
Hanghang Tong
Andrew J Margenot
Jingrui He
Venue: NeurIPS 2022 Accept (2022)
Keywords: Deep Active Learning
NTK

Abstract: Active learning theories and methods have been extensively studied in classical statistical learning settings. However, deep active learning, i.e., active learning with deep learning models, is usually based on empirical criteria without solid theoretical justification, thus suffering from heavy doubts when some of those fail to provide benefits in applications. In this paper, by exploring the connection between the generalization performance and the training dynamics, we propose a theory-driven deep active learning method (dynamicAL) which selects samples to maximize training dynamics. In particular, we prove that the convergence speed of training and the generalization performance is positively correlated under the ultra-wide condition and show that maximizing the training dynamics leads to a better generalization performance. Furthermore, to scale up to large deep neural networks and data sets, we introduce two relaxations for the subset selection problem and reduce the time complexity from polynomial to constant. Empirical results show that dynamicAL not only outperforms the other baselines consistently but also scales well on large deep learning models. We hope our work inspires more attempts in bridging the theoretical findings of deep networks and practical impacts in deep active learning applications.

Deep Active Learning by Leveraging Training Dynamics
Haonan Wang Wei Huang". Ziwei Wu', Andrew Margenot
Hanghang Tong'. Jingrui He
University of Illinois Urbana-Chan Champaign University of New South Wales
(haaonnn,,aweeiwn2..nma margenot, htong. @ cillinois.ede edu 2 [weihuang, uts) I @ gmail.com
Abstract
Active learning theories and methods have been extensively studied in classical statistical learning scttings. However, deep active learning, i.c., active learning with deep learning models, is usually based on empirical criteria without solid theoretical justification, thus suffering from heavy doubts when some of those fail to provide benefits in real applications. In this paper, by exploring the connection between the generalization performance and the training dynamics, we propose a theory-driven deep active learning method (dynamicAL) which selects samples maximize training dynamics. In particular, we prove that the convergence speed of training and the generalization performance are positively correlated under the ultra-wide condition and show that maximizing the training dynamics leads to better generalization performance. Furthermore, to scale up to large deep neural networks and data sets, we introduce two relaxations for the subset selection problem and reduce the time complexity from polynomial constant. Empirical results show that dynamicAL not only outperforms the other baselines consistently but also scales well large deep learning models. We hope our work would inspire more attempts on bridging the theoretical findings of deep networks and practical impacts of deep active learning in real applications.
Introduction
Training deep learning (DL) models usually requires large amount of high-qualit labeled data [1] to optimize model with a massive number of parameters. The acquisition of such annotated data is usually time-consuming and expensive, making it unaffordable in the fields that require high domain expertise. A promising approach for minimizing the labeling effort is active learning (AL), which aims identify and label the maximally informative samples, that a high-performing classifier can be trained with minimal labeling effort [2]. Under classical statistical learning settings, theories of active learning have been extensively studied from the perspective of VC dimension [3]. As result, a variety of methods have been proposed, such as (i) the version-space-basee approaches, which require maintaining set of models [4, 5], and (ii) the clustering- based approaches, which assume that the data within the same cluster have pure labels [6].
However, the theoretical analyses for these classical settings may not hold for peramatemater deep neural networks where the traditional wisdom is ineffective [1]. For example, margin- based methods select the labeling examples in the vicinity of the learned decision boundary [7, 8]. However, in the over wer-ppaammterized regime, every labeled example could potentially be near the learned decision boundary [9]. As result, theoretically, such analysis hardly guide us design practical active
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

learning methods. Besides, empirically, multiple deep active learning works, borrowing observations and insights from the classical theories and methods, have been observed unable to outperform their passive learning counterparts in few application scenarios [10, 11].
On the other hand, the analysis of neural network's optimization and generalization performance has witnessed several exciting developments in recent years in terms of the deep learning theory [12, 13, 14]. It is shown that the training dynamies of deep neural networks using gradient descent can be characterized by the Neural Tangent Kernel (NTK) of infinite [12] or finite [15] width networks. This is further leveraged to characterize the generalization of over-parama wverpaaraeeterzee networks through Rademacher complexity analysis [13, 16]. We are therefore inspired to ask: How can we design practical and generic active learning method for deep neural networks with theoretical justifications?
To answer this question, we firstly explore the connection between the model performance on testing data and the convergence speed on training data for the wver-parameterized deep neural networks. Based on the NTK framework [12, 13], we theoretically show that if a deep neural network converges faster ("Train Faster"), then tends to have better generalization performance ("Generalize Better"), which matches the existing observations [17, 18, 19, 20, 21J. Motivated by the aforementioned connection, we first introduce Training Dynamics, the derivative of training loss with respect to iteration, as a proxy to quantitatively describe the training process. On top of it, we formally propose our generic and theoretically motivated deep active learning method, dynamicAL, which will query labels for a subset of unlabeled samples that maximally increase the training dynamics. In order to compute the training dynamics by merely using the unlabeled samples, we leverage two relaxations Eseudo-labeling and Subset Approximation to solve this non-trivial subset selection problem. Our relaxed approaches are capable of effectively estimating the training dynamics as well as efficiently solving the subset selection problem by reducing the complexity from O(N²) to (()).
iroorticall-mmoovvateedd
In theory, we coin a new term Alignment to measure the length of the label vector's projection on the neural tangent kernel space. Then, we demonstrate that higher alignment usually comes with a faster convergence speed and a lower generalization bound. Furthermore, with the help of the maximum mean discrepancy [22], we extend the previous analysis to an active learning setting where the i.i.d. assumption may not hold. Finally, we show that alignment is positively correlated with our active learning goal, training dynamics, which implies that maximizing training dynamics will lead to better generalization performance.
Regarding experiments, we have empirically verified our theory by conducting extensive experiments on three datasets, CIFARIO [23], SVHN [24], and Caltech101 [25] using three types of network structures: vanilla CNN, ResNet [26], and VGG [27]. We first show that the result of the subset selection problem delivered by the subset approximation is close to the global optimal solution. Furthermore, under the active learning setting, our method not only outperforms other baselines but also scales well on large deep learning models.
The main contributions of our paper can be summarized as follows:
We propose a encory-driven deep active learning method, dynamicAL. inspired by the observation of "train faster, generalize better". To this end, we introduce the Training Dynamics, a proxy to describe the training process.
We demonstrate that the convergence speed of training and the generalization performance is strongly (positively) correlated under the ultra-wide condition; we also show that maximizing the training dynamics will lead a lower generalization error in the scenario of active learning.
Our method is easy to implement. We conduct extensive experiments to evaluate the effectiveness of dynamicAL and empirically show that our method consistently outperforms other methods in a wide range of active learning settings.
2 Background
Notation. We use the random variable E X to represent the input data feature and y E y as the label where K is the number of classes and [K] := {1, ..., K}. We are given non-degenerated data source D with unknown distribution p(., y). We further denote the concatenation of as x = 12, T and that of y as Y [,1, .... yMr] We consider a deep learning classifier ho(x) = argmax o (f(;;) 0))= : x + y parameterized by 0 E TRP, where a1.) is the softmax function
and f is neural network. Let & be the Kronecker Product and 1x E IR K X be an identity matrix.

---

Active learning. The goal of active learning is to improve the learning efficiency of a model with limited labeling budget. In this work, we consider the pool-based AL setup, where finite data set S = (11 w))r with M points are i.i.d. sampled from p(a,, y) as the (initial) labeled set. The AL model receives an unlabeled data set U sampled from p(æ) and request labels according to p(ylæ) for any U in each query round. There are R rounds in total, and for each round, query set Q consisting of unlabeled samples can be queried. The total budget size B x R.
Neural Tangent Kernel. The Neural Tangent Kernel [12] has been widely applied to analyze the dynamics of neural networks. If a neural network is sufficiently wide, properly initialized, and trained by gradient descent with infinitesimal step size (i.e., gradient flow), then the neural network is equivalent to kernel regression predictor with a deterministic kernel (-,.)), called Neural Tangent Kernel (NTK). When minimizing the mean squared error loss, at the iteration t, the dynamics of the neural network has a foosed-form expression:
df df())((t) dt
()) - ))),
(1)
where ((t) denotes the parameter of the neural network at iteration t, (x, E R
is called the empirical NTK and XC,' x') - (er ((t) Vof'(z';(()) is the inner product of the gradient of the i-th class probability and the gradient of the j-th class probability for two samples x, x' E X' and j E [K]. The time-variant kernel .-. is equivalent to the (time-invariant) NTK with high probability, i.e. if the neural network is sufficiently wide and properly initialized, then:
X, (X) @ Ix-
The final learned neural network iteration t, is equivalent to the kernel regression solution with respect to the NTK [14]. For any imput x and training data {X, }} we have,
f(2; (t)) O (z, X) (I - ) -
where is the learning rate, (xx X) is the NTK matrix between input x and all samples in training data X.
3 Method
In section 3.1, we introduce the notion of training dynamics which can be used to describe the training process. Then, in section 3.2, based on the training dynamics, we propose dynamicAL. In section 3.3, we discuss the connection between dynamicAL. and existing deep active learning methods.
3.1 Training dynamics
In this section, we introduce the notion of training dynamics. The cross-entropy loss over the labeled set S is defined as:
T(()) = Σ
(4)
Σ
vi logo' (f 0)),
where o² o'((x;;)) 0)) = exp( (m=f)))(r)))
Σ, (x:M)) We first analyze the dynamics of the training loss, with respect
to iteration f, on one labeled sample (derivation is in Appendix A.
{ 0).
- - ((
(5)
Øt
For neural networks trained by gradient descent, if the learning rate is small, then V,0 = - - 0: =
0 (esouies {(((==00).:) Taking the partial derivative of the training loss with respect to the parameters, we have (the derivation of the following equation can be found in Appendix A.2):
-17
86
@0(f(x;; (x)
(o'(f(=; v²) (f;(x;)) JE(K]
Σ
(6)
00
00
3

---

Therefore, we can further get the following result for the dynamics of training loss:
f 0). - E (
E Val( [all( - vf.).
0t
(0/ (8,
(7)
Furthermore, we define d' i-th class. Then, the training dynamics (dynamics training loss) over training set S, computed with the empirical NTK (X, x),, is denoted by G(S) E R:
Y and Y is the label vector of all samples for
alls(=1;)),w)
G(S) 1J (FL-D))
Σ
Øt
(8)
3.2 Active learning by activating training dynamics
Before we present dynamicAL, we state Proposition 1, which serves as the theoretical guidance for dynamicAL and will be proved in Section 4.
Proposition 1. For deep neural networks, converging faster leads to a lower worst-case generaliza- tion error.
Motivated by the connection between convergence speed and generalization performance, we propose the general-purpose active learning method, dynamicAL, which aims to accelerate the convergence by querying labels for unlabeled samples. As we described in the previous section, the training dynamics can be used describe the training process. Therefore, we employ the training dynamics proxy to design an active learning method. Specifically, at each query round, dynamicAL will query labels for samples which maximize the training dynamics G(S).....
= argmaxocu G(S (), s.t. |Q] 12 b,
where Q is the corresponding data set for Q with ground ground-truth truth labels. Notice that when applying the above objective in practice, we are facing two major challenges. First, G(S U Q) cannot be directly computed, because the label information of unlabeled examples is not available before the query. Second, the subset selection problem can be computationally prohibitive if enumerating all possible sets with size b. Therefore, we employ the following two relaxations make this maximization problem to be solved with constant time complexity.
Pseudo labeling. To estimate the training dynamics, Ia in the unlabeled data set U to compute G. Note, the effectiveness of this adaptation has been demonstrated in the recent gradient- based methods [11, 28], which compute the gradient as if the model's is current prediction on the example is the true label. Therefore, the maximization problem in Equation (9) is changed to,
the predicted label dr, for sample
Q = urgmax G(S Q
(10)
where Q the corresponding data set for Q with pseudo labels Vz-
Subset approximation. The subset selection problem of Equation (10) still requires enumerating all possible subsets of U with size b, which is O(n²). We simplify the selection problem the following problem without causing any change on the result,
org
argmax A AQQis)
(11)
where (Q UQ) - G(S) is defined as the change of training dynamics. We approximate the change of training dynamics caused by query set Q using the summation of the change of training dynamics caused by each sample in the query set. Then the maximization problem can be converted to Equation (12) which can be solved by a greedy algorithm with O(b).
argmaxocu
Σ
All(2, (H()))))) s.t. IQ]
(12)
(x.D)E
To further show the approximated result reasonably good, we decompose the change of training dynamics as (derivation in Appendix A.4):
AQ = Σ
All(e, +
Σ
d( () (e,
(13)
(z.j)e
(x.0)

---

where (2, is the empirical NTK. The first term in the right hand side is the approximated change of training dynamics. Then, we further define the Approximation Ratio (14) which measures the approximation quality,
R(QIS) Eimme (((2,)))15) AQ)(S)
(14)
We empirically measure the expectation of the Approximation Ratio on two data sets with two different neural networks under three different batch sizes. As shown Figure 4, the expectation Eq-u ((Q S) R when the model is converged. Therefore, the approximated result delivered by the greedy algorithm is close the global optimal solution of the original maximization problem, Equation (10), especially when the model is converged.
Based the above two approximations, we present the proposed method dynamicAL in Algorithm 1. As described below, the algorithm starts by training a neural network f(:;0) on the initial labeled set S until convergence. Then, for every unlabeled sample Iu., we compute pseudo label Uu, and the change of training dynamics A (1) Vu) [S)) After that, dynamicAA. will query labels for top-b samples causing the maximal change training dynamics, train the neural network on the extended labeled set, and repeat the process. Note, to keep close to the theoretical analysis, re-initialization is not used after each query, which also enables dynamicAL to get rid of the computational overhead of retraining the deep neural networks every time.
Algorithm Deep Active Learning by Leveraging Training Dynamics
Input: Neural network ((:0), unlabeled sample set U, initial labeled set S, number of query round R. query batch size b.
for r = to R do
Train f(=; ()) on S with cross-entropy loss until convergence.
for E U do
Compute its pseudo label fh.. = argmax (zi 0). Compute A (((Tu, SS).
end for
Select b query samples Q with the highest A values, and request their labels from the oracle. Update the labeled data set S = S SUQ.
end for
return Final model ():
3.3 Relation existing methods
Although existing deep active learning methods are usually designed based on heuristic criteria, some of them have empirically shown their effectiveness [11, 29, 30]. We surprisingly found that our method dynamicAL has some connections with those existing methods from the perspective of active learning criterion. The proposed active learning criterion Equation (12)
aeeoreticalll-motiivle
can be explicitly written as (derivation in Appendix A.5):
((((E.. =
D.) +
Σ Vol(s(r.;))),n) in)) (a)( (F (x.A)ES
(15)
Note. The first term of the right-hand side can be interpreted as the square of gradient length (2- norm) which reflects the uncertainty of the model the example and has been wildly used as active learning criterion in some existing works [30, 11, 31]. The second term can be viewed as the influence function [32] with identity hessian matrix. And recently, [29] has empirically shown that the effectiveness of using the influence function with identity hessian matrix as active learning criterion. We hope our theoretical analysis also shed some light on the interpretation of previous methods.
4 Theoretical analysis
In this section, we study the correlation between the convergence rate of the training loss and the generalization error under the ultra-wide condition [12, 13]. We define a measure named alignment
5

---

to quantify the convergence rate and further show its connection with generalization bound. The analysis provides a theoretical guarantee for the phenomenon of "Train Faster, Generalize Better" as well as our active learning method dynamicAL. with a rigorous treatment. Finally, we show that the active learning proxy, training dynamics, is correlated with alignment, which indicates that increasing the training dynamics leads to larger convergence rate and better generalization performance. We leave all proofs of theorems and details of verification experiments in Appendix B and respectively.
4.1 Train faster provably generalize better
Given an ultra-wide neural network, the gradient descent can achieve a near-zero training error [12, 33] and its generalization ability in unseen data can be bounded [13]. It is shown that both the convergence and generalization of a neural network can be analyzed using the NTK [13]. However, the question what is the relation between the convergence rate and the generalization bound has not been answered. We formally give a solution by introducing the concept of alignment, which is defined as follows:
Definition 1 (Alignment). Given data set S = {X,Y), Y. the alignment is measure of correlation between X and Y projected in the NTK space. In particular, the alignment can be computed by A(X,Y) = Tr|y (T)Y
Σ E Ax yk
In the following, we will demonstrate why "Train Faster" leads to "Generalize Better" through aligmment. In particular, the relation of the convergence rate and the generalization bound with alignment is analyzed. The convergence rate of gradient descent for ultra-wide networks is presented in following lemma:
Lemma (Convergence Analysis with NTK, Theorem 4.1 of [13]). Suppose Xu -mmia (+) > 0 for all subsets of data samples. For 8 E (0, 1), if m- = 2 n² least 1 8, the network can achieve near-zero training error,
xg54,2) and 1j O 2g ), with probability at
K - k=1
| f(x:(())2+
(16)
where n denotes the number of training samples and m denotes the width of hidden layers. The NTK o VVAV with A {X:3 diagonal matrix of eigenvalues and V (o a unitary matrix.
In this lemma, we take mean square error (MSE) loss as an example for the convenience of illustration. The conclusion can be extended to other loss functions such as cross-entropy loss (see Appendix B.2 in [14]). From the lemma, we find the convergence rate is governed by the dominant term (16) as
YX = En - 1² (प) yk), which is correlated with the alignment:
Theorem 1 (Relationship between the convergence rate and alignment). Under the same assumptions as Lemma 1, the convergence rate described by & satisfies,
Y1 (01-,t,X(XX)) Y) S (X, S YI
(17)
Remark 1. In the above theorem, we demonstrate that the aligument can measure the convergence rate. Especially, we find that both the upper bound and the lower bound of error Σx(X, Y) are inversely proportional the alignment, which implies that higher alignment will lead to achieving faster convergence.
Now we analyze the generalization performance of the proposed method through complexity analysis. We demonstrate that the ultra-wide networks can achieve a reasonable generalization bound.
Lemma (Generalization bound with NTK, Theorem 5.1 of [13]. Suppose data S {12, u:)) i.i.d. samples from non-degenerate distribution p(æ, y), and 2 poly (n,, 1 - Consider any loss function & IR x + [0, 1) that is 1-Lipschitz, then with probability at least 1 - over the random initialization, the network trained by gradient descent for T Q 201 log ạ) iterations has population risk Cp = ((E..)~p(a [8( Pr(4 (x; 0), 0))y) that is bounded as follows:
(X, X)Y 2Tr C 1-1(X
+ (o
log Ago
S
(18)
73

---

In this lemma, we show that the dominant term in the generalization upper bound is B(X,Y) = 1V In the following theorem, we further prove that this bound is inversely proportional n to the alignment Y).
Theorem 2 (Relationship between the generalization bound and alignment). Under the same assump-
tions as in Lemma 2, if we define the generalization upper bound as B(X.Y) = v TT 2 iY] then it can be bounded with the alignment as follows:
YY Th (
Amaz T
A(X,Y) S
(19)
Amnin
A(X,Y)
Remark 2. Theorems I and 2 reveal that the cause for the correlated phenomenons "Train Faster" and "Generalize Better" is the projection of label vector on the NTK space (alignment).
4.2 "Tain Faster, Generalize Better " for active learning
B MMD
In the NTK framework [13], the empirical average requires data in S is i..d. samples (Lemma 2). However, this assump- tion may not hold in the active learning setting with multiple query rounds, because the training data is composed by i.i.d. sampled initial label set and samples queried by active learn- ing policy. To extend the previous analysis principle to active learning, follow [34] to reformulate the Lemma 2 as:
0.40
(llett)
63. 25
20.30
0.35
0.30
0.25
0,002
0.20
0.15
0.10
Co S (Cop 11.-La) Log) + 2TT T (XX,X
+ to (V log
b-200
b-1000
0.05
n
n
(20)
Figure 1: Comparison between Em-
where Cy (.. (()))))))) (e] 0), y)], q(x,,) y) denotes the
pirical Generalization Bound and MMD.
data distribution after query, and X, Y includes initial training samples and samples after query. There is new term in the upper bound, which is the difference between the true risk under different data distributions.
Cp f. =F -eeew)-pte (C( (x; 0). v)l (e 0), v)]
(21)
Though in active learning the data distribution for the labeled samples may be different from the original distribution, they share the same conditional probability p(ylær). We define g(z) I, (f(;; 0), y)p(y( dy. and then we have:
C, Lo = (1l))(x)dd g(x))(x))dz.
(22)
To measure the distance between two distributions, we employ the Maximum Mean Discrepancy (MMD) with neural tangent kernel [35] (derivation in Appendix B.3).
E - Ly S MMD(S., He) + (V C'In(1/0)
(23)
n
Slightly overloading the notation, we denote the initial labeled set as So. He as the associated Repro- ducing Kernel Hilbert Space for the NTK O and x' E S, Oz x²) I C. Note, MMD(S,, S, He) the empirical measure for MMD(p(a ) 9 (xx). He). We empirically compute MMD and the dom- inant term of the generalization upper bound B under the active learning setting with method dy As shown in Figure 1, on CIFARIO with a CNN target model (three convolutional layers with global average pooling), the initial labeled set size |S| 500, query round R and budget size b E (250, 500, 1000), we observe that, under different active learning settings, the MMD is always much smaller than the B. Besides, we further investigate the MMD and B for R 2 2 and observe the similar results. Therefore, the lemma still holds for the target model with dynamicAL. More results and discussions for R > 2 are in Appendix E.4 and the computation details of MMD and NTK are in Appendix D.I.
7

---

4.3 Alignment and training dynamics in active learning
In this section, we show the relationship between the align- ment and the training dynamics. To be consistent with the previous theoretical analysis (Theorem and 2), we use the training dynamics with mean square error under the ultra- width condition, which can be expressed as (MSE(S) =
12000
x[X]]x YIlKa) X
Tr (f(X; 0) - Y) T (X,, (X((X; 0) - Y) Due to the lim- ited space, we leave the derivation in Appendix A.3. To further
11000-
quantitatively evaluate the correlation between (assæ(S U Q
1000-
and A[X]] Y))))),
utilize the Kendall T coefficient [36]
to empirically measure their relation. As shown in Figure 2, for CNN on CIFAR10 with active learning setting, where
10000
T= 0.57
|S| 500 and Q 250, there is strong agreement between GMSE U Q) and XX ()))). which further indicates that increasing the training dynamics will lead to a faster conver- gence and better generalization performance. More details about this verification experiment are Appendix D.2.
1000 1200 1400 1800
G(SU Q)
Figure 2: Relation between Align- ment and Training Dynamies.
Experiments
5.1 Experiment setup
Baselines. We compare dynamicAL with the following eight baselines: Random, Corset, Confidence Sampling (Conf), Margin Sampling (Marg), Entropy, and Active Learning by Learning (ALBL), Batch Active learning by Diverse Gradient Embeddings (BADGE). Description of baseline methods is in Appendix E.
Data sets and Target Model. We evaluate all the methods on three benchmark data sets, namely, CIFARIO [23], SVHN [24], and Caltech101 [25]. We use accuracy as the evaluation metric and report the mean value of 5 runs. We consider three neural network architectures: vanilla CNN,
ResNet18 [26], and VGGI 1 [27]. For each model, we keep the hyper-parameters used in their official implementations. More information about the implementation is in Appendix C.I.
Active Learning Protocol. Following the previous evaluation protocol [1]], we compare all those active learning methods in a batch-mode setup with an initial set size M = 500 for all those three data sets, batch size b varying from {250, 500, 1000]. For the selection of test set, we use the benchmark
split of the CIFARIO [23]. SVHN [24] and sample 20% from each class to form the test set for the Caltech101 [25].
5.2 Results and analysis
The main experimental results have been provided plots due to the limited space. We also provide tables in which we report the mean and standard deviation for each plot Appendix E.3.
Overall results. The average test accuracy at each query round is shown in Figure 3. Our method dynamicAL can consistently outperform other methods for all query rounds. This suggests that dynamicAL is good choice regardless of the labeling budget. And, we notice dynamicAL can work well on data sets with a large class number, such as Caltech 101. However, the previous state-of-the-an method, BADGE, cannot be scaled up to those data sets, because the required memory is linear with the number of classes. Besides, because dynamicAL depends on pseudo labeling, a relatively large initial labeled set provide advantages for dynamicAL. Therefore, it is important to examine whether dynamicAL can work well with small initial labeled set. As shown in Figure 3, dynamicAL is able to work well with relatively small initial labeled set (M 500). Due to the limited space, we only show the result under three different settings in Figure 3. More evaluation results are in Appendix E.2. Moreover, although the re-initialization trick makes dynamicAL deviate from the dynamics analysis, we investigate the effect of it to dynamicAL and provide the empirical observations and analysis in Appendix E.5.
Effect of query size and query round. Given the total label budget B, the increasing of query size always Ieads to the decreasing of query round. We study the influence of different query size
8

---

(3/5416, CAN Query Barm Sow Sec, Intaa See Kow 991
CW-R Visi. Query Bornh Sov Int Ser Spa
CaRedioo Fratedt Cuery baidh Sec 500. Iice 300
Rambom
Rancom
Core
Bandom
Narg
Compett
Ayramical
Synamich
25
Query Round
Quary Round
Query Round
Figure 3: Active learning test accuracy versus the number query rounds for range of conditions.
and query round on dynamicAL from two perspectives. First, we study the expected approximation ratio with different query batch sizes on different data sets. As shown in Figure under different settings the expected approximation ratio always converges to I with the increase of training epochs, which further indicates that the query set selected by using the approximated change of training dynamics is a reasonably good result for the query set selection problem. Second, we study influence of query round for actual performance of target models. The performance for different target models on different data sets with total budge size B 1000 is shown in Table 1. For certain query budget, our active learning algorithm can be further improved if more query rounds are allowed.
CIFAR10, ResNet
SVHN,
Batch Size 2-0
Batch Size b-250
Batch Size b=500
Batch Size b=300
Batch Size 6=1000
Batch Size 1=1000
10
15
20
25
30
40
50
10
Epoch
Epoch
Figure 4: The Expectation of the Approximation Ratio with different query batch sizes
Table I: Accuracy of dynamicAL with different query batch size b.
Setting
CIFARIO+CNN CIFARIO+Resnet SVHN+VGG Caltech101+
= 10, b- = 100
36.84
40.92
76.34
37.06
R 6- 500 R = 4, h- 250
36.72
40.78
75.26
36.48
36.71
40.46
74.10
35,91
6 1000
36.67
40.09
70.04
33.82
Comparison with different variants. The active learning criterion of dynamicAL can written as E(syes (=; 0,), Ill + +VVelff (f f), b.) (f (z; 0). We empirically show the performance for y E {0, 1, oo} in Figure 5. With 7 0, the criterion is close the expected gradient length method [31]. And with 7 = co, the selected samples are same with the samples selected by using the influence function with identity hessian matrix criterion [29]. As shown in Figure 5, the model achieves the best performance with indicated by the theoretical analysis (Equation 15). The result confirms the importance of theoretical analysis for the design of deep active learning methods.
2, which is aligned with the value
Related work
Neural Tangent Kernel (NTK): Recent study has shown that under proper conditions, an infinite- width neural network can be simplified as linear model with Neural Tangent Kernel (NTK) [12].
Since then, NTK has become powerful theoretical tool to analyze the behavior of deep learning ar- chitecture (CNN, GNN, RNN) [33, 37, 38], random initialization [39], stochastic neural network [40], and graph neural network [41] from its output dynamics and to characterize the convergence and generalization error [13]. Besides, [15] studies the finite-width NTK, aiming at making the NTK more practical.

---

CHARIO, CNN, Batch Size:
SWHN. VGS, Batch
CIFARIO. Reshet, Batch Size:
55-
Accuraccy 15
Accurayy (84)
Test Acturacy (%)
-2-
-0
Qurry Round
Query Round
Query Round
Figure 5: Test Accuracy of different variants.
Active Learning: Active learning aims at interactively query labels for unlabeled data points to maximize model performances [2]. Among others, there are two popular strategies for active learning, i.e. diversity sampling [42, 43, 44] and uncertainty sampling [45, 46, 47, 11, 48, 49, 29]. Recently, several papers proposed to use gradient to measure uncertainty [49, 11, 29]. However, those methods need to compute gradient for each class, and thus they can hardly be applied on data sets with large class number. Besides, recent works [50, 51] leverage NTK to analyze contextual bandit with streaming data, which are hard to be applied into our pool-based based setting.
7 Conclusion
In this work, we bridge the gap between the theoretic findings of deep neural networks and real- world deep active learning applications. By exploring the connection between the generalization performance and the training dynamics, we propose theory-driven method, dynamicAL, which selects samples to maximize training dynamics. We prove that the convergence speed of training and generalization performance is (positively) strongly correlated under the ultra-wide condition and we show that maximizing the training dynamics will lead to lower generalization error. Empirically, our work shows that dynamicAL not only consistently outperforms strong basclines across various setting, but also scales well on large deep learning models.
8 Acknowledgment
This work is supported by National Science Foundation (ISS-1947203, IIS-21 17902, IIS-2137468, IIS-2134079, and CNS-2125626), a joint ACES-ICGA funding initiative via USDA Hatch ILLU- 802-946, and Agriculture and Food Research Initiative (AFRI) grant no. 2020-67021-32799/proe accession no. 1024178 from the USDA National Institute of Food and Agriculture. The views and conclusions are those of the authors and should not be interpreted as representing the official policies of the funding agencies or the government.
References
[1] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
[2] Burr Settles. Active learning literature survey. Technical report, University of Wisconsin- Madison, 2009.
[3] Steve Hanneke al. Theory of disagreement-based active learning. Foundations and Trends in Machine Learning, (1233)11313304 2014.
[4] David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 15(2):201-221, 1994.
[5] Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-89) 2009.
[6] Sanjoy Dasgupta and Daniel Hsu. Hierarchical sampling for active learning. In International conference on Machine learning, pages 208-215, 2008.
10

---

[7] Maria-Florina Balcan, Andrei Z. Broder, and Tong Zhang. Margin based active learning. In Conference on Learning Theory, volume 4539, pages 35-50, 2007.
[8] Maria-Florina Balcan and Philip M. Long. Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory, volume 30, pages 288-316, 2013.
[9] Mina Karzand and Robert D. Nowak. Active learning in the overparameterized and interpolating regime. CoRR, abs//905. 12782, 2019.
[10] Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In Neural Information Processing Systems, pages 7024-7035, 2019.
[11] Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. International Conference Learning Representations, 2020.
[12] Arthur Jacot, Franek Gabriel, and Clément Hongler. Neural tangent kernel: convergence and generalization in neural networks. In Neural Information Processing Systems, pages 8580-8589, 2018.
[13] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analy- sis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, volume 97, pages 322-332, 2019.
[14] Jachoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Neural Information Processing Systems, pages 2019.
[15] Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kemnl.. In International Conference on Learning Representations, 2020.
[16] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 32:10836-10846, 2019.
[17] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, volume 48, pages 1225-1234, 2016.
[18] Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, volume 70, pages 1159-2167, 2017.
[19] Clare Lyle, Lisa Schut, Robin Ru, Yarin Gal, and Mark van der Wilk. bayesian perspective on training speed and model selection. In Neural Information Processing Systems, 2020.
[20] Binxin Ru, Clare Lyle, Lisa Schut, Mark van der Wilk, and Yarin Gal. Revisiting the train loss: efficient performance estimator for neural architecture search. arXiv preprint arXiv:2006.0444 04492, 2020.
[21] Keyulu Xu. Mozhi Zhang, Stefanie Jegelka, and Kenji Kawaguchi. Optimization of graph neural networks: Implicit acceleration by skip connections and more depth. In International Conference on Machine Learning, volume 139, pages 11592-11602, 2021.
[22] Karsten M Borgwardt, Arthur Gretton, Malte J Rasch, Hans-Peter Kriegel, Bernhard Schölkopf, and Alex I Smola. Integrating structured biological data by kernel maximum mean discrepancy. Bioinformatics, (4(4))e49-e$5 2006.
[23] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.

---

[24] Yuval Netzer, Tao Wang, Adam Coates, Ro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits natural images with unsupervised feature learning, 2011.
[25] Li Fei-Fei, Rob Fergus, and Pietro Perona. Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories. In 2004 conference on computer vision and pattern recognition workshop, pages 178-178. IEEE, 2004.
[26] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Puttern Recognition, pages 770-778, 2016.
[27] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large- image recognition. In International Conference on Learning Representations, 2015.
[28] Fangzhou Mu, Yingyu Liang, and Yin Li. Gradients as features for deep representation learning. In International Conference on Learning Represenlutions, 2020.
[29] Zhuoming Liu, Hao Ding, Huaping Zhong, Weijia Li, Jifeng Dai, and Conghui He. Influence selection for active learning. arXiv preprint arXiv:2108.090:20 2021.
[30] Jiaji Huang, Rewon Child, Vinay Rao, Hairong Liu, Sanjeev Satheesh, and Adam Coates. Active learning for speech recognition: the power of gradients. arXiv preprint arXiv:1612.0333 2016.
[31] Megh Shukla. Egl++: Extending expected gradient length to active learning for human pose estimation. arXiv preprint (04903300 2021.
[32] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, volume 70, pages 1885-1894, 2017.
[33] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Neural Information Processing Systems, pages 8139-8144 8148, 2019.
[34] Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode active learning. ACM Transactions on Knowledge Discovery from Data, 9(3):1-23, 2015,
[35] Sheng Jia, Ehsan Nezhadarya, Yuhuai Wu, and Jimmy Ba. Efficient statistical tests: A neural tangent kernel approach. In International Conference on Machine Learning, volume 139, pages 4893-4903, 2021.
[36] Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81-93) 1938.
[37] Simon S Du, Kangeheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. arXiv preprint 1905. 13192, 2019.
[38] Sina Alemohammad, Zichao Wang, Randall Balestriero, and Richard Baraniuk. The recurrent neural tangent kernel. In International Conference on Learning Representations, 2020.
[39] Wei Huang, Weitao Du, and Richard Yi Da Xu. On the neural tangent kernel of deep networks with orthogonal initialization. arXiv preprint arXiv:2004.0586 2020.
[40] Wei Huang, Chunrui Liu, Yilan Chen, Tianyu Liu, and Richard Yi Da Xu. Demystify op- timization and generalization of over-parameterized pac-bayesian learning. arXiv preprint arXiv:2202.01958. 2022.
[41] Wei Huang. Yayong Li, Weitao Du, Richard Yi Da Xu, Jie Yin, Ling Chen, and Miao Zhang. Towards deepening graph neural networks: A gatk-based optimization perspective. arXiv preprint 21X1v:2103.03111, 2021.
[42] Bo Du, Zengmao Wang, Lefei Zhang, Liangpei Zhang, Wei Liu, Jialie Shen, and Dacheng Tao. Exploring representativeness and informativeness for active learning. IEEE transactions on cybernetics, 47(1):14-26, 2015.
12

---

[43] Riccardo Volpi, Hongseok Namkoong, Ozan Sener, John C. Duchi, Vittorio Murino, and Silvio Savarese. Generalizing to unseen domains via adversarial data augmentation. In Neural Information Processing Systems, pages 5339-5349, 2018.
[44] Fedor Zhdanov. Diverse mini- batch active learning. arXiv preprint
2019.
[45] Nicholas Roy and Andrew McCallum. Toward optimal active learning through sampling estimation of error reduction. In International Conference on Machine Learning, pages 441- 448, 2001.
[46] Jingbo Zhu and Matthew Ma. Uncertainty-base active learning with instability estimation for text classification. ACM Transactions on Speech and Language Processing (TSLP), 8(4):1-21, 2012.
[47] Yazhou Yang and Marco Loog. Active learning using uncertainty information. In International Conference Pattern Recognition, pages 2646-2651, 2016.
[48] Donggeun Yoo and In So Kweon. Learning loss for active learning. In IEEE Conference on Computer Vision and Pattern Recognition, pages 93-102, 2019.
[49] Burr Settles, Mark Craven, and Soumya Ray. Multiple-inss instance active learning. In Neural Information Processing Systems, pages 1289-1296, 2007.
[50] Pranjal Awasthi, Christoph Dann, Claudio Gentile, Ayush Sekhari, and Zhilei Wang. Neural active learning with performance guarantees. arXiv preprint arXiv:2/06.03243, 2021.
[51] Yikun Ban, Yuheng Zhang, Hanghang Tong, Arindam Banerjee, and Jingrui He. Improved algorithms for neural active learning. 2022.
[52] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[53] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773 2012.
[54] Felix Dangel, Frederik Kunstner, and Philipp Hennig. BackPACK: Packing more into backprop. In International Conference on Learning Representations, 2020.
[55] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[56] Alexandre Rame, Corentin Dancette, and Matthieu Cord. Fishr: Invariant gradient variances for out-of-distributiin generalization. In International Conference Machine Learning, pages 18347-18377. PMLR, 2022.
[57] Pranav Subramani, Nicholas Vadivelu, and Gautam Kamath. Enabling fast differentially private sgd via just-in-time compilation and vectorization. Advances in Neural Information Processing Systems, 34:26409-26421, 2021.
[58] Amir Zandieh, Insu Han, Haim Avron, Neta Shoham, Chaewon Kim, and Jinwoo Shin. Scaling neural tangent kernels via sketching and random features. arXiv preprint arXiv:2106.07880. 2021.
[59] R Botsch. Chapter 12: Significance and measures of association. Scopes and Methods of Political Science, 2011.
[60] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018.
[61] Dan Wang and Shang. new active labeling method for deep learning. In International Joint Conference Neural Networks, pages 112-119, 2014.
13

---

[62] Dan Roth and Kevin Small. Margin-base based active learning for structured output spaces. In Machine Learning: ECML 2006, 17th European Conference on Machine Learning. Berlin, Germany, September 18-22, 2006, Proceedings, volume 4212, pages 413-424, 2006.
[63] Wei-Ning Hsu and Hsuan-Tien Lin. Active learning by learning. In AAAI Conference Artificial Intelligence, pages
2015.
[64] Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: empirical study. Advances in Neural Information Processing Systems, 33:15156-15172 2020.
[65] Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani. Daniel M Roy. and Surya Ganguli. Deep learning versus kernel learning: empirical study of loss landscape geometry and the time evolution of the neural tangent kernel. Advances in Neural Information Processing Systems, 33:5850-558 1-1501 2020.
[66] Daniel S Park, Jaehoon Lee, Daiyi Peng. Yuan Cao, and Jascha Sohl-Dickstein. Towards nngp-guided neural architecture search. arXiv preprint arXiv:2011.06006, 2020.
[67] Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective. arXiv preprint arXiv:2102.11535, 2021.
[68] Xiangning Chen, Cho-Jui Hsieh, and Boqing Gong. When vision transformers outperform resnets without pre-training or strong data augmentations. arXiv preprini 1rX4v. 2021.
[69] Aditya Deshpande, Alessandro Achille, Avinash Ravichandran, Hao Li, Luca Zancato, Charless Fowlkes, Rahul Bhotika, Stefano Soatto, and Pietro Perona. A linearized framework and new benchmark for model selection for fine-tuning, arXiv preprint arXiv: 102. 102.00084, 2021.
14


Reviews:
[{"review_id": "gPmbnRlrCV4", "reviewer": "Reviewer_GLZg", "summary": "The paper proposes an active learning method for deep learning (named dynamicAL) that selects data points which maximize the training dynamics. The paper proves a relationship between the convergence speed of training and generalization and shows experimentally that dynamicAL can outperform other popular active learning baselines.", "questions": "- Can you prove formal results similar to Theorem 1 and 2 for the active learning setting in Section 4.2 and 4.3 ?", "limitations": "There is no potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The method proposed in the paper is novel and works well compared to other baselines.\n- The experiments are extensive.\n- The paper is well-written.\n\nWeaknesses:\n- The main theoretical results in Section 4.1 (Theorem 1 and 2) are only for iid data, which do not hold for the active learning setting. Although Section 4.2 gives some discussions for the active learning setting, the paper does not prove any formal results for the setting.\n- Some notations can be simplified to make the formulas cleaner; for example in Eq 13, the subscript u for x, y, etc. can be dropped without affecting the meaning of the equation. The same is also true for other equations such as 12, 14, etc.", "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": "axcumpLmIuE", "reviewer": "Reviewer_yzw6", "summary": "1. The paper describes DynamicAL, an algorithm for active learning based on NTK-based analysis of training dynamics\n2. The algorithm is based on the notion that fast training results in better generalization. The authors describe \"alignment\" as a measure of convergence rate and show that this term affects the generalization bounds derived in the NTK regime.\n3. The authors then show that the proxy used in DynamicAL (\"training dynamics\") correlates with alignment and therefore could be used as a proxy\n4. The paper propose a greedy variant of the proposed algorithm and show that it well approximates the non-greedy variant, while being significantly faster\n5. The paper shows that the resulting algorithm outperforms existing baselines on a few models/datasets", "questions": "1. What is the runtime of the algorithm? It appears that calculating equation 15 would scale linearly with |S|, which seems quite undesirable\n\n2. Does the algorithm suffer from clustering due to the greedy approximation? As an example, suppose that every single item in the dataset is duplicated 10 times and the query size is 10. Will the algorithm not pick the exact same image 10 times? (see the distinction between BALD and BatchBALD, for example)\n\n3. Is the experiment in section 4.3 calculating G using pseudo-labels or ground truth labels? It would be interesting to see the effect of changing pseudo-labels to ground-truth labels on the results in section 4.3\n\n4. While section 4.3 shows that G (training dynamics) correlates with A (alignment), it would useful to see how well G correlates to the final generalization performance, as this is true objective of the active learning algorithm.", "limitations": "See the questions and strength/weaknesses section", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Good presentation, well structured\n2. Well motivated, main claims of the papers are well justified from theoretical point of view, and verified empirically (section 4)\n3. Resulting algorithm is simple to implement and could be considered generalizations of existing methods (as mentioned in section 3.3)\n\nWeaknesses:\n1. Derivation and algorithm based heavily on NTK theory, but practical sized networks have been shown to deviate far from this regime (see [1, 2], for example). This paper does not address this issue. At least some discussion of it would be useful\n2. Unclear computational requirements compared to other methods or runtime analysis (this part, while possible to interpret based on the algorithm description, could be stated more explicitly)\n3. Improvements over baselines seem rather marginal (although this is somewhat expected in a somewhat saturated field)\n\n[1] - https://arxiv.org/abs/2007.15801\n[2] - https://arxiv.org/abs/2010.15110", "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": "SzpOhpMbhPa", "reviewer": "Reviewer_7LZg", "summary": "The authors prove that convergence speed of training and generalization are positively correlated. Based on this observation, the authors proposed a novel active learning algorithm (dynamicAL), which maximizes training dynamics. DynamicAL is theoretically motivated and generalizes existing methods such as uncertainty sampling methods and influence function methods.\n", "questions": "Can you compare the proposed method with other baseline methods for rounds > 10?\n\nCan you discuss the tightness of the bound in the relationships between convergence and generalization?\n", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\n\nThe paper examines the training dynamics of Neural Tangent Kernel, which is suitable for theoretical analysis. The authors proved that convergence speed and generalization are positively correlated.\nThe authors proposed a new objective for an active learning algorithm: optimize the speed of training convergence.\n\nQuality:\nThe results are novel and interesting. However, the quality of the bound is not clear. For example, the authors introduce the notion of label alignment and show that label alignment is correlated with convergence and generalization. Based on this correlation, the authors conclude that convergence and generalization are positively correlated. While it is logical, I believe it oversimplifies the dependency between convergence and generalization given that the bound is an approximation and the quality of the bound was not assessed.\nExperimental results can be improved by measuring performance for all rounds (> 10 rounds until the training set is exhausted). Currently, the authors evaluate and compared methods for less than 10 query rounds. It is not clear if the proposed method outperforms the baselines in all rounds.\nThe improvement is rather small (often less than 1%).\n\nClarity:\nIn general, the paper is easy to read. However, its flow and presentation can be improved. For example, the authors first present the method and later present a theoretical analysis of “Train faster → generalize better”. I suggest that some of the theoretical results can be presented together with the method to improve the presentation quality. Other, unnecessary lemmas should be moved to the appendix. Then, the authors can expand the theoretical section and discussion of related work sections.\n\nSignificance:\nThe authors’ idea of optimizing for convergence speed is interesting and of potential significance, as it can be explored by a wider community in other fields. However, the authors should improve the presentation and clarify of the paper, while also updating experimental results.\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": "G_fn61eZFj-", "reviewer": "Reviewer_Sva2", "summary": "In this paper, the authors address the problem of active learning in the setting where the learning model is over-parameterized with respect to the data.  They note that theories of active learning are based upon assumptions that hold for hypothesis classes with lower parameterizations may not hold in the over-parameterized setting, and propose to use newer tools from generalization theory to theoretically ground active learning for deep neural networks.  They propose to use tools for studying the relationship between training dynamics and generalization performance (such as the NTK) as the basis for new deep active learning heuristics to select unlabeled data points in the pooled setting, eschewing traditional methods that select points that maximize either labeled data diversity or model uncertainty.   They demonstrate that selecting data points which maximize the rate at which models train (the rate of descent of the training loss as a function of the number of parameter updates) is positively correlated with a lower generalization bound, thus establishing it as a bona fide heuristic for the acquisition function.  \n", "questions": "Lines 284-285: I would recommend trying this out on datasets with more severe class imbalances.  Each of CIFAR10, SVHN and Caltech 101 are rather well behaved and don’t exhibit any class imbalances, making them odd choices for active learning.  Perhaps this is why there does not seem to be much of a drastic difference in the results of Figure 3?\n\nLine 162: The use of pseudo labeling in this paper connects this work to recent work on self-supervised learning.  I wonder if the authors have considered the implications of what current theories of self-supervised learning can do to inform this work, or what this work could do to transform a self-supervised learning method into a few-shot method that would preform better?\n", "limitations": "Yes, they have.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Lines 49-52: Will definitely have to ensure that TD can be computed or well-estimated quickly, lest this be impractical\n\nLine 100: $K^{i,j}(x,x’)$ is the inner product of the gradient of the $i$-th class probability and the gradient of the $j$-th class probability evaluated at {x} and {x’} respectively.  I think?  It's not totally clear, and having to flip back to the notation section much higher up is not ideal.  \n\nLine 122: Similar criticism here.  This section includes a lot of notation, it would help the reader here to better understand equation (8) to recall that $K^{ij}(X,X)$ is the empirical NTK.\n\nLine 150: This is a common issue in active learning.  This can bias the selection of points, since the point-wise contribution to G(S) is not necessarily additive.  See work by [Farquahr et al 2021](https://arxiv.org/abs/2101.11665) for an example in the case of using uncertainty to acquire labels.  A test to see how vulnerable G(S) is to this phenomenon would be to run selection with $b = 1$, and then with $b$ increasing in various intervals, to see how frequently the single points acquired with $b = 1$ appear in the  set of $b$ points acquired in a single batch selection.\n\nLine 154: I presume that $\\mathcal{K}^{ij}$ is the empirical NTK, but it would help the reader to specify what it represents, as it’s not super clear by the derivations from lines 149 - 155.\n\nLines 176-178: While using an IF derived acquisition function makes some sense (in the sense that high influence points will by identification provoke large magnitude changes in the model parameters), it’s not clear that it’s a better or more valuable way to acquire points.  \n\nLine 194: “of” missing here\n\nLines 217-219: In theorem 1, the factor $\\nu$ will change at $t -> \\infty$, since it depends on the reciprocal of $n^2$.  Is this accounted for in the proof?\n\nLine 260: I would reformulate this sentence here, since evaluating one experiment for two query rounds on one network and dataset does *not* do much to convince the reader that Lemma 2 holds.  I think the authors should broaden the datasets they use to establish the validity across other datasets, especially with different class imbalances.\n\nLine 263: This figure is nice, but it lacks some context.  How good is the correlation between the training dynamics proxy and alignment?  What would help readers understand this better would be a comparison of different acquisition functions and how they correlate with alignment.  This correlation argument would become much stronger.\n\nSection 5: There are two key points missing in the empirical analysis of dynamicAL versus other acquisition functions.  \n\nThe first is an analysis of the degree of overlap between the points selected by dynamicAL and other methods; how many of the same points are chosen, and does the membership of the sets of acquired points converge over time, or do they diverge as successive rounds of acquisition take place?\n\nThe second is that in both figure 3 and 5 we see only the means but not the variances of each set of retraining experiments.  I suspect that there are two components contributing to the performance of each algorithm: first is the selection of the points acquired, as well as the smaller differences in training dynamics for each network due to initialization, batch order in which the data is presented to the models, or even GPU noise.  It would be more convincing to see error bars, so that we can gauge how much of an effect the selection of points has on the accuracy.", "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