Deep Active Learning by Leveraging Training Dynamics
Authors: Haonan Wang
Wei Huang
Hanghang Tong
Andrew J Margenot
Jingrui He
Venue: ICLR 2022 Submitted (2022)
Keywords: deep learning
active learning
neural tangent kernel

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 justiﬁcation, thus suffering from heavy doubts when some of those fail to provide beneﬁts 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 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. Further on, 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 ﬁndings of deep networks and practical impacts in deep active learning applications.

Under review as a conference paper at ICLR 2022
DEEP ACTIVE LEARNING BY LEVERAGING TRAINING DYNAMICS
Anonymous authors Paper under double-blind review
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 theory-driven deep active learning method (dynamicAL) which selects samples to maximize training dynamics. In particular, we prove that 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. Further on, to scale up 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 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.
INTRODUCTION
Training deep learning (DL) models usually requires large amount of high-quality labeled data (Zhang et al., 2017) to optimize a model with a massive number of parameters. The ac- quisition 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 to identify and label the maximally informative samples, so classifier can be trained with minimal labeling effort (Settles, 2009). Under classical statistical learning settings, theories of active learning have been extensively studied from the perspective of VC dimension (Hanneke et al., 2014). As a result, variety of methods have been proposed, such as (i) the version-space-basse approach, which requires maintaining set of models (Cohn et al., 1994; Balcan et al., 2009), and (ii) the clustering- -based approach, which assumes the data within the same cluster have pure labels (Dasgupta & Hsu, 2008).
that
However, the theoretical analyses for these classical settings may not hold for over-parameterizee deep neural networks where the traditional wisdom is ineffective (Zhang et al., 2017). For example, margin- based methods select the labeling examples in the vicinity of the learned decision boundary (Balcan et al., 2007; Balcan & Long, 2013). However, in the over parameterized regime, every labeled example could potentially be near the learned decision boundary (Karzand & Nowak, 2019). As a result, theoretically, such analysis can hardly guide us to design practical active 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 a few application scenarios (Kirsch et al., 2019; Ash et al., 2020).
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 (Jacot et al., 2018; Arora et al., 2019b; Lee et al., 2019). It is shown that the training dynamics of deep neural networks using gradient descent can be characterized by the Neural Tangent Kernel (NTK) of infinite (Jacot et al., 2018) finite (Hanin & Nica, 2020) width networks. This is further leveraged

---

Under review as a conference paper at ICLR 2022
to characterize the generalization of over weerparamettriiee networks through Rademacher complexity analysis (Arora et al., 2019b; Cao & Gu, 2019). 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 training data for the werrparamettrrzzd deep neural networks. Based on the NTK framework (Jacot et al., 2018; Arora et al., 2019b), we theoretically show that if a deep neural network converges faster ("Train Faster"), then it tends have a better generalization performance (" ("Generalize Better"), ), which matches with the existing observations (Hardt et al., 20;6; Liu et al., 2017; Lyle et al., 2020; Ru al., 2020; Xu et al., 2021). 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 seveeticall-mmee motiivated deep active learning method, dynamicAL, which will query labels for a subset of unlabeled samples that maximally increases the training dynamies. In order to compute the training dynamics by merely using the unlabeled samples, we leverage two relaxations Eseudo-labelingg and Subset Approximation to solve this non-trivial subset selection problem. Our relaxed approaches are capable of effectively estimating the training dynamics well efficiently solving the subset selection problem by reducing the complexity from O(N") to O(b).
In theory, coin new term Aligmment 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 lower generalization bound. Furthermore, we extend the previous analysis to an active learning setting, where the i.i.d. assumption may not hold with the help of the maximum mean discrepancy (Borgwardt et al., 2006). Finally, we show that alignment is positively correlated with our active learning goal, training dynamics, which implies that maximizing training dynamics will lead better generalization performance.
Regarding experiments, we have empirically verified our theory by conducting extensive exper- iments on three datasets, CIFARIO (Krizhevsky et al., 2009). SVHN (Netzer al., 2011), and Caltech101 (Fei-Fei et al., 2004) using three types of network structure: vanilla CNN, ResNet (He et al., 2016), and VGG (Simonyan & Zisserman, 2015). We first show that result of the subset selection problem delivered by the subset approximation is close to the global optimum solution. Furthermore, under active learning setting, our method not only outperforms the other baselines but also scales well on large deep learning models.
The main contributions of our paper can be summarized as follows:
We propose theory-drived deep active learning method, dynamicAL, inspired by the results of "train faster, generalize better". To this end, we introduce the Training Dynamics, as a proxy to describe the training process and embody the inspiration.
We demonstrate that the convergence speed of training and the generalization performance is (positively) strongly correlated under the ultra-wide condition; also show that maximizing the training dynamics will lead to 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
2.1 NOTATIONS
We use the random variable E X to represent input data feature and y y label where K is the number of classes and [K] := (1, K}. We are given a data source D with unknown distribution p(æ, y). We further denote the concatenation of x as X [21. 22, ..., x T and that of y Y = 1/ V2...., yarl TT. We consider deep learning classifier ha (x) = argmax (x; 0)) x + parameterized by 0 E RP, where (.)) is the softmax function and f is a neural network. Let @ be the
Z2,...,
Kronecker Product and Xx E R-K xK be an identity matrix.
2.2
ACTIVE LEARNING
The goal of active learning is to improve the learning efficiency of a model with a limited labeling budget. In this work, consider the pooe-b AL setup, where finite data set S 9))
2

---

Under review as a conference paper at ICLR 2022
with M points are i.i.d. sampled from the p(z, y) as the (initial) labeled set. The AL model receives an unlabeled data set U sampled from p(z) and request labels according to (yy[z) for any 2 E U in each query round. There are R rounds in total and for each round, query set Q consisting of b unlabeled samples can be queried. The total budget size = b x R.
2.3 NEURAL TANGENT KERNEL
The Neural Tangent Kernel (Jacot al., 2018) has been widely applied analyze the dynamics of neural networks. If the neural network is sufficiently wide, properly initialized, and trained by gradient descent with infinitesimal step size (a.k.a. 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 i, the dynamics of the neural network has a closed-form expression:
df(2'; K. (1(200)) ))
(1)
where (tt denotes the parameter of the neural network at iteration t. (,, E XX
is called the empirical NTK and K2, x') = Vaf 0(t)) T (z'; 0()),, for two samples r, E X' and i, E [K]. The time-varian kernel (C(:,-) is equivalent to the (imeeinvariiat) NTK
with high probability, that is, if the neural network is sufficiently wide and properly initialized, then:
X) = O x') @ Ix
The final learned neural network at iteration f, is equivalent to the kernel regression solution with respect to the NTK (Lee et al., 2019). For any input x and training data {X, Y) we have,
fax; {(t) (ax X) (xx, (I - -,((XX)))
(3)
where y the learning rate, O (r, X) is the NTK matrix between input x and all samples in training data X.
3 METHOD
In section 3. I, we introduce the notion of training dynamics which can be used to describe the training process. Then, in section 3.2, based the training dynamics, we proposed dynamicAL. In section 3.3, we discuss the connection between dynamicAL and existing deep active learning methods.
3.1 TRAINING DYNAMICS
In this section, introduce the notion of training dynamics. The cross cross-entropy loss over labeled set defined as:
L(S)= Σ (((x.0)).) = Σ
Σ
vi log (f(=;)))
(4)
(Ai-n)ee
(#L-)))S [E[K]
where o'(((x; 0)) Σ, (x:0)) We first analyze the dynamics of the training loss, with respect to iteration f, on one labeled sample (derivation is in Appendix A.
oxp(1' (x:00)
al(f(z;;) 0).
(5)
Øt
For neural networks trained by gradient descent, if learning rate is small, then V,0 p 0, = 8 ((ruunes {(((a))))))
-1
Taking the partial derivative of the training loss with respect to the parameters, we have (the derivation of the following equation be found in Appendix A.2):
OE( 0).v)
Σ (o' - -²") (f;(0;0) SE[K]
(6)
00
a0
Therefore, can further get the following result for the dynamics of training loss
fx( 0). = (=((((=;))))- - +' E Vol'(z; (v) (F(()))))))))))))))))))) - v/-)
01
3

---

Under review as a conference paper at ICLR 2022
Furthermore, we define d' (X,Y) = of(((: - Y and Y is the label vector of all samples for i-th class. Then, the training dynamics (dynamics of training loss) over training set is denoted by G(S) e R:
1 G(S)
(xX))
Ōt
(8)
(ELSS))
3.2 ACTIVE LEARNING BY ACTIVATING TRAINING DYNAMICS
Before we present dynamicAL, we state the Proposition 1, which serves as theoretical guidance for dynamicAL and will be proved in Section 4. Proposition 1. For deep neural networks, converge faster leads to a lower worst-case generalization error
Motivated by the connection between convergence speed and generalization performance, we propose the general-purposs 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), L..,
Q = agg
Q), a.t. [Q]=
where Q is the corresponding data set for Q with ground-trute labels. Notice that when applying the above objective in practice, we are facing two major challenges. First, G(S U 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 to make this maximization problem to be solved with constant time complexity.
Pseudo Labeling. To estimate the training dynamics, we use the predicted label G. for sample T. in the unlabeled data set U to compute G. Note, the effectiveness of this adaptation has been demonstrated the recent gradient-bant -based methods (Ash et al., 2020; Mu et al., 2020), which compute the gradient if the model's ' current prediction the example is the true label. Therefore, the maximization problem in Equation (9) is changed to,
Q argmax G(SU Q)
(10)
where Q is the corresponding data set for Q with peseudo labels, Yo.
Subset Approximation. The subset selection problem of Equation (10) still requires enumerating all possible subsets of U with size b, which is O(z"). We simplify the selection problem to the following problem without causing any change on the result.
argmax G @) = argmaxoou A(Q)S)
(11)
where =
- 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).
qgu
Σ
A([(Fu. s.t. |Q] =
(12)
(au SE)
To further show the approximated result is reasonably good, we decompose the change of training dynamics as (derivation in Appendix A.4),
A( = Σ All(E.. H.H
Σ
('a, B.) 1C (In, xy. (ww) (13)
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,
H([[S)- = Evenswee Aff(xu) (I ((S)
(14)
A(
4

---

Under review as a conference paper at ICLR 2022
We empirically measure the expectation of the Approximation Ratio on three data sets with three different neural networks. As shown in Figure 4, the expectation, TEq- R(Q[S) R 1 when the model is converged. Therefore, the approximated result delivered by greedy algorithm is close to the global optimal solution of the original maximization problem, Equation (10), especially when the model is converged.
Based on the above two approximations, we present the proposed method dynamicAL Algorithm 1. As described below, the algorithm starts by training a neural network f(:;0) on initial labeled set S until converge. Then, for every unlabeled sample Tus we compute pseudo label yn, and the change of training dynamics A ((((Tu: Du)) (S). After that, dynamicAL, will query labels for top-b samples causing maximal change on training dynamics. Then train the neural network (without re-initialization) on the extended labeled set, and repeat the process.
Algorithm Deep Active Learning by Leveraging Training Dynamics
Input: Neural network f(; unlabeled sample set U, initial labeled set S, number of query round R. query batch size b.
for r = 1 to do
Train f(:
() on S with cross-entropy loss until convergence.
for Iu E do
Compute its pseudo label j.. argmax (xr (uuu:)) 0).
Compute A (((Fu, {S)
end for
Select b query samples Q with the highest A values, and request their labels from the oracle. Update the labeled data set SUQ.
end for
return Final model f-:
3.3 RELATION TO EXISTING METHODS
Although existing deep active learning methods are usually designed based on heuristic criteria, some of them have empirically shown their effectiveness (Ash ct al., 2020; Liu et al., 2021; Huang et al., method dynamicAL has connec-
2016). We surprisingly found that our theoretically-motiive tions with those existing methods from the perspective of active learning criterion. The proposed active learning criterion in Equation (12) can be explicitly written (derivation in Appendix A.5):
Aff(zu, {.) = (),: +2
Σ (F.2)ES
(). Vellf(z;)).))
(15)
The first term of right-hand side can be interpreted as the square of gradient length (2-norm) which reflects the uncertainty of the model on the example and has been wildly used as an active learning criterion in some existing works (Huang al., 2016; Ash et al., 2020; Shukla, 2021). The second term can be regarded as the influence function (Koh & Liang, 2017) with identity hessian matrix. And recently, Liu et al. (2021) has empirically shown that the effectiveness of using it as the active learning criterion. We hope our theoretical analysis can 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 altra-wide condition (Jacot et al., 2018; Arora al., 2019b). We define measure named aligument to quantify the convergence rate and further show the connection with generalization bound. The analysis provides a theoretical guarantee for the phenomenon of "Train Faster, Generalization Better" well as our active learning method dynamicAL with rigorous treatment. Finally, we show that the our active learning proxy, training dynamics, is correlated with alignment, which indicates that increasing the training dynamics leads larger convergence rate and better generalization performance. We leave all proofs of theorems and details of verification experiments in Appendix B and D respectively.
5

---

Under review as a conference paper at ICLR 2022
4.1 TRAIN FASTER PROVABLY GENERALIZE BETTER
Given an wldre-wide neural network, the gradient descent can achieve a near-zero training error (Jacot et al,, 2018; Arora et al., 2019a) and its generalization ability in unseen data can be bounded (Arora et al., 2019b). It is shown that both convergence and generalization have a connection with the NTK (Arora et al., 2019b). However, the question what is the relation between convergence rate and generalization bound has not been answered. We formally give a solution by introducing the concept of alignment, which is defined as follows,
Definition (Alignment). Given a data set 5 = between X and Y projected in the NTK space. In particular, the alignment can be computed by A(X,Y) (XX Ex E yky
{X,Y), J. the alignment is a measure of correlation
In the following, we will demonstrate why train faster generalizes better through alignment. In particular, the relation of convergence rate and generalization bound with alignment are analyzed. The convergence rate of gradient descent for ultra-wide networks is presented in following lemma, Lemma 1 (Convergence Analysis with NTK, Theorem 4.1 of (Arora et al., 2019b)), Suppose A Amin (0) > 0 for all subsets of data samples. For d E (0, 1), if = M x and
? 0 22 ). Then with probability at least 8, the network can achieve near-zero training error,
n I - 1(x;0()) = (1- SALAAAAEE
(16)
where n denotes the number of training samples, mn the width of hidden layers. The NTK θ = AVAV with A = {> diagonal matrix of eigenvalues and V = [0: a unitary matrix.
In this lemma, we take mean square error (MSE) loss as 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 (Lee et al., 2019)). From the lemma, we find convergence rate is governed by the dominant term (16) as (X, = - E - (") y*)z, which correlated with the alignment:
Theorem (Relationship between convergence rate and aligmment). Under the same assumptions as in Lemma 1. The convergence rule described by & satisfies,
TrYY D1 Y) S (X, S ()-
(17)
Remark 1. In the above theorem, we demonstrate that the alignment can measure the convergence rate. Especially, find that both the upper bound and the lower bound of error Ex(X, Y) are inversely proportional to 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 reasonable generalization bound.
Lemma 2 (Generalization bound with NTK, Theorem 5.1 of (Arora et al., 2019b)). Suppose data S = {(x,, |= are i.i.d. samples from a non-degenerate distribution p(x,8) and m 2 poly(n, An 8 Consider any loss function e R R - [0, 1] that is 1 L-Lipschitz. Then with probability at least 1 - 8 over the random initialization, the network trained by gradient descent for 2 92( nāo log ") iterations has population risk Lp = E(z.a)=p(z.v ( [f(f 0), y) that is bounded
as follows:
2T θ (X,X)) + (V log Ago c S
(18)
7
72
In this lemma, we show that the dominant term in the generalization upper bound is B(X, = 2T-Y1 In the following theorem, we further prove that this bound is inversely proportional
the alignment A(X, Y).
Theorem (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) = 2Try e then it can be bounded with the alignment as follows,
Tr2 Y] n 82 (X,)) Amaz T A(X,Y) 2
(19)
Amin A(X,Y) Y)

---

Under review as a conference paper at ICLR 2022
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 "TRAIN FASTER, GENERALIZE BETTER" FOR ACTIVE LEARNING
In the NTK framework (Arora al., 2019b), the empirical average requires data in S is i.i.d. samples, Lemma 2. However, this assumption 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 learning policy. To extend the previous analysis principle to active learning, we follow (Wang & Ye, 2015) reformulate the Lemma 2 as:
C, s (Cop Ca)+
2T e '(X,X)) +
n log
Auá
(20)
where C. = ())(1)))()).))) (x; 0), y)1, qxx y) denotes the 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.
L, - Cu ((rr))-p(e..p [[(f (x; f): v)] - ((e.)))-((.))) [x;(()))) 0).
(21)
Though in active learning the data distribution for the labeled samples may be different from the original distribution. However, they share the same conditional probability p(y|z). We define
g(x) S, E( (); v) Then we have,
gla)p(z)de / Saapptdddd-sssaattte {
Cp c, =
(22)
To measure the distance between two distribution, we employ the Maximum Mean Discrepancy (MMD) with neural tangent kernel (Jia et al., 2021) (derivation in Appendix B.3).
C Lg < MMD(S S, He) + (V( C1m(110)
(23)
T2
Slightly overloading the notation, we denote the initial la- beled set as Sa, He as the associated reproducing kernel Hilbert space for the NTK O, and Vz, S, (zzzz') x') < C. Note, MMD(Sp, S, He) as the empirical measure for MMD(p(2), q(x), Ho). We empirically compute MMD and the dominant term of the generalization upper bound B under the active learning setting with our method dynamicAL. As shown in Figure I, on CIFAR 10 with a CNN target model (three con- volutional layers with global average pooling), the initial la- beled set size |.S] = 500, query round R = and budget size 6 e (250, 500, 1000}. we observe that, under different active learning setting, the MMD always much smaller than the B. Therefore, the lemma 2 still holds for the target model with dynamicAL. The result for 2 is in Appendix E.4. The computation detail of MMD and NTK is in Appendix D.1.
70-
A (1-0)
N0M0 (1ghht)
0.35
60-
2009
0.30
50
0.2
0-2022
0.20
0.15
0.10
250
b-500
b-1000
0.05
Figure 1: Empirical Generaliza- tion Bound and MMD
4.3 ALIGNMENT AND TRAINING DYNAMICS ACTIVE LEARNING SETTING
In this section, we show the relationship between the align- ment and the training dynamics. To be consistent with the
12000
previous theoretical analysis (Theorem 1 and 2), we use the
M
AlXI|X Milaa
11500
training dynamics with mean square error under the ultra-
11000
width condition, which can be expressed as GMSE(S)
Tr [(f(X; - Y)T TY)Te T (XXXX)(((XX)) - Y)]. Due to the limited space, we leave the derivation in Appendix A.3. To further quan- titatively evaluate the correlation between GMSE(S U Q) and A(XII_Xq Y (|))),
10000
0.57
). we utilize the Kendall 7 coefficient (Kendall, 1938) to empirically measure their relation. As shown in Figure 2, for CNN on CIFARI0 with active learning setting, where S 500
400 600
500
1000 1200 3000 1500 1030
G(S u Q)
Figure 2: Alignment and Train- ing Dynamics.
and Q = 250, there is a strong agreement between GasE and A[X] Xq. Y)),, which further indicates that increasing the training dynamics will lead to a faster convergence and better generalization performance. More details about this verification experiment are in Appendix D.2.
7

---

Under review as a conference paper at ICLR 2022
5 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.I.
Data set and Target Model. We evaluate all the methods on three benchmark data sets, namely, CIFARIO (Krizhevsky et al., 2009), SVHN (Netzer et al., 201 1), and Caltech101 (Fei-Feii et al., 2004). We use the accuracy as the evaluation metric and report the mean value of runs. We consider three neural network architectures: vanilla CNN, ResNet18 (He et al., 2016), and VGG11 (Simonyan & Zis- serman, 2015). For each model, we keep the hyper-parameters used their official implementations. More information about the implementation is in Appendix C.I.
Active Learning Protocol. We evaluate all those active learning methods in batch-mode setup with an initial set size M 500 for all those three data sets, batch size b varying from {250, 500, 1000]. And, after each query, no re-initialization used.
5.2 RESULTS AND ANALYSIS
The main experimental results have been provided as plots due the limited space. We also provide tables in which we report the mean and standard deviation for each plot in Appendix E.3.
Overall Results. The average test accuracy at each query round shown in Figure Our method dynamicAL can consistently outperform other methods for all query rounds. This suggests that dynamicAL. is a good choice regardless of the labeling budget. Besides, we notice dynamicAL can work on data sets with a large class number, such Caltech101. However, the baseline method, BADGE, cannot be scaled up to those data sets, because the required memory is linear with the number of classes. Note, dynamicAL depends the quality of pseudo labeling, thus proper initial labeled set is important. This figure shows that dynamicAL is able to work well with a relatively small initial labeled set (M 500). Due the limited space, only show the result under three different setting in Figure 3. More evaluation results are in Appendix E.2 and Appendix E.5.
Query
Query
Test
Corf ALEL
Randor
Con ALD.
Text
Harg
Mag
Marg
Auli
Brines
Briney
Syropy
25
Queryy Round
Query Round
# Quarry Quuery Round
Figure 3: Active learning test accuracy versus the number of query round for a range of conditions.
Effeet of Query Size and Query Round. Given the total label budget B, the increasing of query size always leads to the decreasing of query round. We study the influence of different query size and query round on dynamicAL from two perspectives. First, we study the expected approximation ratio with different query batch size on different data sets. As shown 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, 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 is allowed.
Figure 4, under different
Table 1: Accuracy of dynamicAL. with different query batch size b.
Method
CIFARIO CNN
CIFARIO + Resnet SVHN + VGG
Caltech101 + Resnet
10, b 100
36.84
40.92
76.34
37.06
R = 4, 250
36.72
40.78
75.26
36.48
R = 2, b 500
36.71
40.46
74.10
35.91
R = 1,b 1000
36.67
40.09
70.04
33.82
8

---

Under review as a conference paper at ICLR 2022
CI ResNet
SVHN, VGG
Size b-
Batthh
Batch Size 5-500
Datch Size b-500
Batch Size b=1000
Batch Size b- 1000
E
Eo R--RRR
20
30
40
10
20
Epoch
Epoch
Figure 4: The Expectation of the Approximation Ratio with different query batch size b.
Comparison with Different Variants. The active learning criterion of dynamicAL can be written as Ei [[x;; Ow), lIl + VVL([ (x.; 0). (o)( (), w) We empirically show the performance for y (0, 2, оo) in Figure 5. As the prediction of our analysis (Equation 15), for 2, the model achieves the best performance. The result confirms the importance of theoretical analysis for the design of deep active learning methods.
CIFARLO, CNN, Batch Size: 500
SVMN, VGG, Batch Size: 500
CIFAR1O, Restitt Batch Size: 500
02
Teat Accuratyy 67
Testt Accurtyy (94)
15
32-
Round
Round
Round
Figure 5: Test Accuracy of different variants.
6 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) (Jacot et al., 2018). Since then, NTK has become a powerful theoretical tool to analyze the behavior of deep learning model (CNN, GNN, RNN) from its output dynamics (Arora et al., 2019a; Du et al., 2019; Alemohammad et al., 2020) and to characterize the convergence and generalization error (Arora et al., 2019b). Besides, (Hanin & Nica, 2020) studies the finite-width NTK, aiming at making the NTK more practical.
Active Learning: Active learning aims at interactively query labels for unlabeled data points to maximize model performances (Settles, 2009). Among others, there are two popular strategies for active learning, i.e., diversity sampling (Du et al., 2015; Volpi et al., 2018; Zhdanov, 2019), uncertainty sampling (Roy & McCallum, 2001; Zhu & Ma, 2012; Yang & Loog, 2016; Ash et al., 2020; Yoo & Kweon, 2019; Settles et al., 2007: Liu et al., 2021). Recently, there are several papers proposed to used gradient to measure uncertainty (Settles et al., 2007; Ash et al., 2020; Liu et al., 2021). 1). However, those methods need to compute gradient for each class, they can hardly be applied on data sets with large class number.
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 the 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, work show that dynamicAL not only consistently outperforms strong baselines across various setting, but also scales well on large deep learning models. We provide the discussion the limitation of future work in Appendix F.

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY
To ensure the results and conclusions our paper are reproducible, we make the following efforts:
Empirically, provide the URL for the code, and instructions needed to reproduce the main experimental results. And we specify all the training and implementation details in Section 5 and Appendix C.I. Besides, we independently run experiments five times and report the mean and standard deviation in Appendix E.3.
Theoretically, we state the full of assumptions and include complete proofs of our theoretical results in Section 4 and Appendix B.
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
Sina Alemohammad, Zichao Wang, Randall Balestriero, and Richard Baraniuk. The recurrent neural tangent kernel. In International Conference on Learning Representations, 2020.
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, pp. 8139-8 -1199,8188, 2019a.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, volume 97, pp. 322-332, 2019b.
Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In International Conference Learning Representations, 2020.
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, pp. 288-316, 2013.
Maria-Florina Balcan, Andrei Z. Broder, and Tong Zhang. Margin based active learning. In Conference on Learning Theory, volume 4539, pp. 35-50, 2007.
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-88) 89, 2009.
Karsten M Borgwardt, Arthur Gretton, Malte Rasch, Hans-Peter Kriegel, Bernhard Schölkopf, and Alex J Smola. Integrating structured biological data by kernel maximum mean discrepancy. Bioinformatics, 22 22(14):e49-e) 2006.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 1510886-10846, 2019.
Yao-Chun Chan, Mingchen Li, and Samet Oymak. On the marginal benefit of active learning: Does self-supervision eat its cake? In ICASSP 202 1-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3455-3459, IEEE, 2021.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 15(2):201-221, 1994.
Felix Dangel, Frederik Kunstner, and Philipp Hennig. BackPACK: Packing more into backprop. In International Conference Learning Representations, 2020.
Sanjoy Dasgupta and Daniel Hsu. Hierarchical sampling for active learning. International conference on Machine learning, pp. 208-215 215. 2008.
Bo Du, Zengmao Wang, Lefei Zhang, Liangpei Zhang, Wei Liu, Jialie Shen, and Dacheng Tao. Exploring representativennss and informativeness for active learning. IEEE transactions on cybernetics, 47(1):14-26, 2015.
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 arXiv: 13192, 2019,
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. pp. 178-178. IEEE, 2004.
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-77.. 2012.
Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel. In International Conference Learning Representations, 2020.
11

---

Under review as a conference paper at ICLR 2022
Steve Hanneke et al. Theory of disagreement-basee based active learning, Foundations and Trends@ in Machine Learning, 7(2-3):131-23 13--999,, 2014.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, volume 48, pp. 1225-1234, 2016.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Wei-Ning Hsu and Hsuan-Tien Lin. Active learning by learning, In AAAI Conference Artificial Intelligence, pp. (659-26655, 2015.
Jiaji Huang, Rewon Child, Vinay Rao, Hairong Liu, Sanjeev Satheesh, and Adam Coates. Active learning for speech recognition: the power gradients. arXiv preprint arXiv:1612.03226, 2016.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernl:: convergence and generalization neural networks. In Neural Information Processing Systems, pp. 8580-8589, 2018.
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, pp. 4893-4903, 2021.
Mina Karzand and Robert D. Nowak. Active learning in the overparameterized and interpolating regime. CoRR, abs/1905.12782 2019.
Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81-9,, 1938.
Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In Neural Information Processing Systems, pp. 7024-7035. 2019.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference Machine Learning, volume 70, pp. 1885-1894, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Jaehoon 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, pp. 8570-8581, 2019.
Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, volume 70, pp. 2159-2167, 2017.
Zhuoming Liu, Hao Ding, Huaping Zhong, Weijia Li, Jifeng Dai, and Conghui He. Influence selection for active learning. arXiv preprint 208.v:2008.093: 2021.
Clare Lyle, Lisa Schut, Robin Ru, Yarin Gal, and Mark der Wilk. A bayesian perspective on training speed and model selection. In Neural Information Processing Systems, 2020.
Sudhanshu Mittal, Maxim Tatarchenko, Özgün Çięek, and Thomas Brox. Parting with illusions about deep active learning. arXiv preprint 192.0119122053,,,,2000
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
Fangzhou Mu, Yingyu Liang, and Yin Li. Gradients as features for deep representation learning. In International Conference Learning Representations, 2020.
Yuval Netzer, Tao Wang, Adam Coates, Ro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning, 2011.
12

---

Under review as a conference paper at ICLR 2022
Mamshad Nayeem Rizve, Kevin Duarte, Yogesh S Rawat, and Mubarak Shah. In defense of pseudo- labeling: An uncertainty-awann aware pseudo-label selection framework for cmmi-superiised learning. arXiv preprint arXiv:2101.06322) 2021.
Dan Roth and Kevin Small. Margin-basede 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, pp. 413-424, 2006.
Nicholas Roy and Andrew McCallum. Toward optimal active learning through sampling estimation of error reduction. In International Conference on Machine Learning, pp. 441-448, 2001.
Binxin Ru, Clare Lyle, Lisa Schut, Mark van der Wilk, and Yarin Gal. Revisiting the train loss: an efficient performance estimator for neural architecture search. arXiv preprint 4rXiv:2006.04492, 2020.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: core-set approach. In International Conference on Learning Representations, 2018.
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin 2009.
Burr Settles, Mark Craven, and Soumya Ray. Multiple-instance active learning. In Neural Information Processing Systems, pp. 1289-1296, 2007.
Megh Shukla. Egl++: Extending expected gradient length to active learning for human pose estimation. arXiv preprint arXiv:2104.094993 2021.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel. Fixmatch: Simplifying emii-supervised learning with consistency and confidence. arXiv preprint arXiv:200/.0768) 2020.
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, pp. 3339,5349, 2018.
Dan Wang and Yi Shang. A new active labeling method for deep learning. In International Joint Conference on Neural Networks, pp. 112-119, 2014.
Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode active learning. ACM Transactions on Knowledge Discovery from Duta, 9-3):1223, 2015.
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, pp. 11592-1 1602, 2021.
Yazhou Yang and Marco Loog. Active learning using uncertainty information. In International Conference on Pattern Recognition, pp. 16646-661,, 2016.
Donggeun Yoo and In So Kweon. Learning loss for active learning. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 93-102, 2019.
Weiwei Yuan, Yongkoo Han, Donghai Guan, Sungyoung Lee, and Young-Koo Lee. Initial training data selection for active learning. In Proceedings of the 5th International Conference on Ubiquitous Information Management and Communication, pp. 1-7, 2011.
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:2 106.07880. 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
13

---

Under review as a conference paper at ICLR 2022
Fedor Zhdanov. Diverse mini mini-batch active learning. arXiv preprint 10X.v:1901.0594... 2019.
Jingbo Zhu and Matthew Ma. iicertaintt-bassed active learning with instability estimation for text classification, ACM Transactions on Speech and Language Processing (TSLP), 8(4):1-21, 2012.
14

---

Under review as a conference paper at ICLR 2022
A
APPENDIX: DERIVATION OF OBJECTIVES
For the notational convenience, we use f(x) to represent f(z; the Appendix.
A.1 TRAINING DYNAMICS FOR
Loss
The partial derivative for softmax function can be defined with the following,
(f(()()) - - i (z) (- i
(24)
Then, have:
@E(f(x).
Glog f(æ) do (f(x))
V
0t
(f((((z)
Öt
1 (f(x))
(x)
-
=-
o' x))
(z)
Öt
(25)
(z)
Σ v Σ (1/i = و or (f(x))
0t
Σ ((
A.2 DERIVATION FOR CROSS-ENTROPE LOSS
@((f(z),v)
de 0f(z)
(o'(((z)) 0f(z)
- o'((z)) f(z)
00 Of(x) 00
00
-- v' o'f(x)) (f(z)) Σ (1-i=- 1 σ (f(z)) (x)
(26)
00
E -1)( -
00
A.3 APPENDIX: TRAINING DYNAMICS FOR MEAN SQUARED ERROR
For the labeled data S, define the Mean Squared Error(MSE)
LMSE(S) Σ (MSE(f()).)) =- Σ
Σ
1
(x)
2
(5.8)SS
(a.y)eS
Then the training loss dynamics for each sample can define as:
(lMsE((()).))
-w-r(a)
Øt
Because neural networks are optimized by gradient descent, thus:
aE(s(x).v)
Σ [) 05
v 0.t1 0:
00
(E.
(x.D)ES
Therefore, the training dynamics of MSE loss can be expressed as:
GMSE(S) 1 10Em (MSE(f(z).)) (S(X) -TXX))))XXXXXX
7 Ø1
15

---

Under review as a conference paper at ICLR 2022
A.4 APPENDIX: DECOMPOSITION OF THE CHANGE OF TRAINING DYNAMICS
According to the definition of training dynamics ( (Equation (8) ), we have,
C(S)= Σ
(d'(((nx))) -i)
Σ
Vol'(m; V (1 m/))
U(SUQ) Σ Σ -))
Σ (a (#'s)))SUQ
Vof 0) Vof (o v²)
1. (R.V)ESUQ
The change training dynamics, = - - can be further simplified as:
= - G(S)
= Σ (d'(I(zu;))) - V.)
Σ
0) (o (00 vi))
iJ (.
Σ
Σ
(d'(f(zu:0) - Vof T
Vo (m. (f F.)
1. (su JEQ
Σ
(o'(f(zu:)) - Th.)
Σ
Vel' 0) Vol (z 0) (o" (xw: ()) R..
Σ
All(2u Ho) {+))
Σ
d' (ens T (x a of (wt Fhr)
(Ru.Sr))it Th JE
A.5 APPENDIX: SIMPLIFICATION OF THE CHANGE OF TRAINING DYNAMICS
Al((Tr, [o)][ss = E (d'(f(zu;)) f..)
Σ
Vo Vof' (o (o vi)
1d (R
Σ Σ (o'(f(zu;))
Vof (zu: T ()) (f(xx: [.)
The derivative of loss with respect to model parameters can be written as:
Ecawes (f((x; 0).9)
Σ
Σ
-o)
00
(r.)) kE
Therefore, the change of training dynamics caused by [(r Du)} can be written as:
A(f(zu, (.HS) - [Vol(f(r. +2 Σ
Vollf(r.))) Do) (oo(f(())))))
(x.N)eS
B APPENDIX: PROOFS FOR THEORETICAL ANALYSIS
B. PROOFS FOR THEBREM
Lemma (Convergence Analysis with NTK, Theorem 4.1 of Arora et al. (2019b)). Suppose Xo
Amin ( for all subsets of data samples. For 8 (0, 1), if 2( xgo+2 and n 0 dy Then with probability at least 1 8, the network can achieve near-zero training error.
n²
K ΣΣ
|| - A(x;0(0))
(27)
where n denotes the number of training samples, m the width of hidden layers. The NTK N AVAV with A {x))_ diagonal matrix of eigenvalues and V (7, (= unitary matrix.
16

---

Under review as a conference paper at ICLR 2022
). then with probability at least - over the random initialization, we have, || (((x;((t)) =
x Proof. According to Arora et al. (2019b), if m 2( n² and learning ratio 1) ((22)
(t, y + We decompose the NTK using O V AV with A {>r diagonal matrix of eigenvalues and V = {w: a unitary matrix. At each training step in active learning, the labeled samples will be updated by = S S.Q. We can apply the convergence result in each of this step and achieve near zero error.
V K Ei=
Theorem 1 (Relationship between convergence rate and alignment). Under the same assumptions as in Lemma The convergence rate described by & satisfies,
Tr(YTy] - 20nA(X, S (X & TH -
(28)
Proof. We first prove the inequality on the right hand side. is easy to see that (1-1),) - (1 (1-1)a)) for each X; and > 1, based on the fact that Vλ, 0 S 1 n7 S 1. Then we can obtain,
K Σ (1
K n (1
(XX, =
A=1
k=1
TT-YT(TT ,oyr = V -
Then we use Bernoulli's inequality to prove the inequality on the left hand side. Bernoulli's inequality
states that, (1 + x) 2 2 + ræ, for every integer r 2 0 and every real number 2 -1. It is easy to
check that (-m)a) 2 --, 1, AY2 Therefore.
(1, YR)22 a
(X,YY)=
TT 20/ - TT|YTT]] 21A((X,Y)
B.2 PROOF FOR THEOREM? 2
Lemma 2 (Generalization bound with NTK, Theorem 5.1 of Arora et al. (2019b)). Suppose data S = ((T,, {(1,, ) are i.i.d. samples from a non-degenerate distribution p(r, y), and m 2 poly(n, An 1) Consider any loss function e R x R- + [0. 1] that is L-Lipschitz, Then with probability at least 1 - 8 over the random initialization, the network trained by gradient descent for 2 (2( ndo log ") iterations has population risk Lp E(aws ((( v) that is bounded
as follows:
2Tr O (X,X) + O (V log Ago
Cpp S
(29)
72
Proof. We first show that the generalization bound regrading our method ultra-wide networks. The distance between weights of trained networks and their initialization values can be bounded as, [w, (1) (0)l 0 )) We then give bound on the |[W(() W())]le, where
afit) aw(!)* then the update function W = {W1, ...... is the set of all parameters. We definite Z
is given by W(t + 1) = (t) - (2 (t) - -Y). Summing over all the time step f = 0, I.... we can obtain that W (xx) - (0) = Σ 7 n)0)y = Ze ly. Thus the distance can be measured by [[ - = θ --y
Then the key step is to apply Rademacher complexity. Given R with probability at least 8, simultaneouslly for every B > 0, the function class FB,R = {f ([w,(() w. (0)l < R (vr E (oo) - (1 < B) has empirical Rademacher complexity bounded as,
(FB.BR = E E
sup Σ cff()))
B
log /1/4) + 22R² mm+ R 2 (1+(
JEFB,R i=1
22n
m
17

---

Under review as a conference paper at ICLR 2022
where B = VIILY T (X,,)), and R vm
Finally, Rademacher complexity directly gives an upper bound on generalization error (Mohri et al.,
2018), sup)er(C((f) Ls(f) I 2Rs + 3ev log(2/5) where (s( S Vn' Based on this, we apply a union bound over finite set of different i's. Then with probability least 6/3
2n
log xga ) Vi E
over the sample S, we have Su,,EFR.e, (Gp(f) - Ls(f)) S 2Rs(FB,.n) O(V
(1. ((, Taking a union bound, we know that with probability at least
2 over
the sample S, we have, fr E Fny, for some i", Rg(Fn; FF RR) S
Trly (XXX)
and
2n
supsrEFo; (C/(TT) [s(sT)) S 2Rs O(V n
These together imply.
" log Xoá
2 2Tr θ XX, +
+
log And
fo(fi Vn + 2Rg (B; + O(V
n
72
n1
More proof details can be found in Arora et al. (2019b).
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) 2 Txly then it can be bounded with the alignment as follows,
Y
12
TY TL Bx, S Amar Ty A(XYY) 2
(30)
Amén A(X,Y)
Proof. We first expand the following expression:
K マタ (',XX
K ΣΣ
n
A
(v yays
=
2
k=1
k=
Then we use this expansion to prove the inequality on the left hand side,
K
K
K
K
ykyz
Σ 7
(0
yk(z))
A;
k=
1=1
k=
k==1
1=1
K
y
Σ
y
V
Σ yk vTVV)
= Ty
The second line is due to quadratic mean is greater equal to geometric mean. Finally, we prove the inequality on the right hand side,
n
n
1 (w]
(o) ybk
Ac
2k
No
k=
K
K
K E v (2
K
Amax
Σ (u x
Σ 1=1
(w: T yb/)2))
Amarx
T
VTVA)
Aminn
Amin
Rm I R
km
km
Amaa
T yy
Amin
18

---

Under review as a conference paper at ICLR 2022
B.3 DERIVATION FOR MAXIMUM MEAN DISCREPANCY
The difference between truth risk over p(x) and g(ar) can be defined as,
Cp - Lgg = glx)p(z)dd ((x)g(x))d
where =(z)= 1, 0), v)p(() (1p))///)d bry. Follow Wang & Ye (2015), we assume that the prediction functions have bounded norm [ p. Thus, the function g is bounded. By given the loss function, also measurable. Then, 9 ğ E C(x). such that,
J. Lawtrltaae
J olooa(tade = [ [. f g(x))(()dd
| g(x))(x)de ((x))(x)de - (MD()(s).((x).c) jec(x)
sup
where C(x) is the function class of bounded and continuous functions of z. To make the MMD term be measurable, we empirically restrict the MMD on reproducing kernel Hilbert space (RKHS) with the characteristic kernel He. Following Gretton et al. (2012), know that the relationship between the true MMD and the empirical MMD is.
MMD(S,, S, He) 2 e 2(1 + +229)
C
(MMMD(p()))
2e 20 1N
where MMD(S,, S, Ho) ) is the empirical measure for MMD(p(z), g(z), He). Slightly overloading the notation, we denote S q(x). which may not be i.i.d., and the initial label set So p(r). Then, in the active learning setting, So S S. Further, we denote |Sol = no, |S| = and Vx, E
S, (rr, x') C. Therefore, we have, v c + + ng 2
For constant factor y M
M
have the following inequality,
((MMD(2()). Z MMD(S,, S, Ho) + + S 2e 2
C
Denoting 2e 2 = =8/2, then we have e that with probability at least 1 - 8, the following inequality holds:
4C (n48))
Combining all the above results, we show
7
C
4C 4C1n(4/6)
Cp - C, v (S, S, Ho) + +4V
+
V
n
m
Then, we can get,
C'In(1/0)
C by MMD(Ss, S, He) +0
n2
C APPENDIX: MORE DETAILS OF EXPERIMENTAL SETTINGS
C. IMPLEMENTATION DETAIL.
For simple CNN model, we utilize the same architecture used in Pytorch CIFARIO Image Classi- fication Tutorial For ResNet model, we use the Pytorch Offical implementation of ResNet- 18 and set the output dimension to the number of classes. For VGG model, we use the Pytorch Offical implementation of VGG-11 3, Besides, we leverage the library BackPACK (Dangel et al., 2020) to collect the gradient of samples in batch.
http:://gggchaaogoaaaaaasseseett htmi
thub. http://hwww.ppppoooooooooooooota s/
htw.toddtddd.eeeeeee..eeeeee resnet.
py
'https:/ thub. http://www.ppppoooo////oo/aaaaaa s/vgg-py
19

---

Under review as a conference paper at ICLR 2022
We keep constant learning rate of 0.001 for all three datasets and all three models. All the codes mentioned above use the MIT license. All experiments are done with four Tesla V100 SXM2 GPUs and 12-core 2.2GHz CPU.
D APPENDIX: VERIFICATION EXPERIMENTS UNDER ULTRA-WIDE CONDITION
D.I EXPERIMENT SETTING AND COMPUTATIONAL DETAIL FOR THE EMPIRICAL COMPARISON BETWEEN NTK AND MMD
Experiment Setting For the verification experiment shown in Figure we employ a simple CNN the target model, in which there are three convolutional layers following with global average pooling layer, on the CFAIRIO data set. Note, this CNN architecture widely used in NTK analysis works (Arora et al., 2019a; Zandieh et al., 2021). To make the verification experiment close the application setting, we keep size of initial labeled set and query batch size same as what we used in Section 5.
Computational Detail We follow (Jia et al., 2021) to compute the MMD with NTK kernel. The MMD term, MMD(p(z), ((x), He). can be simplified into the following form:
((e)) = E(O my) x,), - (1I,,
(31)
where Te, By ~ p(x) and 24 J ~ g(x). Then, we define set So as {"1,..., ~ p(x) and set S as (z'...., 2n13 q(z), where no S n. The MMD2(S0. S) is an unbiased estimation for (pD)))( ((x)), can we explicitly computed by:
MSo s)= m² m
2
nt2 m(n 1)
( xT)) Σ (3i,
(32)
b
Σ
O 1/))
Σ (a(,
Σ
Σ
θ (3i x5)
Σ
O
Therefore, the MMD term of Equation (23), MMD(S S, He) can be empirically approximated
by / /M. S).
D.2 EXPERIMENT SETTING FOR THE CORRELATION STUDY BETWEEN TRAINING DYNAMICS AND ALIGNMENT
Experiment Setting For the verification experiment shown in Figure 2, we also use the simple CNN on CIFARIO. And to keep consistent with the application setting, we set [S| = 500 and Q = 250. The Q randomly sampled from the unlabeled set and the labeled set fixed. We
independently sample Q 150 times to compute the correlation between between GMSH(S Q) and A(XIIXq: Y|))))
E APPENDIX: MORE DETAILS OF EXPERIMENTAL RESULTS
E. BASELINES
1. Random:
Unlabeled data are randomly selected at each round.
2. Coreset: This method performs a clustering over the last hidden representations in the network, and calculates the minimum distance between each candidate sample's 's embedding
20

---

Under review as a conference paper at ICLR 2022
and embeddings of labeled samples. Then data samples with the maximum distances selected. (Sener Savarese, 2018).
3. Confidence Sampling (Conf): The method selects b examples with smallest predicted class probability max (1;; 0) (Wang & Shang, 2014).
4. Margin Sampling (Marg): The bottom b examples sorted according to the example's multi-class margin are selected. The margin is defined as f' 0) - (x; 0), where and are the indices of the largest and second largest entries of f(; 0) (Roth & Small, 2006).
5. Entropy: Top b samples are selected according the entropy of the example's predic- tive class probability distribution, the entropy is defined as H ((f 0)); where (pp) Σ; p, 1 (Wang & Shang, 2014).
P.
6. Active Learning by Learning (ALBL): The bandit-style meta-active learning algorithm combines Coreset and Conf (Hsu & Lin, 2015).
7. Batch Active learning by Diverse Gradient Embeddings (BADGE): b samples are selected by using k-means++ seeding on the gradients the final layer, order to query by uncertainty and diversity. (Ash et al., 2020).
E.2 EXPERIMENT RESULTS
The results for ResNet18, VGG11, and vanilla CNN CIFARIO, SVHN, and Caltech101 with different batch sizes have been shown in the Figure and 6. Note, for the large batch size setting = 1000) on 1a1,ech101, we set the number of query round 4, in which 49.2% images will be labeled after 4 rounds.
E.3 NUMERICAL RESULT OF MAIN EXPERIMENTS
For the the main experiments, report the means and standard deviations of active learning performance under different settings in the the following tables.
Table 2: CIFAR1O, CNN, Query Batch Size:250, Initial Set Size:500
Marg
Entropy 3252211 2695
4ynamic41.
0
32.5 22,35%
1.06%
32.48%
256%
32.41::11 181%
33.275
2666
32 13.50%
1,267%
32.66% 1882%
11.33
1.155% 33,00%
33.161t 1:1 1.166
32.74% 1.61%%
32.75%
1.306%
33.00%
1.703%
32.98%
1.184%
33.45%
1.813%
33.52%
1.311%
34.06%
33.77:1110119
14.11%11.402
34.02%
31.66%
14.70%
35,059
1.508%
25.50%
1.100%
35. 10.1
1.6999
30.44%6--.9579
35.25%
1.344%
34.97%
1.227%
35.7556
1.024%
35.79%
--.115%
35.64%
1.945%
36.55%
1:1 1.119%
36 14%
1.44--11.544 1.545%
35.08% 1: 1.3991
36.59%
1.508%
35.58% 8: 1.17%%
36.33%
0.7911%
36.22%
1:0.716%
28%
1.124%
37.18%
1.1 547%
36.77% 1.004
35.68% 1: 1.399%
37.19% 1.06%%
36.15%
1.311%
37.29%
1.126%
37.45%
1.533%
1.368%
37.28%
37.65%---2200222
1.988%
37.29%%
1.605%
28.01%
1.0.74%%
37.67%
1.
36.57%
1.346%
38.09%
1.11%%
37.07%
1.731%
38.28%
1.47.5
38.11%
1.295%
37.59%
1.848%
38.43%
1:1 1.675%
38.01% 1.009
36.98%
1.7.48%%
38. 38.58%
1.556%
37.35%
1.335%
38.51%
1.091%
76.70%
1929/
37.85%
1.7891
38.29% 1.312%
37.2516
38.91%
57.57%
1.170%
38.7816
0.77766
38.91%% 1.39%%
Table 3: CIFARIO, CNN, Query Batch Size:500, Initial Set Size:500
Marg
Entrupy
0
92.369 1.1621111665 184%
32.31%
441%
52.20% 1: 307%
32.54%
111%
33. 325
1.88%
32.41%
1.442
32.20%
1.300
320%
$2.17%
11005
34,87% 2:1 28648
34,89% +:1 575%
34, 58.5 +: 6644
33.845
368%
34. 34.75%
5.30%%
$4.08
54.08%
1.36%
34.44%
1.230
34.99% 2:1 1.557%
1.5559
882%
+: 15665
36.50%
35.9096-:1
1.667%
1.74%%
1.536/
+: 1.253%
37.99%
3565%
17.30%
36.209
1.685
1.66%
36.55%
37.569
1.7445
303
80.0099-200 80009
30.155
0566%
53.23% 8.8788
16.75%
39. 10.108:::100 3365
57 17.20%-22
1.381%
38.4918
1.239%
30.37%
1.07009 708%
38, 59.6995 - 0.8611
39.98% 1:1 502%%
39.01% + 1.2789
39.81%
1.42%% 400%%
57.80%
1.550%
39.61% + 1.219%
40109 +-1.9405
1088
3019
97.979:1
40-47%:1:1 1.16%%
58.47% 1.270%
2: 1.11%
39.51 01.5118::11
40.999
2175
10.59921.6008
41.05%:::
39.11%
40.9798-0.811489
41.21%
30. 000.00992200000 0.8877
41.39%
1:1 614
40 30%
3575
39.06%
41 11.3099.. 5665%
30 10.55% 1.50%%
41. 41.27%
.09%%
41 11.599 1.011%%
40.17% 1.170
41.64% 1 287%
40.71
71.71%9..77999 7399%
39.4398--:8925
41.559-4:111 1.141%
59 19.955%-22 1..9%.211.299 1.999%
41.79% 2:0.6459
21

---

Under review as a conference paper at ICLR 2022
Query Size:250,
CIFAROD, BesNes, Quary Batch
39
50
38
Test Accuracy (%6)
Test Accuracy (96)
25
34
Random
Conf
35
Random
Conf
Marg
Entropy
BADGE
Entropy
BADGE
Coreset
dynamicAL
30
dynamicAL
Query Round
# Query Round
CIFAR1O, Restlt, Query Batch Size:1900, Intiia Size 500
SWHN, Sice:1000, Inibal Size:500
Test Accuracy (96
Test (%)
70
40-
50
Random
Conf
Random
Cont
Marg
ALBL
40
Mang
ALBL
Entropy
Entropy
30
Corecet
dynamicAL
Coreset
dynamicAl.
Query Round
# Query Round
Caltech101, Reskict, Query Batch Stoc:1000, Inital Set Stee:500
Accuracy (86)
45
40
35
Random
Marg
ALBL
Entropy
dynamicAL
Coreset
Query
Figure 6: The evaluation results for different active learning methods under a range of conditions.
Table 4: CIFARIO, ResNet, Query Batch Size:500, Initial Set Size:500
Random
Marg
Entrupy
28. 75% 7809
78.75% 1.0 360%
2K.79 21 3045
28.49
120%
78. 315
1.01%
28
78.75
28.95%
1.09%
7x. 525 1:0 6869
34. 34.11% 2 0885%
34.62% 4 0224%
54.42% 2 849%
34.57%
33.49%
1.20%%
44.4%% 2.077%
54.42%
34.26%
35 $5.599 2:2 8585
4000%%
1.222%
38.44561111 1.4088
38.23%
1.44%
40.10%
2.574%
39.7816
1.344%%
1:0-9999
18%
40.969-1099618
40.87%
42.06%
41.74%.21.333
1.300
42.51%
18.1188-22 1.8099
44.09% 1:1 165%
41.0%% + 15005
42.60%
1.00:--:1..00000 1994%
43. 43.10%
1.32%
43.52%
3.0664%
43.7698
1.364%
44. 44.36%
1:0-9000
46 7338 2535%
45.57% 1:1 1.15%
45.00% 5-0 0.733%
43.86/6
1.3699
44.83%
11339---11330 1.399%
3.097% 44.64%
44.73%
1.675%
46.02%
4-1.754%
1188%
46.38981:
1888--1140077 4075
1.07%%
189
1.5029
47.47%:4:
47.18
47.17%
47.911 1.722%
49. 26% 1:0 6526%
49 0606
+: 119%
47.14% 1880
48 40F 1.78%
48 18..188 501/
48. 18.111%::11 1 1.04%
40 30.5%% 673%%
48.56 84% .844%
49.75% 1 341%
49 20.466%-22
2825%
48.179-: 1.80%
49 39.359-411 1.99%%
49 45%
49.0698
50.50% 5011%
22

---

Under review as a conference paper at ICLR 2022
Table 5: CIFARIO, ResNet, Query Batch Size: 1000, Initial Set Size:500
Random
Many
Enirupy
Caresel
Conf
ALBL
BADGE
dynomicAL
36.34% 1.46%
28.0P% 1 0045
25 E: 1,750%
29.05%
1.13%%
2910/
0.847%
28.18% 20022
329%
39.5798
50.09% 180%
38.95% 144%
40.5094-22
2 340%
39.675
39,409--30005
40.099-111
7059
2
15.0388-4
1,255%6
45.45%
444%%
44.48% +: 111.8.588 82395
43.78%6
45.62% +:1 2824
43.58%
1.325%
45.77% 222.422222500
47 50000
257%
47.96% +:0 735%
48 15% 2..5222.0005 509%
48.82%
7975%
47.24%
1.926
47.89% 189%
40.32% 4:1 704%
00.1338-2
49.97% 2.819%
48.14%::0.5668
50.79%-4
1.70%%
49.05%
1.851%
49.1398-440588
51.50%
1.517%
52,2416
520005 +
49.89%-+1107996
52.399--222002%
50.59%
1.6.0%%
50.94%
3-6299%
53.2418-:11
53.3398:2 1.3009
51,879
53.579 2.77%-1.100 1239%
$2.01%:2..788
$1 51.999 5009
52.699
1.599%
52.36%%
1.924%
55.069 11.788
54. 8548 =1 1.238%
55.199 1 1366
54.79% #:3 14498
$2.999=11147%
55 0..00%++220000
54.20%
1.68%%
53.7798
3-399999
56.33% 11619
1.161%
+-0.732%
56,23%
1.318826
36.79%---2.0039
55.209
1.885%
14.9118-44411445
1.706
57.7388 50056
$7.2999-11.2299
514299219545
57 2..7099-2.0425
56.67%
1.783%
56.0298 3.9399
58.569
5744%
Table 6: SVHN, VGG, Query Batch Size:500, Initial Set Size:500
Random
Marg
Entrupy 20.41% R8.55S
Corrsel
Conf
ALBL
BADGE
dynamicAL
131%%
250%
25.83%
26.52%
4.5%%
25.31%
26.38%
100%
20.30% 50.%
61. 25% 24.29%281822
63.938 1 12748
50.025
2.77444 4.74%
17.02%-4.67225
61 19999261888
62. 33.144
58.209-566118
63.011112..00
71 35.35% 2 764%
34,08%
52393
71.25% = 4599%
47.95%
23.319
71.75%=2.5555
74.74%
2.978%
74.10%
4-.555%
1.620%
79.17% +: 06-418
76.74% 1.525%
73.7096--2284800
78.02%
77.65%
77.75%6 2-251---22200 100%%
79.20%
4-2.51%%
1.88%
82.18984:0
5049
79.67%
8.89%
78.14%:22
11.3229-::1000 1.00%
81 0096-11111 1.005%
80.1698:::1 1.3535
82.11% 13.11%
80 5068
21 1499
83.85%
75049
81 81.7% 0776
20.5498--2.11990
53.91%%::
83 13.377%-22 ..255
82.9446-
84.19% + 1400%
81 99.
334%
85.61%
6344%
83 0.5599
62:528
1.592%
84 149948-1-.8888
85 19% 99399
83.69%
1:0 9.55%
85.80%
498%%
00.00%:::1
048%
86.62%
1:0 607%
84 2000:0000000
83.98%-::1
65.97%-1:1100
760%% 85.1588:100
56.75%
87.5778
1:088-200000000 62546
85. 7895 0:0088
85.26/6 1.91%%
57.1399-:006799
37.55%==0.8831
86.61 0.
57.91%
2.44%
84.42% 0.744%
88.23%
1:0 600%
87. 14550
86. 86.1889:008880
87.878.1:00 5588%
87 07.8899 0.788.
87.29% 4411%
58.52% +:1 1400%
Table 7: SVHN VGG, Query Batch Size: Size:1000, Initial Set Size:500
Random
Marg
Entropy 2685% 4 20155
Coreset
Couf
ALBL
dynamicAL
0
25,00% 1.4799
26.208 1.5 4099
26. 26.1899-6.2336
27 21 2.2211
4.688%
26.8896 248%
26.45% 2 3..47%
70 22.369 2: 1.54%
69.06%
1.666%
68 72% 2: 156%
68.48%
111%
68 08855-13338899
70.51 3.87%
70.09%
70.04% 1: 1.60%
77.91
1 237%
56.566
77.66% 1.744%
18.899
78.14%8:1
78.678:111700
86.8% 1.710%
83.68% 6575%
52.83%-0.55270
12.54%:::146615
63.75% 165%
83.50% 1.600%
13.07%::1.33300
83.11%-::1 1.269%
83.63% 0. 7.46%
86.12% 13119
85 85.809 7444%
1..54%
$5.918.:11113
86 1.99777
86, 16.50%%:1 1.87%
85.70% 1: 1.70%
85. 11.1178-00000 0
88.049
0224g
87 67.66 6..66%%
87.19%
87.61%-111004 1.44%%
87 67.65% 1.0315
88.03% 7425%
87. 46.6% 11054 1.054%
86.0 86.009
80.1388 +:
99586
08.699--005055
58.908-1-0445
8.09%
08.4118-200001
10.9%%
= 1.274%
17.300::000000
90. 30.36% 1:0 512%
90 00000:00:0000000 257%
89.65%:100 4865
90. 00:18881:000066
89 80.8376:00000000
90.5398::0.44
90.099 149%
375%
90 385%
90. 90.15%%::
90 20.968 00.969-1:00677%
90.75%
31.2558820044222
90.98% 1:0 7838
88.28%
91.595 1:777
91.25%
90.618:1031115
91. 73.55%
91 91.41%2206665%
91.76%
01.67%110.440
Table 8: Caltech101, ResNet, Query Batch Size:500, Initial Set Size:500
Randoua
Marg
Entropy
Coresct
Conf
ALBI
dynomicAL
0 21 59% 1 1.431%
21 989
688%
21. 49% = 681%%
21 39.99 10 1 738%
21. 21.98-22 1599
21 1..32 1.838%
21 1...8-11.3255
1.1-111112
28.42%
27.43%
28.61%
15555%
28.02%111.555%%
29.348:2..115
94% 0..35%
34.76%:1111
7.55%
32.94% +: 2.42%
1
32.85%
149%
15.869-1:00120
37 34% 1.88%
19.708 1.28% 128%
36 16% 2:0 6366
40.19 .015%
37.528 1520%
40.20%-1:1 1.01%%
41. -1.199920.7899
13.87%-1-0888
43.26%
16622
40.12% 1:0 305%
45.38%
5.508%
11.82% 1 1.00%
1127%-10.72594
4..5%
46.25% 1.56%
43.24% 617%
47.1%:211
6834
44.608
295%
48 35
49.439:1:1 1.299
60% 1,383%
40.208::11110
45.71%
+ 047%
50.09
1.59%
:0 760%
$1 21:209-t:111 4466%
52.51%:=1.7500
49 97% 0..5000
51.40% 1 1.571%
48, 19% 1:0:208%
1887%
49.19%
885%
53 9.999-1:11 1666
15.00%-111.0995
52 060- 1:1 1.76%%
53,569::2:
044%
50.81% 2:0 9439%
55.31%
1.09 105%
51.99%
383%
56 129-1:0.8389
56 1.
51.015--0.698%
55.92%
0..49
53.05% 1:0.554%
0.6911
1.998
57.99%-1-088054
58.81% 1.000%
Table 9: Caltech ResNet, Query Batch Size: 1000, Initial Set Size:500
Randon
Marg
Eatropy 21,839% 735%%
Coresct
Conf
ALBL
dymanicAL
1550%
22.05%
0011%
12,038:11 1.336
22.059:1::6633
2144%:11.77 1.73%%
33.809:::
0025
31. 31.98% + 100%
33.40%-00
37.499-228855
33.669--22.1 174%
2
42 1099-10.500%
41.22% 11.00.00000 730%
39.23% 10096%%
43.24% 0.960%
40.05%
1.0988%%
43.2891--2.36672
43.27%
3
140%--00.7009
47.169::006599
46.26% 1:0 968%%
50.51%
1.511:20.7000 7069
47.87% 698%%
50.10912..889
50.499=1..6348
52.77%-10.99%%
54.52% 1.28%%
54.11%
56.15% 1.261%
53.76%
1.16%%
56.96%---1.733%
57.52%-21.169%
E.4 MAXIMUM MEAN DISCREPANCY FOR MULTIPLE ROUNDS
As shown in Figure 1, the MMD term is much smaller than the B at the first query round. To better understand the relation between MMD and B for multiple query setting, measure the MMD/B
23

---

Under review as a conference paper at ICLR 2022
for R 2. As shown in Figure 7, B is much larger than MMD even multiple query rounds. Besides, we notice that, for the first round, the larger query batch always leads to larger MMD/E B, because the sampling bias introduced by the query policy will be amplified by using large batch size.
0.010
100
500
250
1000
0.009
0.008
MMD/B
0.007
0.006
0.005
0.004
0.003
2
3
4
# Query Round
Figure 7: MMD/B for larger query round.
Furthermore, we measure the MMD/B with a constant total budget size but different query rounds. The result shown in Table 10. As our expectation, spending the total query budget in one query round will induce the largest MMD/E B. And, with more query rounds, the MMD/E B will be lower.
Table 10: MMD/ under constant budget size.
R 10, 100
R 250
R= 2,
500
R= 1, 1000
MMD/B
0.004999
0.005253
0.005367
0.005455
E.5 EXPERIMENT RESULT IN RETRAINING SETTING
In Section 5, mainly focus the non-retraining setting, in which the weights of the network obtained in the previous will be used for the next AL cycle. To further study the effectiveness of dynamicAL in the retraining setting, in which the network will be reinitialized after each query, we compare dynamicAL with the strong baseline in the retraining active learning setting, such as Coreset (Sener & Savarese, 2018). We follow Ash al. (2020) to query samples when training accuracy be greater than 99% and the results are shown in Table 11 and 12. The results show that dynamicAL can still be better than or competitive with the commonly used active learning methods. Besides, we notice that the improvement in the non-retraining setting is more significant, because the dynamic analysis (Equation (8) considers the change of dynamics according the model's current parameters.
Table 11: CIFAR1O, ResNet, Query Batch Size 500, Initial Set Size 500.
#Round
Random
Coreset
dynamicAL
0
30.80=1.81
30.77+0.92
30.94+2.17
35.80=1.52 36.62=2.10
36.47=0.13
42.91=1.75
43.16=1.79
42.74+2.44
3
43.76=00.6
44.35+2.25
46.43+1.07
4
17.9
18.74.11.94
49.38-11.80
5
19.16=1..77
1..20
51.61+1.099
52.43+11.33
13.44
54.33+
12.81
53.8910.78
14.59+1.04
8
54.5610.23
57.12
57,50
18.08 9
59.62+1.50
6..35
24

---

Under review as a conference paper at ICLR 2022
Table 12: SVHN, VGG, Query Batch Size 500, Initial Set Size 500.
#Round
Random
Coreset
dynamicAL.
12.68
6..7416.16
52.39:13.73
1.96
68.0813.61
66.4814.10
2
73.46=1.51
1..93=1.44
74.34+2.22
3
77.30=1.08
76.49=2.08
76.73+2.65
79.27=0.78
79.33=0.72
80.19=0.78
19.97
82.09:11008
1..9
83.97=10.42
82.30-10.33
83.80
7
83.44-0.557
83.29-1.111
84.85+1.12
86.24=0.52
84.72:10.52
1..5
83.75=1122
85.62:1..55
86.57=00.44
F LIMITATION AND FUTURE WORK
Our proposed active learning method, dynamicAI. is designed for the small budget, non-retraining setting in active learning, which is commonly other settings (Mittal et al., 2019). However, as shown in Appendix E.5, if retraining from scratch is affordable a certain application, the performance our method is comparable with -tate-of-the-art techniques, such as Coreset (Sener & Savarese, 2018). Moreover, there are some works trying to combine the techniques of self-supervised and cemi-supervised learning with active learning (Mittal et al., 2019; Chan et al., 2021). As demonstrated in the recent semi semi-supervised learning works (Sohn et al., 2020; Rizve et al., 2021), the data augmentation, consistency regularization and uncertainty- aware pseudo-label selection will boost the quality of the pseudo labeling that dynumicAL, relies on. Then, potentially, they can improve the performance of dynamicAL. Besides, large initial set size and properly selected initial set (Yuan et al., 2011) also potentially improve the quality of the pseudo labeling. Therefore, future research directions include theoretically analyzing the effect of semi-superee supervised learning technologies for active learning and empirically verifying the effectiveness of combining dynamicAL and semi-supervised learning technologies retraining and non-retraining active learning settings.
practice, and tends be more challenging than
25


Reviews:
[{"review_id": "nwM2fUTYHpg", "reviewer": "Reviewer_p3z9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper has a nice derivation of the dynamics of the training loss and provides an algorithm to maximize the rate of convergence.\n\nMy biggest concern is the empirical evaluation. In the training regime on CIFAR10, only 37% test accuracy is attained which is really really low. Secondly, it is strange to have different experimental settings (batch size, number of rounds) for different datasets. I think the experiments require a larger amount of data (at least up to 10k labeled points for CIFAR10 and SVHN).\n\nOther comments:\n\nIn equation (15), is the gradient squared supposed to be in the summation? It doesn't depend on the summation so it seems like the summation is a factor of |S|.\n\nShould the inequality in equation (23) be in the other direction? How does maximizing over a restricted (smaller) set result in a larger value?\n\n", "summary_of_the_paper": "This paper provides a theoretically-motivated active learning algorithm based on maximizing convergence speed, which is justified by the \"train faster, generalize better\" intuition. The paper has limited but favorable empirical results. ", "summary_of_the_review": "The theory in this paper appears good, though I am not very familiar with NTK analyses which makes me hesitate to say more. The empirical evaluation lacks quality however.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IoIpj90QAk", "reviewer": "Reviewer_YgGb", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes a new active learning strategy that samples examples which would help the network converge faster during training.\nThe paper suggests that faster convergence during training typically leads to better generalization performance. Therefore it should be beneficial for and AL algorithm to select examples that will speed up training convergence. \nThis speed-up is measured by approximating the derivative of the of the loss with respect to the training iteration t (which they call training dynamics). The authors propose many relaxations to be able to compute this derivative in practice, notably: (i) when computing the loss, assign weak labels to unlabeled samples, and (ii) instead of computing the derivative on all possible subsets, compute it separately for each unlabeled example then approximate the training dynamics of a subset using the sum of the training dynamics of each sample in that subset. \n\nStrengths:\n\n1. The paper is well written and well organized. \n2. The idea of linking training dynamic to active learning is novel and potentially influential. \n\nWeaknesses:\nThe main weakness of this paper (and the reason I am not recommending it for acceptance) is its experimental section. The theoretical section is well written, but the problem is completely non-tractable and cannot be theoretically analyzed in a realistic setting so the experimental section is instrumental and necessary to support the paper's claims. However, I don't think the experimental section is thorough at all. \n\n1. Coresets AL is a very strong baseline on Cifar10 with a ResNet18, so it is a warning sign that in your experiments it underperforms compared to Random. If you look at Fig 4 in the coresets paper [1], all  AL methods (including Random sampling) hover between 60% and 65% accuracy on Cifar10 with budget 5000 using a VGG-16. I have also run many experiments in that exact setting using a ResNet18 instead and it's easy to reproduce these accuracies. \nIn fact, figure 3)a) in [2] (which you cite in your paper), runs the same CIFAR10 experiments and reports around 78% for random sampling using 5k samples. However, in the middle-left and top-right plots of your Figure 6 of Appendix E.2, the best accuracy on CIFAR10 when the budget is 5000 using a ResNet18 is below 55%. [2] provides the exact training hyperparameters to reproduce their results so you can try copying them and rerunning your experiments. \nThe only difference between your experiments and those in the CoreSets paper is that you don't retrain your models from scratch at each round and instead you continue training from the previous checkpoint. So either (a) not resetting the network weights makes a big difference or (b) your training hyperparameters do not allow the network to train to saturation. I don't think (a) is the culprit here because if you look at figure 3)a) in [2] they report 45% on CIFAR10 using 1k randomly selected images while your number is less than 30% (this is when you train from scratch at round 0). \nIf (b) is true then those plots are inconclusive, since you're not training to saturation and your method is specifically targeting examples that allow faster convergence. \nI know that it can be very hard to find good hyperparameters for these experiments because you're trying to use the same learning rate schedule at round 0 as you are on round 9, but the learning rate schedule that works with 1000 training examples is likely less than optimal when training with 9000 examples. \nI also understand that it saves computation time and cost to continue training where you left off at the previous round but running at least one experiment where you train from scratch at each round is again necessary to at least show that this isn't the reason your method stands out. Also these experiments can take less than one day when using the machine you mention in appendix C.1.\n Obviously in my comments above I focus on ResNet18 on CIFAR10 because I am familiar with this setting and could find apples to apples comparisons to point you to in [2] , but you should revisit the rest of your experiments on other datasets to verify that they do not suffer from the same problems. \n\n2. I understand that you use small budgets in your experiments to save compute. However, using a small initial budget benefits methods that don't rely heavily on the classifier's feature extractor. If you choose a small initial budget, the feature extractor will be messed up and again methods such as Coresets will completely mess up. \n\n\n[1] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018.\n\n[2] Zhuoming Liu, Hao Ding, Huaping Zhong, Weijia Li, Jifeng Dai, and Conghui He. Influence selection for active learning. arXiv preprint arXiv:2108.09331, 2021.", "summary_of_the_paper": "This paper suggests a new method to perform active learning by choosing prioritizing examples that lead to faster convergence during training. ", "summary_of_the_review": "I found the paper's experimental section to be insufficient. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "FDVX1FMmCj", "reviewer": "Reviewer_j1Xn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\nThe paper is technically clear and well-written, with good result on toy benchmarks (i.e., clean, small images with mostly balanced distribution). The method seems to be a good continuation of Ash et al., 2020; Liu et al., 2021 and built a theoretical bridge between these objectives with the training dynamics and generalization in deep learning theory justification.\n\nWeakness:\n* The infinite-width assumption: The main theoretical result (Theorem 1) is derived under the assumption of infinite width model. However, it is well known that the infinite assumption does not hold in practice (e.g., [Fort et al, 2020](https://arxiv.org/abs/2010.15110)), which has led the community to derive better approximations such as NTH ([Huang and Yau, 2019](https://arxiv.org/abs/1909.08156)) or their more tangible lower-order approximations ([Chen et al, 2020](https://proceedings.neurips.cc/paper/2020/file/b6b90237b3ebd1e462a5d11dbc5c4dae-Paper.pdf)). While I understand the authors are building their results based on classic NTK theory, it is still worth addressing (can be non-rigorous or based on small empirically verifications) cases where the infinite-width assumption does not hold. Mostly if the high-level conclusion of the theory (faster training -> better generalization) still hold?\n\n* The Pseudo Labeling approach: While I understand this is a technique that is being used in the previous works, I wonder what would  would happen if model prediction is wrong, such that the training dynamics is computed against the wrong label? Some comments about this in either Section 3 or in the conclusion section would be helpful.\n\n* Clarity: This is a minor comment: To make sure the deposition is maximally accessible, please provide derivation for equation (13) and (15) (e.g., in the appendix).", "summary_of_the_paper": "This work proposes DynamicsAL, a novel AL criteria that selects new training example base on its ability to maximize the training dynamics $\\frac{\\partial}{\\partial t} l(f, y)$. \nThe authors supplied a practical algorithm (Section 3.2) and compared the proposed criteria with existing methods (Section 3.3).  \nThe authors also derived theoretical result on faster converges leads to better generalization (Section 4) under the assumption that the network has infinite width, and also empirically verified their result based in the non-i.i.d. case. Experiments on standard benchmark and architecture (CNNs on CIFAR/SVHN/Caltech101) are conducted, where DynamicsAL is shown to outperform existing approaches.", "summary_of_the_review": "A paper that continues the investigation of active learning using gradient/influence function signal (Ash et al., 2020; Liu et al., 2021). It builts a theoretical bridge between these objectives with the concepts of training dynamics and generalization, and supplied a algorithm that is practically effective. I personally find this work to be a nice value add to the community, both in terms of the theoretical contribution and the practical utility of the algorithm. Hence recommend accept.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EFYtrRsMt89", "reviewer": "Reviewer_8dDv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe work is very timely, since it leverages on recent results to provide a better objective for deep active learning, namely the time independence of the NTK and the train-faster--generalize-better paradigm. From there, everything descends smoothly, providing a clean story and a method that seems to work well. Even though the theoretical analysis is only justified in the ultra-wide limit, the empirical evidence provided (on satisfactory models and datasets) suggests that the method is still good for typical use cases.\n\nAs the authors truthfully recognize, with active learning the data is not iid, and this needs to be addressed. In particular, it is not clear that the dominant term of the population risk is given by B (which then goes as 1/Alignment). To do so, they upper bound the difference of the population risks using the two distributions (from population and from active learning) by the Maximum Mean Discrepancy (MMD). Then, they show empirically that MMD<B for several values of b, on the first query round:\n\n- They state that  the MMD is always much smaller than B, but the blue and yellow bars in figure 1 look similar. It took me a long while to realize that the bars have different axes. There is no legend nor visual aid that helps the reader. This must be changed.\n\n- They only show this for round R=1. Could one expect that the two quantities approach each other for larger R? My intuition would say that the MMD increases with R (though I don't know by how much). \n\n- Practitioners would be often interested in quite large R, but results do not seem to go in this sense.\n\n- From figure 1 we see that bigger b implies a smaller B/MMD. This can be expected, since with a bigger b the two distributions are more different. Would it be more interesting to compare at constant budget size, as done in table 1?\n\n- If we then look at table 1, we see that the best performing schemes are those with many smaller query rounds. Is there some intuitive reasoning that could lead to this expectation? What is the recommendation that the authors would give to a practitioner who wants to implement their method? \n\nDid the authors observe a deterioration in their active learning scheme as models become narrower? Should we expect this? Does this mean that dynamicAL should not be used for \"deep and narrow\" models?\n\nWhy only 4 query rounds for the CIFAR and Caltech datasets? It doesn't seem that the performance has converged as for SVHN (which got 9 rounds), and the performance is not close to those that are obtained in practice.\n\nFigure 3 might be more readable if different symbols are used for each method. I had a hard time identifying each curve.\n\nThere's a couple of typos and expressions that need some English polishing (nueral, convergence faster, ...).\n", "summary_of_the_paper": "The authors address the problem of active learning in the context of deep learning. Instead of querying new examples based on the decision boundary (which in nonlinear models can be tricky or even ill-defined), as it is usually done for linear models, they rely on the train-faster--generalize-better paradigm. Thus, they propose to optimize the \"training dynamics\", which is the time derivative of the loss function in the ultra-wide limit. By using pseudo labeling and subset approximation, their method allows for fast selection of the examples that should be added to the dataset.\nThey justify their active learning strategy through an analysis in the limit of very wide models, through the neural tangent kernel, which is particularly convenient since the NTK does not depend on time in the ultra-wide limit. \nThey study a quantity that they call \"alignment\" (which measures the correlation between input and output in the NTK space) and show that a higher alignment is related to better generalization (a better bound) and faster training (--> larger training dynamics). They then show that this is also true in the active-learning setting, where the data is no more iid, with the help of some empirical evidence. Finally, they test their method and compare it with other active learning strategies, which they systematically outperform.\n", "summary_of_the_review": "The paper looks good. Some aspects of the presentation can be improved. Some of the results rely on approximations or numerical evidence which might not be universal, but I find the method quite interesting, and it paves the road to new possibilities in deep active learning.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel strategy for deep active learning based on the training dynamics of the underlying deep model, defined as the derivative of the loss of the ultra-wide NTK. All reviewers enjoy the clean story and motivation of the proposed acquisition/objective function and appreciate the authors’ effort in providing theoretical justification and analysis. 

One note is that -- as Reviewer 8dDv highlighted -- part of the analysis pertaining to the incompatibility between the generalization bound of NTK and the non-iid nature of active learning rely on numerical evidence: the MMD under the covariate shift setting (i.e. assuming that the conditional distributions P(Y |X) remains consistent) is shown empirically to be smaller than the dominant term of the generalization bound. This serves as a reasonable empirical motivation/ justification of the dynamicAL heuristic under the AL setting, but I would suggest the authors be more precise in the abstract / intro (e.g. abstract) that this is an empirical result. 

While the theoretical results are interesting, not all reviewers are convinced that the experimental results are sufficiently compelling. In particular, Reviewer YgGb points out that the significant performance boost reported in the main paper was mainly due to the non-retraining (i.e. not retraining the model (from scratch)) constraints imposed by the problem setup. Reviewer p3z9 shares the same concern that such a setting would be far from realistic at least for the data sets/labels considered in the experiments. The authors refer to Ostapuk et al, 2018 as a justification of the non-retraining setting; yet they assumed a high budget, e.g., up to 50% of all labels of datasets. 

In summary, this is a theoretically well-motived work, but the empirical components need to be further clarified and supported with more realistic experiments to merit acceptance for the proposed solution.
Decision: Reject