A Neural Pre-Conditioning Active Learning Algorithm to Reduce Label Complexity
Authors: Seo Taek Kong
Soomin Jeon
Dongbin Na
Jaewon Lee
Hongseok Lee
Kyu-Hwan Jung
Venue: NeurIPS 2022 Accept (2022)
Keywords: Active learning
neural tangent kernel
semi-supervised learning

Abstract: Deep learning (DL) algorithms rely on massive amounts of labeled data. Semi-supervised learning (SSL) and active learning (AL) aim to reduce this label complexity by leveraging unlabeled data or carefully acquiring labels, respectively. In this work, we primarily focus on designing an AL algorithm but first argue for a change in how AL algorithms should be evaluated. Although unlabeled data is readily available in pool-based AL, AL algorithms are usually evaluated by measuring the increase in supervised learning (SL) performance at consecutive acquisition steps. Because this measures performance gains from both newly acquired instances and newly acquired labels, we propose to instead evaluate the label efficiency of AL algorithms by measuring the increase in SSL performance at consecutive acquisition steps. After surveying tools that can be used to this end, we propose our neural pre-conditioning (NPC) algorithm inspired by a Neural Tangent Kernel (NTK) analysis. Our algorithm incorporates the classifier's uncertainty on unlabeled data and penalizes redundant samples within candidate batches to efficiently acquire a diverse set of informative labels. Furthermore, we prove that NPC improves downstream training in the large-width regime in a manner previously observed to correlate with generalization. Comparisons with other AL algorithms show that a state-of-the-art SSL algorithm coupled with NPC can achieve high performance using very few labeled data.

A Neural Pre-Conditioning Active Learning Algorithm to Reduce Label Complexity
Seo Taek Kongl
Soomin Jeon?
Donghin Na²
Jaewon Lee3 Hong-Seok Lee
Kyu-Hwan Jung
University of Illinois, Urbana-Champaign SSngkkunkwann University
Dong-A University
VUNO Inc.
Abstract
Deep learning (DL) algorithms rely massive amounts of labeled data. Semi- supervised learning (SSL) and active learning (AL) aim reduce this label com- plexity by leveraging unlabeled data or carefully acquiring labels, respectively. In this work, we primarily focus on designing an AI. algorithm but first argue for a change in how AI. algorithms should be evaluated. Although unlabeled data is readily available in pool-based AL., AL algorithms are usually evaluated by measuring the increase in supervised learning (SL) performance at consecutive acquisition steps. Because this measures performance gains from both newly ac- quired instances and newly acquired labels, we propose to instead evaluate the label efficiency of AL algorithms by measuring the increase SSL performance at consecutive acquisition steps. After surveying tools that can be used to this end, we propose our neural pre-conditioning (NPC) algorithm inspired by a Neural Tangent Kernel (NTK) analysis. Our algorithm incorporates the classifier's uncertainty unlabeled data and penalizes redundant samples within candidate batches to effi- ciently acquire diverse set of informative labels. Furthermore, improves downstream training in the large-width regime in a manner previously observed correlate with generalization. Comparisons with other AL algorithms show that state-of-the-art SSL algorithm coupled with NPC can achieve high performance using very few labeled data.
prove that NPC
1 Introduction
Active learning (AL) describes the setting where model can interact with a dedicated annotator and query for labels. This is in contrast to passive learning where labels are acquired randomly. In base- AL, both unlabeled Zu = Xt and labeled data Z, = (Kz, V/) are available for training. and labels are incrementally acquired by querying D Q labels at each query step until a labeling budget B is met. The question we aim to answer in this work is: "Given images and labeling budget B, what's the maximum performance that be achieved?" Traditionally, AL. algorithms have been evaluated by measuring downstream supervised learning (SL. performance, ie. training Z,, but we argue that downstream semi-supervised learning (SSL) performance, i.e. training on 2 = 2, U Zg, a better benchmark for the following reasons. Supervised learning performance an evaluation metric for AL fails to extricate performance gains from newly-acquired labels y from the influence of newly-acquired samples x'+11 In contrast, SSL trains a model on Z and the only difference of datasets z z after subsequent query steps the labels y and the respective performances reveal gains from newly-acquired labels. While it has been shown
This work was submitted while the authors worked at Vuno Inc. Correspondence skong 10@ illinois.edu and khwanjung @skku.edu
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

that many AL algorithms outperform passive learning (PL) with respect to instance- efficiency. we see that some AL algorithms in fact under-perform PL with respect to this criterion that measures label efficiency.
Simply replacing SL with SSL can introduce new problems in evaluating the lahel-efficiency of AL algorithms. While in principle more data should always be better, SSL performance deteriorates significantly when the labeled set's classes are imbalanced (Lee et al. 2021 Kim et al. 2020). In AL, the number of images corresponding to each class cannot be observed prior to labeling, and constructing a balanced labeled set would require discarding majority classes retrospectively. Class imbalance had not been as problematic when benchmarking AL algorithms with SL performance because large query sizes ultimately yields class distributions closer to uniform. We address this issue by adopting the recently-pun recently-proposed distribution re-alignment method (Kim et al. 2020) applied to a widely used SSI. algorithm called FixMatch (Sohn et al. 2020).
Having motivated downstream SSL performance as an evaluation metric for AL., we seek to maximize performance with respect to a labeling budget B. We propose a neural pre-conditioning (NPC) algorithm that builds on prior work and addresses problems noticed in literature. Our algorithm uses the Gram matrix of the model's gradients with respect to parameters. Gradients of the loss function have been used by Huang et al. (016)); Ash et al. (020)) in the context of AL to model a classifier's uncertainty about unlabeled samples, whereas we use gradients of the classifier's outputs. Because of the difference, the embeddings used by NPC capture uncertainty by comparing the direction of gradients with other possibly more certain samples' in addition their magnitudes. Moreover, our algorithm operates in the batch-mode setting where the collective importance of candidate samples measured together. Lastly, we show that the landscape of downstream SSL is improved when supervised on labeled data selected by NPC which is why we name it neural pre-conditioning.
This paper is structured as follows. Section 2 formally describes why comparing downstream SL performance after consecutive acquisition steps fails to measure the label-efficiency of AL algorithms, and proposes to consider downstream SSL performance as fair evaluation metric. Section 3 lays out the observations made in prior works that motivate the proposed algorithm before proceeding to stating the algorithm and how it addresses these concerns. Section 4 addresses the last pre-conditioning property of the algorithm and describes potential benefits to randomized search procedure invoked by NPC. Lastly, Section 5 presents experiments that show how the proposed algorithm enhances downstream SSL. performance, and highlights how some AL algorithms are not as effective in our proposed setting.
2 Problem Setting and Related Work
2.1 Active Semi-Supervised Learning
To measure performance gains from only newly acquired labels, alternate between applying AL to acquire labels and training a classifier on newly acquired data using SSL., where at first a small set of labels 10 Qo with balanced classes is assumed. At each query step 8, the classifier queries for Q labels y corresponding to samples X' from the remaining unlabeled pool Xt- A state-of-the-ar SSL algorithm named FixMatch (Sohn et al.) 2020) with pseudo-label refinement procedure (DARP, Kim et al. (2020) is used to handle class imbalance when training after subsequent querylacquisitiion steps. We refer to the above procedure as active semi-supervised learning (ASSL) following (Hanneke) 2007), and remark that the term has been used to refer to different procedures (Wang et al. 60 Our ASSL setting closely follows standard AL benchmarks (Ash et al., 2020 2019) with the difference being that SSL, instead
Sener & Savarese 2017] Gissin &
of SL, is invoked for training.
We explain why comparing downstream SSL,, instead of SL. performance at consecutive acquisition steps is better evaluation scheme when measuring the label-efficiency of AL algorithms. Consider two fully-trained classifiers at consecutive acquisition steps s and s + 1. The performance difference of downstream SL (ASL) performance is given by
IP (i (Itest:; Xx U x Yy U U)*+1)= # (test) - P (0 (Itest; X1, VL)) F Vtest),
(1)
where ÿ (Ztests -) is the prediction of a classifier trained on data In contrast, the difference of downstream SSL performance
P (6 (Irests Xt U U... uy # Vreet) - P (6 (Fresti Xt U No, # yteat)
(2)
2

---

measures the gain from only newly-acquired labels yx++ While ASL is affected by both newly- acquired images and labels, ASSL extricates the two and reveals performance gains from only the newly-acquired labels. The above description motivates one reason to consider ASSI,, but it is clear that AL. can be applied to improve SSL. performance as in (Song et al. 2019).
Despite its importance, we believe two main hurdles restrained prior works to consider ASSL. SSL algorithms have seen great advances only recently (Berthelot al. 2019 Sohn et al. 2020 and their full strengths simply weren't I available. On CIFAR-IO, state-ol-the-ar SSL algorithms presented with as few as 40 labels are now able to match full-supervision where all labeled data is used. Second, SSL performance degrades significantly when the class distribution of labeled data is imbalanced. In AL. a-priori enforcing balanced classes is impossible because labels are unknown and discarding majority classes (under-samplingg wastes what was spent to acquire the labels. When the labeled set's classes are highly imbalanced, pseudo-labels generated by SSL algorithms are even more-so imbalanced (Kim et al. 2020). By adopting pseudo-label refinement process, we rectify performance degradation caused by class imbalance and are able to achieve increasing performances when incrementally acquiring more labels.
2.2
Related Work
2.2.1
Active Learning
Only DL-based AL algorithms are surveyed, where version-space approaches become trivial due to their expressive power (Ash et al. 2020). A fully-trained classifier is used to query for labels of samples from pool of unlabeled data Xy. Many AL algorithms can be characterized by how they valuate each candidate batch X' c Xy, where labels corresponding to the batch maximizing some scoring function v (X') are acquired. Among the earliest algorithms, the uncertainty- algorithms developed in (Wang& & Shang, 2014) score each sample using the classifier's 's margin 2 4ig fe ( 9) - fay; y²), or entropy (a (f(x.:)) 1)) where the softmax function. Because DNNs are often mis-calibrated and their softmax probabilities are not good proxy for uncertainty (Guo et al. 2017), a line of work (Kirsch al. 2019 use Bayesian neural networks (Gall & Ghahramani] 601 Gissin & Shalev-Shwartz (2019) computes the H--divergence (Ben- -Bvid ct 2010) resulting from hypothetical inclusions of unlabeled samples to the labeled set, and selects those that best aligns the distributions underlying labeled and unlabeled sets. [Sener & Savarese (2017) pose each query step as a core-set selection problem and finds an approximate solution. EGL (Huang et al. 2016) and BADGE (Ash et al. 2020) use the gradients of loss unlabeled samples as proxies for uncertainty. The former queries for samples that maximize the gradient norm, while the latter diversifies gradient embeddings using k-means++.
2.2.2 Semi-supervised Learning
Modern SSL algorithms utilize unlabeled samples and add consistency loss to act as regularization in addition to the standard supervision loss. FixMatch (Sohn et al.) (0200 is a state-of ofaee--f-the-rrr
algorithm that combines and simplifies a sequence of developed SSL methods (Lee) 2013) Laine & Aila, 2017 Tarvainen & Valpola| [201 Berttelot et al. 2019) by generating pseudo-labels with weakly- aaakleee samples. Kim et al. (2020) Lee et al. (2021) observe that pseudo-labels generated by related algorithms (Berthelot et al. 2019 Sohn et al. 2020 Berthelot et al. 2020) are severely AL,
imbalanced when the classifier is trained on imbalanced data, thereby degrading performance. it is impossible to ensure balanced classes in either the labeled unlabeled sets and the same problem persists. For our problem setting, we use FixMatc--DARP (Kim et al.) (020)) where pscudo-labela procesodddd such that their class distribution matches target distribution. Because for general purposes it is impractical to assume knowledge of class distribution underlying unlabeled samples, set this target as the uniform distribution.
3 Motivations and Method
3.1 Notations
A classifier's 's output layer (preceding softmax) is denoted as fe, and the gradients with respect to its parameters as Vo. We often drop the subscript and leave it otherwise for emphasis. For simplicity of exposition, we describe our notations assuming single class and note that this can casily be
3

---

re-written following (Arora et al. 2019a; Allen-Zhu et al., 2019 Du et al. 2019) for multi-class classification. Given .V samples
{ ......... 2N and parameters, the dimension of networks
gradient is listed as fe (X) Nxx The Gram matrix K, (X X²)) := V fo, (X) V fő, (X) computed using parameters O, obtained after optimization (c.g. SGD) steps is also known as the empirical NTK (Arora et al. 2019a).
3.2
Motivations
3.2.1
Uncertainty Embeddings
Motivated by the ubiquity of stochastic gradient descent (SGD) used to train deep neural networks, Huang et al. ( A et al. (2200) use gradient embeddings V C (8; I, y) to measure the uncertainty about a sample x using a proxy label ý. We adopt a similar view on gradients and use them to valuate unlabeled samples, except that our algorithm will make use of the network's gradients V ʃ which is related to the loss gradients V.. through the chain rule. However, while the arguments used in above references are mainly based on the idea that uncertain samples cause large gradients V., this is not necessarily true for the network's ss gradients fe. Instead, the gradients' directions are additionally used measure uncertainty.
network supervised on data including labeled sample 24 will be more-so certain on that sample than on an unlabeled sample Tu. and the product V fo, (21)² )" V fo, (I.,) being small indicates uncertainty about Tus and in turn that Iy should be queried for its label. We show, after presenting our algorithm in Sec. [3.3] that our selection criterion captures uncertainty
information by comparing the gradient's direction with a confident reference vector evaluated at a labeled instance.
3.2.2 Batch-mode Operation
Given a fixed labeling budget [//]] < B, a lower bound on the query size Q is determined by how often the classifier can query the label oracle or worker. When the worker is not to be disturbed, a large query size (e.g. Q = B) is necessary, and ideally an AL algorithm should attain higher performance when querying more often. To avoid excessive numbers of queries, one of the most important traits of an AL algorithm batch mode operation, valuating the collective importance of candidate batch instead of its marginal elements. Early DL-based AL algorithms were myopic v (2t) = >; vxxx), meaning that their valuation samples does not consider the collective value of candidate batches. For example, max- max-margin is myopic policy and queries redundant samples (Kissch et al., (219) when duplicates are present. Algorithms that operate in the batch setting prove eritical query size becomes large.
3.2.3 Loss Landscape and Classification Performance
Loss landscape has long been connected to generalization (classification) performance, one view being that critical points near flat minima more robust to distribution shifts occurring between train and test sets (He et al. 2019). Gradient steps in flat landscapes that do not take into account second order information for re-scaling inevitably take small steps, but it has been observed in (Athiwaratkun jet al. 2019) that SGD continues to take large steps when applied to losses used in SSL. Together these views suggest that an improved loss landscape for SSL would enhance generalization performance.
To this end, one of our considerations in designing an AL algorithm is to construct a training set so that the induced landscape exhibits properties positively correlated with generalization as discussed above. We show that addition to the utilization of uncertainty information from network's gradients and diversity enforcement, another view for our objective is to select data that ameliorates downstream training. Because our algorithm improves the conditioning of downstream optimization problem, we name it Neural Pre-Condee Fre-Conditioning (NPC).
3.3 Algorithm
Let Amin (X') be the minimum eigenvalue of the symmetric Gram matrix (,,, We propose to encode the uncertainty about samples X' through the network's 's gradients V fe, (X') used to compute the Gram matrix K,, and find the subset that solves
max C. ig
min
As (X,, UZz).
33)

---

Algorithm 1 Neural Pre-Conditioning (batch-mode solution to (3)
Inputs: Unlabeled pool Xy, acquisition size Q.
Output: New pool X to be labeled.
for i 1,... = O (Nu) do
x1 t Q unlabeled instances randomly sampled from Xy-
o(x11) Amin (x' U xx using the network's Gram matrix.
end for Return X <- arg max (v)
To understand how our algorithm makes use of the direction of gradients embed uncertainty information as argued in Sec. [32.1] consider the simple case of selecting one of two unlabeled samples Tus x' Let X { zu. J be the set containing these two and a labeled sample, [xxx)) f
and without loss of generality suppose V (x1) f
b with for all æ E X. Given potential labeled sets X1 = {1,, x.. and X₂ {=,,""), the minimum eigenvalues
normalized gradients [()(l =
and Aauin (X2) = 1 b. Therefore, NPC measures the model's 's uncertainty about a sample x,, by comparing its gradient direction (x((,) with more confident sample's fz1) as reference, ultimately returning sample whose gradient direction is further away from the reference's 's to avoid querying for a less informative sample.
(min(())
Next we address how the algorithm enforces diversity for batch-mode queries. Consider multisets X, i.e. X' can have duplicate elements: X * X' U {r) for any x E X. A dataset X with duplicate instances is called degenerate, equivalently any non-degenerate set X' has elements ||ær; - x, > 0 for every pair ش indexing samples in X. We show formally that NPC provably finds only non- degenerate solutions as long as such candidates exist. Proposition M alone resolves issues present in many AL algorithms that acquire identical samples on redundant datasets such as "repeated MNIST" (Kirsch et al., 2019).
Proposition (NPC finds non-degenerate solutions). Suppose & x = ((T) ) (I))) every Fy, By E X₁, U Ky. For any degenerate X, and non-degenerate X2 sets,
Amin (Kt X Amin (Xg U Kx)== 0.
Remark 1. Intuitively, the assumption v; * x = K(I;,,) F K(Iz.-) means that high dimensional vector (function's 's gradients) is one-to-one on the small and countable domain XG, U Xy. This is true least in the neighborhood of initialization for ReLU networks as long as not too many neurons are deactivated (Allen-Zhu et al. 2019) or for another class of networks Du et al. (2019)
Proof. The proof simple consequence of the rank-nullity theorem and positive definiteness. All eigenvalues computed over non-degenerate sets Xy U X non-zero since vectors of K:09 (Xr U U are linearly independent. Because K. is semi-positive definite and singular only when its row vectors are linearly dependent, LHS > O. RHS has duplicate elements in the multiset, and therefore at least two row vectors are linearly dependent. Consequently (x)) is singular, implying RHS=0.
One property that can be inferred from the above proposition is that NPC consolidates labeled data. Interestingly, existing AL algorithms do not explicitly use labeled data when querying labels. Because the labeled set at early acquisition steps may have been constructed using semi-random acquisition step, or its measurements of uncertainty may have been unreliable because the network had been trained such few labels, it is important that the label set is also re-evaluated against potential candidates so that label cost is not wasted on nearly-redundee samples' labels.
3.4 Computational Considerations
Computing the Gram matrix over given candidate X, requires summing each layer's Gram matrix as Kr+ L x,(1). Because each Gram matrix is semi semi-positive definite, its minimum eigenvalue
bounded below by the last layer's Amin (x:!.) 2 Auni (K.)) Therefore, we use only the last layer's gradients to compute Kc,, where the resulting objective serves lower bound to Eq. 3
5

---

Furthermore we replace each block-element whose dimension is the number of classes with its trace to save memory.
When solving the inner-ninimization, the kernel's value over labeled samples can be stored and re-used for every candidate batch X,, We compute the minimum eigenvalue using the robust and efficient locally optimal block preconditioned conjugate gradient method (Stathopoulos & Wu 2002). However, the search space of Eq. 33 is combinatorial the pool size and query size. Therefore we approximate the solution to Eq. 3 by sampling m = O (Nv) subsets uniformly at random to match the runtime of myopic algorithms. where Ny the unlabeled set's size. By the mecluion--xcclusoo principle, the top rNy batches, with E [0. 1]. are included in the search space with probability (1 r)mh Taking m 1000 as an example, the randomized search returns a batch within the
99- 99-percentile with probability 2 1 - 4- 10
4 Discussion
4.1 A Better Optimization Plateau for Generalization
As motivated earlier, flattening out the landscape has positive implications towards generalization. Here we prove that the landscape induced by labels acquired using NPC allows larger step sizes for convergence, which in turn leads to faster convergence towards flat landscapes. At least for shallow 2-layer networks, increasing the convergence rate also reduces the generalization error (Arora et al.. 2019b).
For only this section, assume non-degenerate training set: || 11--,) z1yl > 0 for each + j. Theorem 1. At each gradient descent iteration I with step size v O (Ko)), the MSE loss L. of inoptaly-nnitillized, sufficiently wide ReLU network decays as
L++1 S (1 - O (1/mmin (Kc))) Lr
(5)
with high probability over initialization.
Note that NTK VTK-analyses typically express the training dynamics as a function of Kg, Koxs or the true NTK. Although this can be done with additional perturbation analysis, we leave it this form since we are concerned with the eigenvalue of the network's Gram matrix.
Two remarks follow. First, the above shows that the set of step-sizes under which gradient descent converges is determined by Amin (Ko)). The kernel K2 essentially stays constant throughout training for a sufficiently wide network and is fixed as Ko for simplicity. Therefore, gradient descent can take large step-sizes and still converge when the labeled dataset is constructed using NPC. By maximizing Amin (.oc), where Ko. is the Gram matrix of a classifier trained until cear-convergence, NPC improves both training and generalization. Second is the withstanding of Thm. T when the the computation of K. is reduced by using the last layer's Gram matrix. We described in Sec. th4]that our NPC algorithm solves Eq. (3) by replacing K., in Amin (Kc,) with the last layer's Gram matrix. As shown, training and generalization benefits that come from solving Eq. (3) still hold when using the network's last layer to compute the kernel.
4.2 Benefits of Randomized Search
The alternation between querying for labels and training can be interpreted feedback system, which illustrates the exploration vs. exploitation effect of randomization used to solve Eq. (3) and complements the view that the network's uncertainty about samples is minimized with more labels. state described by trained parameters and training set ZL,Ky is used by a policy, which seleets X and acquires (observes) Dit At the first acquisition step, the network's gradients unreliable measures of uncertainty embeddings due to a lack of labeled samples. Subsequent states are then updated by propagating newly acquired labels to train the network so that gradient embeddings better represent uncertainty about samples. At early acquisition stages, the randomized search therefore encourages the acquisition policy to explore instead of relying excessively on its belief. The search space size decreases with more acquisition steps and therefore the policy progressively exploits its belief.
Our algorithm's is effect on generalization error can also be understood by studying the infinite- witth regime, where we view randomization to act as regularization method considering that we use finite-

---

Table 1: CIFAR-I0 (Qo 10, Q 20); Average accuracy (%) + standard deviation. Initial model achieved 57.64% accuracy.
# Labels
30
50
70
Algorithm
Passive
78.08 + 5.48
91.82 + 2.30
31.00
Margin
87.36 5.01
90.85 + 3.64
90.85
ALBL BADGE
80.61 12.5
89.62 6.66
94.45
80.60 + 4.46
86.43 + 1.22
NPC
85.09 + 9.61
94.63 + 0.07
94.85 + 0.02
width networks. A finite-width network's prediction is approximately kernel ridgeless regression Arora et al. 2019a). Bordelon et al. (202T) showed that for kernel ridgeless regression, training point reduces generalization eгтоr at modes corresponding to larger eigenvalues. Our objective in Eq. (3) selects training set that maximizes the minimum eigenvalue. and therefore enhances data efficiency in the sense that generalization eπror is affected at as many modes as possible. However, finite-width ConvNets are generally better classifiers (Arora et 2020, Lee al. 2020) which were therefore used to query for labels. The eigen-spectrum of a finite width network's Gram matrix not identical the NTK and solving the objective exactly may not directly translate more generalization modes as for infinite width networks.
Experiments
5.1
Implementation Details
We adopt all SSL-related configurations from (Oliver et al. (0188) and use the WRN-28-2 architecture (Zagorykko & Komodakis, 2016) for all experiments. At the first acquisition step, we randomly sampled 1 image per class and used the model that attained median performance across 5 trials. Subsequent acquisitions were performed with query size Q CIFAR-100. All performances are averaged over 3 trials. Following most AL setups, we train classifiers from scratch after each acquisition step. Training from scratch better assesses the value of labels as it mitigates the possibility of vicious cycles where models trained sub-optimally in previous acquisition steps have no hope of improving despite superb data.
for CIFAR-10 and Q 200 for
As discussed earlier, we assume a- e-priori information class distribution underlying unlabeled data. Instead of estimating the underlying class distribution done by Kim et al. (2020) which may be detrimental given few labels, we simply take the target pseudo-label distribution to be uniform and perform pseudo-label refinement accordingly.
5.2 Baseline A Algorithms
The proposed NPC algorithm is compared with passive learning where labels are queried uniformly at random, margin (Roth & Small, (006). active learning by learning (ALBL, Hsu & Lin (2015)) comprising least confidence and Coreset (Sener & Savarese 2017). and BADGE. Margin evaluates the classifier's 's margin and selects Q samples whose margin is lowest. ALBL employs a two-armed adversarial bandit algorithm adapt to the better of least confidence arg min, f (a;)) and Coreset. BADGE was described earlier, and acquires samples by applying k-means++ gradient embeddings. Entropy was also considered but excluded because of its low performance on some experiments.
5.3 Performance
Tables D and 2 show the accuracy of AL algorithms when trained on CIFAR- 10 and CIFAR- 100, respectively. NPC outperforms other label acquisition schemes on nearly all dataset sizes and is least competitive on the few others. Although BADGE is state-of-the-art on AL benchmarks, we observe older algorithms performing better when evaluated by SSL accuracy. This reveals how existing AI. algorithms have been evaluated by their efficiency of sample acquisitions rather than label complexity.
7

---

Table 2: CIFAR-106 (Qu 100, Q 200): Average accuracy (%)
standard deviation. Initial
model achieved 21.29 21.29% accuracy.
# Labels
300
500
700
900
Algorithm
Passive
37.98 + 1.89
47.11 :: 1.41
52.69
1.16
57.97 + 1.43
Margin
37.41 + 1.22
#.721
52.53
0.75
57.03 0.39
ALBL
39.05 + 0.62
4..8
04.2311.7
56.65 0.86
BADGE
24.55 + 1.13
2
08.03
NPC
40.92 + 1.65 48.16 0.77
5.476
58.58 = 0.52
To complement performances, Fig. illustrates the similarity between algorithms the intersection over union (IoU) of label indices as more labels are collected on CIFAR- 1000 At any given label size Nr. an algorithm's is label set is the union of labels acquired different trials. Margin and least-confidence both rely heavily on the classifier's predictions, and labels acquired at different trials overlap significantly. As shown, ALBL and Margin are similar in how labels acquired, which describes that using a classifier's ' least confidence is similar to acquiring based on its margin. On the other hand, other pairs of algorithms have very small overlaps, demonstrating that their acquisition criteria are drastically different.
45%
25%
20%
45%
Muggn
Veige
Maigh
Noigh
Figure 1: Similarity between AL algorithms: Intersection union (IoU%) of labels commonly acquired by algorithms.
5.4 Reducing Inquiry Frequency
The above experiments aim maximize accuracy with budget constraints on the number of labels. Certain applications may additionally require that the number of inquiries is minimized to reduce the frequency of interaction between classifier and annotator. is clear that RANDOM remains unaffected by the number of inquiries, and it desirable that AL algorithms maintain high performance when fewer inquiries possible.
As observed Tab. [ NPC achieves very high performance at N₂ 50. accommodate limit on the number of inquiries, we experiment with how NPC and BADGE, selected based on their similarity, are affected on what we call single and zero shot AL., both referring single query given model trained very few labels (N, = 10) and randomly initialized (N, = 0) model, respectively. As shown Tab. 3 NPC excels in both zero and single shot settings where an imperfect classifier used to valuate samples. Interestingly, NPC remains nearly unaffected by which model is used to query for samples in zero or single shot queries. In contrast, BADGE is detrimentally affected by its over-reliance gradient embeddings single-shot AL and rather performs better in zero-shot queries when gradients are randomly initialized.
A few questions arise from this observation. The fact that BADGE performs worse single-shot AL with larger query size highlights that gradients alone may not be informative features valuating samples assumed. NPC also uses gradients as features for valuating samples, but its robust performance with respect number queries can be attributed our conclusion from theoretical analysis where problem conditioning is directly affected.

---

Table 3: Zero-shot and Single-shot AL CIFAR 10 using Q {30, 50). where zero-shot refers to
acquisition using randomly initialized model and single-shot to a model trained on label per class.
Zero Shot
Single Shot
# Labels
40
60
40
60
BADGE
92.13 3.24
94.42
0.41
86.70 + 5.42
70.28 + 13.22
NPC 93.14 + 1.42
93.16 2.34
92.26 = 3.26
93.76 + 0.58
It's surprising how both BADGE and NPC perform extremely well on zero-shot AL, where a randomly initialized model decides which labels are most valuable. For comparison, FixMatch on balanced data without DARP reportedly achieves 86. 19%, comparable BADGE on single-shot but under- performing both BADGE and NPC on zero-shot. To explain this phenomenon, it is instructive to view randomly initialized networks in their asymptotic limits.
At first glance it may appear that NPC with a randomly initialized network should not work well. However, wide networks at initialization approximate their infinite-width NTK (Arora al. (019a).
As mentioned earlier, fully-trained wide networks are essentially ridge regression Dridge (Xrest)
I. (Itest, X) XC-1 (X,X) X) y. and zero-shot NPC translates to construction the above kernel on which ridge regression will be performed. A training point influences the generalization of kernel regression more for modes corresponding to large eigenvalues (Bordelon et al. (02I), which is maximized by NPC. In summary, NPC using a randomly initialized network selects samples to maximize generalization performance as predicted by approximate kernel regression through the NTK spectrum.
6
Conclusion
This work motivated downstream SSL performance as a benchmark to evaluate AL algorithms. We then described motivations recurrent in previous works and proposed an AL algorithm that addresses these concerns. The proposed NPC algorithm captures uncertainty through the model's 's gradients, operates the batch-mode setting, and improves the landscape of downstream SSL through data acquisition as measured by properties related to generalization. Experiments re-evaluating state-of- the-art AL algorithms with respect to downstream SSL performance, which better measures label complexity, demonstrate that NPC outperforms other AL algorithms on most dataset sizes and tasks.
NPC enjoys several properties that aren't 't present other AL algorithms is at least not obvious. First, NPC explicitly consolidates existing labeled data when measuring the value of labeling un- labeled candidates. Moreover, NPC is batch AL algorithm that provably selects distinct samples. The proposed algorithm is also interesting in that it is a dernel-basee sampling scheme. Kernels are excellent models of data distributions, and NPC's construction of kernel using DL opens new venues for AL.
few limitations and future works are described. Our experiments rely on modern SSL algorithms to evaluate AL algorithms. Although current SSL algorithms achieve extremely high accuracy on vision tasks, they suffer from algorithmic instability where given the same model and dataset, their performances vary more-so than supervised learning. Ideally, all algorithms should achieve higher accuracy in line with the "more data is better" principle. Because performance deterred by class imbalance is resolved using pseudo label refinements, we believe experimental evaluations will benefit most from algorithmic stability. Further, SSL training demands much more computation than SL counterparts, and consequently an exhaustive evaluation of various AL algorithms is prohibitive. Experimental protocols that reduce computations evaluating algorithms yet are fair would expedite research. Lastly, we treat AL and SSL phases independently for our purpose. An interesting direction to pursue would be to design AL and SSL schemes that adapt to each other. For example, our theoretical analysis and NPC's valuation gives upper bound on possible learning rates for downstream training. By designing learning schedules to adapt to the set of admissable step sizes, downstream training may be better stabilized and achieve higher performance.

---

Acknowledgments and Disclosure of Funding
We thank Professor R. Srikant for helpful discussions relating to Neural Tangent Kernels.
References
Allen-Zhu, Z., Li, Y., and Song. Z. A convergence theory for deep learning via over-paramettrrizaton. arXiv preprint arXiv: urX1v:1811.0392, 2019.
Arora, S., Du, S., Hu, W., Li, Z., Salakhutdinov, R., and Wang, R. On exact computation with an infinitely wide neural net. CoRR, abs/1904.11955. 2019a.
Arora, S., Du, S. S., Hu, W., Li, Z., and Wang, R. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. International Conference on Machine Learning, 2019b.
Arora, S., Du, S. S., Li, Z.. Salakhutdinov, R., Wang, R., and Yu, D. Harnessing the power of infinitely wide deep nets on small-data tasks. In International Conference on Learning Representations, 2020.
Ash, J. T., Zhang, C., Krishnamurthy, A., Langford, J., and Agarwal, A. Deep batch active learning by diverse, uncertain gradient lower bounds. In International Conference on Learning Representations. 2020.
Athiwaratkun, B., Finzi, M., Izmailov, P., and Wilson, A. G. There are many consistent explanations of unlabeled data: Why you should average. International Conference on Learning Representations, 2019.
Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F,, and Vaughan, J. A theory of learning from different domains. Machine Learning, 79:151-175, 2010.
Berthelot, D., Carlini, N., Goodfellow, I., Papernot, N., Oliver, A., and Raffel, C. Mixmatch: A holistic approach to semi-supervised learning. arXiv preprint arXiv: (905.02200502249 2019.
Berthelot, D., Carlini, N., Cubuk, E. D., Kurakin, A., Sohn, K., Zhang, H., and Raffel, C. Remixmatch: Semi-supervised learning with distribution matching and augmentation anchoring. In International Conference on Learning Representations, 2020.
Bordelon, B., Canatar, A., and Pehlevan, C. Spectrum dependent learning curves in kernel regression and wide neural networks, 2021.
Du, S., Lee, J., Li, H., Wang, L., and Zhai, X. Gradient descent finds global minima of deep neural networks. volume 97 of Proceedings of Machine Learning Research, pp. 1675-1685, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Gal, Y. and Ghahramani, Z. Dropout bayesian approximation: Representing model uncertainty in deep learning. In Balcan, M. F. and Weinberger, K. Q. (eds.), Proceedings of The 33rd International Conference Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1050-1059, New York, New York, USA, 20-22 Jun 2016. PMLR.
Gissin, D. and Shalev-Shwartz, S. Discriminative active learning. arXiv preprint arXiv:1907.06347, 2019.
Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML 17, pp. 1321-1330. Jog,. 2017.
Hanneke, S. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th International Conference on Machine Learning, ICML '07, pp. 353-360, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 978 9781599937933.
He, H., Huang, G., and Yuan, Y. Asymmetric valleys: Beyond sharp and flat local minima. In Wallach, H., Larochelle, H., Beygelzimer, A., d' d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32, pp. 2553-2564, Curran Associates, Inc., 2019.
10

---

Hsu, W.-N. and Lin, H.-T. Active learning by learning. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). Feb. 2015.
Huang, J., Child, R., Rao, V., Liu, H., Satheesh, S., and Coates, A. Active learning for speech recognition: the power of gradients. arXiv preprint, 12 2016.
Kim, J., Hur, Y., Park, S., Yang, E., Hwang, S. J., and Shin, J. Distribution aligning refinery of pseudo-label for imbalanced semi-supervised learning. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F, and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 14567-14579. Curran Associates, Inc., 2020.
Kirsch, A., van Amersfoort, J., and Gal, Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In Wallach, H.,, Larochelle, H., Beygelzimer, A., d'Alchéé-Biet F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32, pp. 7026-7037. Curran Associates, Inc., 2019.
Laine, S. and Aila, T. Temporal ensembling for cemi-supervised learning. ICLR (Poster). OpenReview.net, 2017.
Lee, D.-H. Pseudo-label : The simple and efficient semi-supervised learning method for deep neural networks. ICML 2013 Workshop Challenges in Representation Learning (WREPL), 07 2013.
Lee, H., Shin, S., and Kim, H. ABC: Auxiliary balanced classifier for class-imbalanced semi- supervised learning- In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, W. (eds.),
Advances in Neural Information Processing Systems, 2021.
Lee, J., Schoenholz, S. S., Pennington, J., Adlam, B., Xiao, L., Novak, R., and Sohl-Dickstein, J. Finite versus infinite neural networks: An empirical study. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS' 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Oliver, A., Odena, A., Raffel, C. A., Cubuk, E. D., and Goodfellow, I. Realistic evaluation of deep semi-supervised learning algorithms. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa- Basa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31, pp. 3235-3246. Curran Associates, Inc., 2018
Roth, D. and Small, K. Margin- based active learning for structured output spaces. In Fürnkranz, J., Scheffer, T., and Spiliopoulou, M. (eds.), Machine Learning: ECML 2006, pp. 413-424, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
Sener, O. and Savarese, S. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv: 7708.00000 00489, 2017.
Sohn, K., Berthelot, D., Li, C.-I.,, Zhang. Z., Carlini, N., Cubuk, E. D., Kurakin, A., Zhang, H., and Raffel, Fixmatch: Simplifying supervipd learning with consistency and confidence. arXiv preprint arXiv:2001.07683 2020.
Song, S., Berthelot, D., and Rostamizadeh, A. Combining mixmatch and active learning for better accuracy with fewer labels. arXiv preprint arXiv: 2019.
Stathopoulos, A. and Wu, K. A block orthogonalization procedure with constant synchronization requirements. SIAM Journal on Scientific Computing. 2366):2165-2182, 2002.
Tarvainen, A. and Valpola, H. Mean teachers are better role models: aieerae-verrged consistency targets improve semi-supervised deep learning results. In Guyon, I., Luxburg, V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30, pp. 1195-1204. Curran Associates, Inc., 2017.
Wang, D. and Shang, Y. A new active labeling method for deep learning. In 2014 International joint conference on neural networks (IJCNN), pp. 112-119. IEEE, 2014.
Wang, K., Zhang, D., Li. Y., Zhang, R., and Lin, Cost-effective active learning for deep image classification. IEEE Transactions on Circuits and Systems for Video Technology. 27(12):2591-2666 2016.
Zagoruyko, S. and Komodakis, N. Wide residual networks. In BMVC, 2016.
11

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [No] We defer the precise arguments to the Appendix. The theorem serves as an answer to our motivations, and we believe the precise assumptions deter from the main message.
(b) Did you include complete proofs of all theoretical results? [Yes] Included in Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] Computational requirements follow standard semi-supervised learning settings.
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you eite the creators? [Yes]]
(b) Did you mention the license of the assets? [No] Data and base code used for experi-
ments are described.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "u9XlWOpOGOh", "reviewer": "Reviewer_1Ma5", "summary": "This paper focuses on the active learning (AL) paradigm to reduce the label complexity compared to typical deep learning methods and proposes to capitalize on the semi-supervised learning (SSL) context instead of the typical supervised learning (SL) one, to be combined with AL. To that end, the authors advocate a neural pre-conditioning (NPC) algorithm  that relies on neural tangent kernels (NTKs) leveraging the minimum eigenvalue of the Gram matrix induced by NTKs. Empirical results demonstrate that merging NPC with some well-motivated SSL approaches can lead to improved prediction performance utilizing only few labeled data.\n", "questions": "- In line 25 in the sentence “Given images X and a labeling budget B, what’s the maximum performance that can be achieved?”. Where does the performance refer to? Does it refer to a classification task (such as object categorization) or regression (or both)? \n- In lines 29-33, the sentence “SL fails to extricate…newly-acquired labels“ is not clear. Does it just mean that SL does not leverage $\\mathcal{Z}_U$ during training?\n-  In lines 55-56, in the sentence “Because of the difference..”, where does the “difference” refer to?\n-  In line 129, in the sentence “In AL, it is impossible to know acquire labels while ensuring” what is the main verb (know or acquire)? Is it maybe to know acquired labels?\n-  In lines  156-158, the sentence “We show after presenting our algorithm in Sec. 3.3 that our selection criterion does indeed select based on the gradient’s direction which captures uncertainty information, which…” is incomplete and unclear. What is selected? \n-  I believe that in Eq. 1 there is a typo. Instead of $\\mathcal{Y}^* \\subset \\mathcal{X}_U$ is it maybe $\\mathcal{Y}^* \\subset \\mathcal{Y}_U$? \n-  In lines 34-35, it is mentioned that “Performance gains as a SL algorithm incrementally acquires labels remain minor relative to passive learning (PL).” This is not true in general. There exist AL-SL based  methods with well-documented merits compared to passive approaches; see e.g [1], [2]. \n-  In line 35, it is mentioned that “This may be attributed to the large numbers of labels required to attain meaningful  accuracy for SL…”. However, this does not always hold; see e.g [1], [2].\n-  In lines 38-39, it is mentioned that “While in principle more data should always be better…”. However, this does not always hold especially when the data are noisy (or redundant).\n \nSome examples of more minor issues are listed below\n\n- In line 5, instead of “Although unlabeled data is readily…”, it should be “Although unlabeled data are readily…”.\n- In line 27, instead of “have been evaluated by measuring downstream supervised…” it should be “have been evaluated by measuring the downstream supervised”. \n- In line 28, instead of “but we argue downstream semi-supervised learning (SSL) performance...” it should be “but we argue that the downstream semi-supervised learning (SSL) performance...”.\n-  In line 69, the verb “have” appears twice. \n-  In line 114, instead of “computes” it should be “compute”.\n\n I strongly suggest that the authors go over the paper carefully and correct the aforementioned and other similar grammatical/syntax errors. \n\n[1] Kapoor, Ashish, Kristen Grauman, Raquel Urtasun, and Trevor Darrell. \"Active learning with gaussian processes for object categorization.\" In 2007 IEEE 11th international conference on computer vision, pp. 1-8. IEEE, 2007.\n\n[2] Pasolli, Edoardo, and Farid Melgani. \"Gaussian process regression within an active learning scheme.\" In 2011 IEEE International Geoscience and Remote Sensing Symposium, pp. 3574-3577. IEEE, 2011.\n", "limitations": "The presentation of the limitations is good in general. Some additional concerns of mine are listed above.", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS \n\n- The proposed framework seems to work well in practice. \n- The literature review is good.\n\nWEAKNESSES\n\n- The writing and presentation of the paper admit further improvements. There are many parts of the paper that are hard to follow (see the Questions section below for some examples).\n- The novelty of the paper is somewhat limited. The SSL methods used are well known and the use of the Gram matrix (and its properties) in NTKs has been explored in the literature. In addition, besides the empirical performance, the contributions of the advocated approach need to be highlighted more clearly. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bCIpeGmQNbf", "reviewer": "Reviewer_yqNP", "summary": "This submission proposes the neural pre-conditioning (NPC) algorithm to leverage the unlabelled data using semi-supervised learning and acquire the valuable data that could be labelled carefully active learning strategy. Furthermore, this work mentioned that traditional active learning methods are typically evaluated with the supervised learning method, which cannot reflect how much the trained model gains the performance from newly acquired labels. Instead, they argue that semi-supervised learning can be a benchmark method to evaluate the Active learning downstream task. The authors state how the NPC algorithm uses the direction of gradients to select the uncertainty samples and prove that the batch-mode operation can increase the diversity of the data selection. They extend the experiments on two datasets with different query sizes and the number of labelled data, comparing the NPC against the other four state-of-the-art active learning methods, which shows the NPC achieves exceptionally high accuracy. In the end, they concluded this work and discussed the limitations and future study directions. ", "questions": "1. What’s the performance of showing in Fig.1? \n2. In the implementation part (the 288th  row), how did you randomly sample one image per class? OR that is the preprocess of selecting the labeled training data? \n3. The augment of “SL fails to extricate performance gains from newly acquired labels from the influence of newly acquired samples. In contrast, SSL trains a model on Z and the only difference in datasets used for training is the label, and performance improvements between rounds s and s + 1 reveal gains from newly acquired labels” is the key point in this paper. Intuitively, the data and label act simultaneously to improve the model's performance. Why did you mention that semi-supervised learning is better for evaluating the effect of the newly acquired labels? Could you please give more explanation?\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The results have significant improvement compared to the previous work, achieving state-of-the-art results. \n2. Quality: This work reads as a complete paper that has complete sections and clear formatting. There are extended comparative experiments to evaluate the proposed method's effectiveness. \n\nWeaknesses\n1. The notations and some presentations are unclear. For example, in eq.1, χ*, Y*and Y_U; in Table 1. What is the Q_0; in 277th row, -u. \n2. Clarity: The presentation is not clear in some parts, like in the introduction part, you mentioned that simply replacing the SL with SSL would introduce a new problem because the class imbalanced issue can deteriorate the SSL performance significantly. Although here you added the reference, I think that supplying more details that explain why this issue induces the SSL performance so significant is necessary since the imbalance issue would also degrade the SL. \n3. Clarity: For the algorithm section, I consider giving more proof in detail is better. The analysis of the two main contributions on the algorithm, gradients direction and diversity, is not very clear. \n4. Originality: this work builds upon prior solutions to improve the performance of active learning using semi-supervised learning in the downstream tasks. However, the novelty is limited. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "R7JxRJXSx1", "reviewer": "Reviewer_96bx", "summary": "This work proposes a batch mode active learning method for active learning. The active sampling criterion mainly leverages the gradient of the currently trained model with respect to both labeled and unlabeled data to sample the informative data batch for humans to label. A theorem is presented to show that if the proposed sampling strategy is ideally implemented, the model loss decay rate is subject to linear.", "questions": "I am interested in how the label information omits in the loss decay bound in theorem1. Can you explain how the inequality in appendix line 16 is derived? I think that is where the label information disappeared in the loss decay.", "limitations": "None", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThe methodology section is well organized; the proposed method is clearly described and explained with the underlying motivation, making it easy to read and understand.\nWeakness:\n1. The proposed method can be seen as a variation of the gradient embedding-based active learning while the main difference is the gradient of the model output, rather than the loss function, is used to construct the active sampling function. However, I am not convinced that the uncertainty can be fully captured without considering the potential labels an unlabeled data instance could have during the sampling. The paper mentioned in multiple places that the gradient of f(x) contains the uncertainty of x. But the paper does not spare any effort to prove/demonstrate that. In fact, I believe the label-instance pair is the menial unit for informative measurement in active learning. Two identical data points with different labels(provided by a human annotator) could have significantly different empacts on the model training. But the proposed sampling method treats them as the same. I do not believe the proposed method can perform uncertainty sampling as claimed in the paper.\n\n2. The batch mode sampling is impractical to me because eq3 suggests that the optimal batch needs to be searched within a solution space of combination(N, Q) where N is the pool size and Q is the batch size. For a practical active learning problem, N can easily exceed 10000, and Q is typically set from 50~500, making combination(N, Q) unreachable. The proposed batch solution in algorithm 1 only randomly tests m batches out of combination(N, Q)  solutions. It is almost impossible to have the optimal batch in that m test batches. No need to mention that each batch testing has O((T+Q)^3) complexity given the T is the current labeled data. \n\n3. The bound of the decay rate proposed in theorem1 is based on the optimal batches. I don’t think it will hold for most of the time since the actual batch mode sampling could not guarantee finding the optimal batch. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GM-T51-qjV", "reviewer": "Reviewer_h4Gx", "summary": "Semi-supervised learning and activa learning are two representative learning paradigms to learn with incomplete supervised data. The difference lies in that active learning relies on human knowledge. This paper argues that the enhancements of SSL performance could be used to evaluate active learning methods to measure their label efficiency. This is an interesting idea. The proposed method is based on a neural tangent kernel analysis, which evaluates unlabeled data based on how they would contribute to updating the training set's inclusion. This is technically sound. The experiments also demonstrate the effectiveness of the proposal.", "questions": "1) Can the proposal be applied to more realistic SSL scenarios? For example, recently there have been many studies about open-set SSL and class-imbalanced SSL. Can the proposal be applied with these methods?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) The paper gives a new perspective on semi-supervised learning and active learning, and shows that the enhancements in SSL performance could be used to evaluate active learning methods. This is a new idea and could inspire subsequent researchers.\n\n2) The proposed method is technically sound.\n\nWeakness\n\n1. The experiments could be further improved. For example, conduct experiments in more settings, such as imbalanced semi-supervised learning and open-set semi-supervised learning. Moreover, it would be better to report performance on more related methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept