Better Optimization can Reduce Sample Complexity: Active Semi-Supervised Learning via Convergence Rate Control
Authors: Seo Taek Kong
Soomin Jeon
Jaewon Lee
Hong-Seok Lee
Kyu-Hwan Jung
Venue:  (2021)
Keywords: Active Learning
Semi-Supervised Learning
Neural Tangent Kernel
Deep Learning

Abstract: Reducing the sample complexity associated with deep learning (DL) remains one of the most important problems in both theory and practice since its advent. Semi-supervised learning (SSL) tackles this task by leveraging unlabeled instances which are usually more accessible than their labeled counterparts. Active learning (AL) directly seeks to reduce the sample complexity by training a classification network and querying unlabeled instances to be annotated by a human-in-the-loop. Under relatively strict settings, it has been shown that both SSL and AL can theoretically achieve the same performance of fully-supervised learning (SL) using far less labeled samples. While empirical works have shown that SSL can attain this benefit in practice, DL-based AL algorithms have yet to show their success to the extent achieved by SSL. Given the accessible pool of unlabeled instances in pool-based AL, we argue that the annotation efficiency brought by AL algorithms that seek diversity on labeled samples can be improved upon when using SSL as the training scheme. Equipped with a few theoretical insights, we designed an AL algorithm that rather focuses on controlling the convergence rate of a classification network by actively querying instances to improve the rate of convergence upon inclusion to the labeled set. We name this AL scheme convergence rate control (CRC), and our experiments show that a deep neural network trained using a combination of CRC and a recently proposed SSL algorithm can quickly achieve high performance using far less labeled samples than SL. In contrast to a few works combining independently developed AL and SSL (ASSL) algorithms, our method is a natural fit to ASSL, and we hope our work can catalyze research combining AL and SSL as opposed to an exclusion of either.

Under review as a conference paper at ICLR 2021
BETTER OPTIMIZATION CAN REDUCE SAMPLE COM- PLEXITY: ACTIVE SEMI-SUPERVISED LEARNING VIA CONVERGENCE RATE CONTROL
Anonymous authors Paper under double-bling review
ABSTRACT
Reducing the sample complexity associated with deep learning (DL) remains one of the most important problems both theory and practice since its advent. Semi- supervised learning (SSL) tackles this task by leveraging unlabeled instances which are usually more accessible than their labeled counterparts. Active learning (AL) directly seeks to reduce the sample complexity by training classification network and querying unlabeled instances to be annotated by a human-in-thee-oowe relatively strict settings, it has been shown that both SSL and AL can theoretically achieve the same performance of fully-superve labeled samples. While empirical works have shown that SSL can attain this benefit in practice, DL.-based AL. algorithms have yet to show their success to the extent achieved by SSL. Given the accessible pool of unlabeled instances pool-based AL, we argue that the annotation efficiency brought by AL algorithms that seek diversity on labeled samples can be improved upon when using SSL as the training scheme. Equipped with a few theoretical insights, we designed an AL algorithm that rather focuses on controlling the convergence rate of a classification network by actively querying instances to improve the rate of convergence upon inclusion to the labeled set. We name this AL scheme convergence rate control (CRC), and our experiments show that deep neural network trained using combination CRC and a recently proposed SSL algorithm can quickly achieve high performance using far less labeled samples than SI. In contrast few works combining independently developed AL and SSL (ASSL) algorithms, our method is natural fit to ASSL, and hope our work can catalyze research combining AL and SSL as opposed to an exclusion of either.
Under
learning (SL) using far less
INTRODUCTION
The data-hungry nature of supervised deep learning (DL) algorithms has spurred interest in active learning (AL), where model can interact with dedicated annotator and request unlabeled instances to be labeled. In the pool-based AL setting, a model initially has access to a set of unlabeled samples and can query instances which need be labeled for training. Under certain conditions on the task, AL can provably achieve up to exponential improvement in sample complexity and thus has great potential for reducing the number of labeled instances required to achieve high accuracy. This is especially important when the annotation task is extremely costly, for example, in medical imaging where only spenill-seeializedd experts can diagnose subject's condition.
Active learning algorithms have been extensively explored, with various formulations including uncertainty- sampling (Wang & Shang, 2014), aligning the labeled and unlabeled distributions (Gissin & Shalev-Shward 2019) with connections to domain adaptation (Ben-David et al.) 2010). and coreset (Sener & Savarese 2018). Furthermore, there is no standard method in modeling a deep neural network's 's (DNN) uncertainty, and uncertainty-basee AL has its own variants ranging from utilizing Bayesian networks (Kirsch et al., (2019) to using a model's 's predictive confidence (Wang & Shang 2014). This ambiguous characterization of how much information sample's 's label carries also motivated AL algorithms based on maximizing the expected change of a classification model
(Huang et al. 2016: Ash et al. 2020).

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Active Semi-Supervised Learning
for each query iteration
..., do
Train a classifier fo using some SSL algorithm on (X2, Ny) until convergence.
Retrieve unlabeled samples X C Xy using Alg. 2 and obtain their labels.
Update labeled and unlabeled pools X2= + Xy U Ru Xu = No end for
While AL comes with optimistic potentials, most algorithms outperform random sampling (passive learning) by only a small margin, with follow-up works (Gissin & Shalev-Shwartz 2019 [Sener Savarese 2018 Ducoffe & Precioso 2018) reporting worse performance of certain AL algo- rithms than random sampling due to their dependency on specific model architectures or dataset characteristics. Furthermore, the performance of AL algorithms are usually reported by training a model using supervised learning (SL) on the queried labeled data despite the availability of unlabeled data in pool-based AL. Semm--supervieed learning (SSL) has recently shown impressive performance with small number of labeled instances, and its most premature variant known as
[Lee) 2013) has been combined with AL. algorithms (Wang et al., 2017). One recent work (Song et al. 2019) uses rather modern SSL algorithm (Berthelot et al.) 2019) and shows the strength of combining AL with SSL which we name ASSL. However, their AL algorithm is not designed specifically considering the ASSL setting.
In this work, we propose a novel query strategy which naturally blends in with SSL, and show that our AL algorithm can rapidly achieve the high performance of fully-supervised algorithms using fewer labeled data. Our algorithm is inspired by recent developments in DNN theory, namely the neural tangent kernel (NTK) (Jacot et al. 2018). Experimental comparisons with diversity-secking strategies and an algorithm with an objective similar to ours demonstrate how labeling instances based on our objective helps SSL attain high performance in a sample-efficient manner.
2 BACKGROUND THBORY
2.1 SAMPLE EFFICIENCIES OF ACTIVE LEARNING AND SEMI-SUPERVISED LEARNING
Here we informally describe some theoretical results describing the superiority of AL to passive learning and SSL to SL in terms of labeled sample complexity, that is, the number of labeled instances that can be used to attain e-classification error. Because pool-based AL subsumes unlabeled instances, it makes much more sense to perform SSL on the readily available unlabeled instances when training a classification network between each query iteration (Alg. T This section describes how AL and SSL algorithms can consider different objectives to attain higher accuracy the ASSL setting.
It is well known that SL can find an e-optimal classifier from a sufficiently rich class of hypotheses (e.g. classifiers which can be realized by deep neural networks) using θ (2) i.i.d samples for the
separable case and Ô (1) in the agnostic case (Massart Nédélec 2006 Vapnik & Izmailov 2015
In contrast, actively adding instances to the (labeled) tramiig set can sometmes improve the sample complexity sub-exponentially from (1/cc) to (polyy log 1/c) (Balcan et al., 2010). When unlabeled instances are drawn i.i.d., Balcan & Urner (2016) showed how labeling samples selected via binary search over ((1/e) unlabeled instances can achieve exponential improvement over passive learning.
Göpfert et al. (2019) constructed few examples which show how an SSL algorithm can use unlabeled instances to significantly improve the labeled sample complexity for a rather restricted class of data distributions. A corollary of one such example is that using Oloo 1/c) labeled samples and O(1/c²) unlabeled samples can be used to obtain e-error. Considering target error & 6% achieved by fully-supervised learning in CIFARIO using O(1/e) R 50, 000 labeled samples, a training set with only Opooyy log(1/))) ~ 250 labeled samples and leaving the remaining (11/e) x 49, 750 samples unlabeled is analogous to the aforementioned sample complexities achievable in the respective AL and SSL settings, although their assumptions may not be satisfied.
Instead of focusing on the same objective for both AL and SSL to attain the potential exponential sample complexity improvements above, we suggest using AL algorithm that queries instances to
Herr slightly abuse the Ô notation denote upper and lower bounds matching up logarithmic factors.
2

---

Under review as a conference paper at ICLR 2021
samples
samples
sampless
M
M
Figure 1: Illustration of how Il-model's (Laine Aila 2017) decision boundary changes as the proposed algorithm enlarges the labeled set. The 4 initial pivot points were manually selected.
help optimization. Specifically, we would like an AL algorithm to construct labeled dataset such that classifier f(T) trained for T iterations rapidly minimizes the optimization error [ f(oo),
and formulate SSL objective L., (J') guide the target classifier f(x)) arg miny (,))) towards solution that minimizes f((=) - f where f arg miny [f)] the optimal classifier and L, is the empirical loss computed over samples. This perspective spans an online setting where less training iterations implies better generalization, i.e. f(x) = - and AL focusing on [f(T) - | effectively minimize the optimization generalization error (f f*1 Together, the eplimization-gcnerraazaaaaieii
resulting model would ultimately minimize the generalization error's upper bound: | - f s [ - - + (f(x)) - f* The next section shows how we can carefully design labeled and unlabeled sets such that classifier trained on this construction enjoys fast rate of convergence by employing a recently developed tool known as the NTK.
2.2 NEURAL TANGENT KERNEL
The neural tangent kernel (NTK) Jacot et al. 2018 is theoretical tool developed understand how overparametrized networks can be opplmopdd and generalize to unseen data. In particular, the training dynamics of DNNs parameterized by 0, any iteration /. follows closed form expression
dfo, 1000 (x, X) (Jo, (X) - -))
dt
when minimizing the mean-squared error (MSE) loss using gradient descent, where KC (X, X) (Vofe, (z) (eoee (x") (x.))xa*** is the empirical NTK (Arora et al. 2019). where each element VaJo, VoJo,, (a') BCCC is matrix block and C' is the number of classes. If we let the width of all layers grow to infinity, a remarkable property holds in which the training dynamics can be characterized using matrix independent of time, namely the NTK KC:
(X) dt
KK(X, x) (fe. (x) >))
(2)
with probability 1 over random initialization the relation 2 holds with probability >
P. For any network of finite width d trained for / iterations, بd where da 0 as
Assuming a network that satisfies the differential equation, the transient solution is given by
fe, (X)
Σ
C.t exp (-A:(Z)))
for some constants and eigenvalue/vector pairs (A,, v.) of the NTK KCX, X'). Notice how the NTK, and turn the convergence rate, depends on the set of instances X it is computed over. This sparks the intuition that the rate of convergence can be controlled by carefully designing labeled set.
3 ACTIVE LEARNING VIA CONVERGENCE RATE CONTROL
3.1 CONVERGENCE RATE CONTROL.
Inspired by the aforesaid NTK's 's characterization of the model's training dynamics when supervised on the dataset it is computed over, we propose to move unlabeled instances X; selected from
converges the RHS in probability as the network's 's width sequentially grows infinity when initialized using He initialization.
Formally, the dynamics (x,
3

---

Under review as a conference paper at ICLR 2021
pool of unlabeled samples Ny that maximize the rate of convergence of the SGD dynamics to the labeled set Xt, hence the name convergence rate control (CRC). While Eq. B is a solution to the time-inhomogeneous ODE in Eq. [] the performance of aafinitely-wide networks fall behind their finite-width counterparts. We thus replace the eigen-pair (λ, u) of the true NTK K. with its empirical NTK (C(T) in Eq. using a model trained for T epochs until its validation accuracy saturates.
Maximizing the eigenvalues of the NTK is multi-objective problem, and CRC takes a worst-case approach to select unlabeled instances that maximize the smallest eigenvalue of the NTK:
max min As (Ie()) (Ka U U., UZ2)) X., Cu sel,
(4)
Each block R(T) (x) E RCx is replaced by its trace computed as E. R(T) (x. x²), which we numerically found to be an accurate replacement to the block matrices in computing the minimum eigenvalue, to reduce both computational and memory complexities. In general, the eigenvalue distribution is not necessarily supported over positive values, and we observed that considering only positive eigenvalues consistently results in higher performance than when considering both negative and positive eigenvalues. CRC thus scores unlabeled instances as the minimum over positive eigenvalues. The solution to Eq. 4 can then be found using dedicated AIPU-implementations available in popular DL frameworks such as PyTorch. This algorithm is detailed in Alg. g
A labeled sample's 's influence on a DNN's predictive behavior is abstruse. Intuitively, a labeled sample may be most informative when it is near region separating different classes; however, this does not guarantee that DNN learns such decision boundary effectively. Furthermore, it is unclear whether sample in some other region could better enhance classifier's performance when added to the labeled set, especially when considering SSL algorithms which complicate DL analysis. Contrary to the above intuition, Rebuffi et al.. (2019) demonstrates how a DNN trained with SSL objective Laiine & Aila 2017) learns decision boundary using only manually selected pivot points not on the class-separatiie separating region. Figure [eguureTillustraan illlustrates how the classifier's 's decision boundary progressively forms near low-density regions as CRC enlarges the labeled set.
3.2 THEORETICAL ANALYSIS
This section theoretically analyzes the effect of estimating the dynamics using the empirical NTK to construct a labeled set for least squares regression E (0) Ilfo (X' - - We begin with a
deviation bound of the empirical NTK from (Arora et al. 2019
Theorem (Paraphrased Theorem 3.1 in (Arora et al. 2019). Consider a fully-connected network
with ReLU nonlinearities of width d and depth L. At initialization, taking the form specified in (Arora
et al. 2019), the following holds with probability 2
LT/2
L 5 =ie.
max (Zre.2) )Bllss
K()r, S
d1/1 log
The above statement shows a general case in which the empirical NTK can be expressed as linear combination of the true NTK and noise matrix parametrized by 6 >> O, as long as the empirical NTK does not change abruptly. A similar result holds for ResNets and CNNs given appropriate conditions (Lipschitz, smooth, non non-polynomial, analytic) on non-linearities and initialization (Du) ct al., 2019), where it has also been shown that K())) provably stays close to K()) throughout training. The next proposition gives tractable approximation of the true NTK's (unknown) eigenvalue as neighborhood of the empirical NTK's (known) eigenvalue.
Proposition (CRC approximation error due to empirical NTK). Suppose I. = K(()) + Ae(e) with a symmetric noise matrix of bounded spectral norm p (Ni)) < c. Then, the true NTK's eigenvalues lies in an c-neighborhood of the empirical NTK's eigenvalues with respect I| i.e. (IC) E Be (2 (K(1) ) where the eigenvalues X(-) are listed monotonically.
This statement has nice implications on optimizing DNNs. Consider Theorem 5.1 in Du et al. 2019) that states running gradient descent with learning rate 7)- = O Aaain (XC,',, on least- squares regression using fully-connected network of sufficient width converges linearly at rate a/mmn (k.)). Two remarks follow:
4

---

Under review as a conference paper at ICLR 2021
Remark 1 (Better conditioning of learning rates). The sufficient condition learning rate is proportional to the (unknown) minimum eigenvalue of the NTK. This implies that the increased minimum eigenvalue allows for a larger set of admissable learning rate schedules. In (Athiwaratkun et al. 2019). it has been shown that SSI. algorithms take larger steps throughout training, continually exploring parameters. Since CRC permits larger learning rates, tuning the step-size may be easier and the larger steps taken by SSL algorithms can still converge when the step-size is over-estimated.
Remark (Direct estimate of sufficient learning rate and convergence rate guarantees). Both the admissable learning rates and convergence rate unknown. Invoking Proposition Jafte selecting >xmmn (x,, which would guarantee linear
X1 using CRC with K(T), we can set =
convergence with the rate deviating at most by the spectral norm of the noise matrix.
3.3 PRACTICAL CONSIDERATIONS
Summing the network's gradients over all layers for each instance pair is infeasible for modern network architectures, and we compare one realization of using all parameters with the final layer's 's to compute the NTK. A comparison of one realization using the NTK computed over all layers vs, using just the final layer averaged over 3 trials (Tab. D shows how using the final layer performs just as well as when all layers were used but with much faster (x00) queries. If we assume that the shallow layers saturate more quickly than deeper layers, justified by the 'lower layers learn first' phenomenon (Raghu et al., 2017). the NTK estimate computed at the network's ' last layer is a prediction of the training dynamics corresponding to a single layer perceptron attached to a (slowly-changla) extractor. In this perspective, the final accuracy is mostly affected by the final layer which determines how high-level features are recognized, and designing a labeled set using the NTK estimated over the last layer would sufficiently capture the model's training dynamics.
feature
Initial Pool
Randomly initialized model
Random sampling
# Labeled
50
100
150
100
150
200
Last
53.12
67.14114.28
71.98
83.67=3.24 73.41
83.67+1.31
All 50.47
68.25
74.03
71.26:1.992
78. 13
79.1013..6
Table 1: CRC performances when NTK is computed over final vs. all layers with G at Q = 50. Left describes performances when initial query and initial SSL training is performed with a randomly initialized model (one trial for 'All'); right uses random sampling for the first query.
One reason why estimating the training dynamics over all layers could be worse than using the last is that the former requires a network trained in the next SSL phase learn a similar low-level representation to that obtained in the previous SSL phase. However, it was observed by Raghu al.] (2017) that two randomly initialized networks trained on the same dataset have similar final layers but extremely different intermediate representations. Because our networks are retrained from scratch between each query iteration, is highly likely that the next network will have very different intermediate representations, and these middle layers would provide noisy estimates to how much the model's functional representation would be affected by the enlarged dataset. Since we are seeking to modify dataset in order to amplify model's performance, it is reasonable that enlarge the labeled set based on how much the additional samples would affect the model's final layers. Had designed the experiments such that model is continuously trained from its previous SSL phase, computing the NTK over all layers may have been beneficial at the expense of computation.
3.4 MYOPIC vs. BATCH-MODE ACTIVE LEARNING
Myopic AL policies refer to algorithms that score unlabeled instances based on their individual importance. Considering how an expert annotator 'in-the-loop' must label queried samples, it is desirable that an AL algorithm queries large batches based on their collective importance. Myopic policies usually degrade in performance sample identical instances (Kirsch et al. 2019), and it has been of great interest in designing a computationally efficient batch-AL algorithm. CRC (Alg. 2 is aatch-mode AL algorithm as it computes Amin over groups of unlabeled instances XT, To cope with the combinatorial complexity associated with the outer-maxing maximizaaiinioon in Eq. 4 randomly sample candidate groups Xr without
the query size Q increases, as they may repetitively
5

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Convergence Rate Control (batch-mode solution to equation 4)
Inputs: Unlabeled pool Ly. query-size Q, group-size G.
Output: New pool X to be labeled.
for t 1,............... |Kul/G ......Ke// I/G do
x:(1) + G unlabeled instances randomly sampled from Xu.
s(xx1) + > (XL U x.!' using the empirical NTK computed over final layers. end for Store
Q/G highest groups: 11:-. 11....1/// t arg max (s).
Xe + xx(ti) x((ti) U... U...U u...ux(( (1ar0)
return
replacement. This randomization significantly reduces the search space, potentially yielding highly sub-optimal solutions, and we introduce a hyperparameter G such that G divides Q, and search over candidate groups |xx,] G, selecting Q/ groups at each query step. The group size controls whether the outer maximization solved more accurately (G = 1) without considering the collective significance of group, or the minr-minimizzaiinn incorporates the collective importance of all queried samples (G Q) at the expense of a substantially smaller search space. This trade-off is established in Tab. 2 when Q 100, averaged over three realizations for G 2, 10, 100. Our relatively small group-sizes make the cubic complexity of the inner-minimization negligible, and a larger group size consequently faster due less (Q - Q/G) eigen-deccopposition operations and inefficient batch-gradient computations in autograd packages. All experiments hereon use = Q considering the speed vs. performance trade-off.
Query step
2
3
G
84.72 + 0.96
87.11 + 1.14
87.83 - 0.17
88.3 = 0.30
89.44 0.59
G
82.55
+ 3,21
84.13
+ 2.64
87.24 + 2.42
87.66 + 1.33
88.63 + 0.60
G 10
83.38
+ 1.14
85.71
+ 1.50
88.07
+ 0.06
88.36 + 0.71
89.35 0.79
G 100
83.31
+ 2.17
86.49
+ 1.47
86.76 + 2.56
88.49 1.43
88.63 + 1.67
Table 2: Effect of different group sizes with Q = 100 using random sampling for the fist query.
3.5 RELATION TO GRADIENT-BANE METHODS
The proposed algorithm can be interpreted as measuring the importance of unlabeled instances by how much they would change model's parameters. Two AL algorithms are similar in this manner in that they seek to label instances which affect the model the most: expected gradient length (EGL) (Huang al. 2016) and BADGE (Ash et al. 2020). EGL first computes the gradient of the cross-entropy loss over all un unlabeled instances, replacing the ground truth target with an expectation over a posterior distribution determined by the trained model, then selects instances with the greatest norm. BADGE uses an embedding of the loss' gradients using predicted classes, computed over the parameters in just the final layer, and uses kmeans++ enforce diversity. Nonetheless, both algorithms only estimate the benefit due to candidate unlabeled samples and do not measure the collective influence of the labeled set.
EXPERIMENTS
4.1 IMPLEMENTATION DETAILS
Our SSL implementation is primarily based on different publicly-available PyTorch implementations of FixMatch (Sohn et al. 2020) for CIFAR 10 and CIFAR 100 as well as mean teacher (Tarvainen & Valpola 2017) for SVHN that performed best at the time of this work. We made modifications as

---

Under review as a conference paper at ICLR 2021
Accarscy
Labeled
500
Kandon
018153.77
92
#241
34925-07
8508
87.00=1.25
87.5780:57
879220047
51.3722155
Entropy
72.43:821
82.41=22.9
83.88=199
8486=1
86.42:095
85.51
8K 09:00.07
86 87:8 1:22
88.27:0.00
18.44-1.17
Confilenc
52.54+7.11
49.55+7.77
30.67+3.15
53.44-875
77.08
78
73.68+5.11
73
75.08-1.229
EGL
57.1817.41
56.61110.53
68.76112.57
74.47112.52
76.671743
13.11
2.27
81.2015.10
82.62.0.366
83.55_..336
CRC
78.4113.16
8367.13.24
85.6711311
86.8800.8
87.0110228
1.14
1..71
88.08.0.06
88.37.10.11
89.38.00.99
Table Performances on CIFARIO using Q E {50, 100} with random sampling for the first query.
suggested in (Oliver et al. 2018). particular, we used the WRN-28-2 and WRN-28- 10 architectures for SVHN/CIFAR 10 and CIFAR 100, respectively, further motivated by the derivation of NTK as a network in its infinite width limit. Mean teacher (MT) enforces consistency between the model trained using SGD and an exponential moving average (teacher) of the model's weights. Fix.Match is a variant of MixMatch (Berthelot et al.) 2019). replacing standard augmentations with more powerful augmentation techniques when computing the SSL. loss. In short, FixMatch enforces consistency between a classification model's predictions on perturbed inputs which effectively yields a more robust model with small Jacobian norm (Athiwaratkun algorithms including MT. Furthermore, the hyperparameters in FixMatch were kept the same across different dataset sizes in their original report, making our experimental comparisons convenient.
al.) (019) in junction with other SSL
The initial pool of labeled instances significantly affected the downstream SSL task and subsequent AL queries, especially for uncertainty- based algorithms (see section 4.2). is practical assume that a model would initially have access to a small pool of labeled images with an equal number of classes. Thus, we randomly sampled balanced number of images per class in the first query iteration and use the AL algorithms in subsequent queries without enforcing balanced classes. Between each query step, the classification network was trained until either its validation accuracy does not improve for 50/100/co epochs or 350/600/512 12 epochs is reached for CIFAR 10/100/SVHN, All experiments are repeated 3 times with mean + std performances reported unless stated otherwise. Our implementation will be open-sourced upon publication.
4.2 BASELINE ALGORITHMS
Both AL and SSL algorithms demand much more time than standard supervised learning. and an extensive comparison of all ASSL combinations is beyond compute availability. We resort to comparing the proposed algorithm with 3 other AI. algorithms, of which scores unlabeled instances based on how much they reduce a model's uncertainty, and the other because of its similarity to CRC. Uncertainty-based AL (Wang & Shang 2014) is one of the simplest DL-based AL algorithm that selects the unlabeled instance with lowest confidence in its prediction: X arg (r }. maxy fe.y(z) In the same work, Wang & Shang (2014) proposed to also use entropy as a measure the model's 's uncertainty unlabeled samples. EGL (Huang et al. 2016) retrieves
instances that modify model the most: X = arg max ()e Ey-pp( va.0) [[V o H (3. fo [=]
where p(y; 24, 0) = (1.) is the model's confidence in class and H is the cross entropy function.
4.3 ACTIVE SEMI-SUPERVIES LEARNING
Here we report the sample efficiencies obtained by different SSL algorithms when the labeled set is constructed using various AL schemes in Tabs. 3 and 4 For reference, the implementations used for each experiment achieve average accuracies of SVHN (100/class): 93.52% CIFARIO (25/class): 87.33, and CIFAR 100 (40/class): 48. 48.96% with balanced sampling. Note, however, that SSL settings consider labeled sets (and consequently, unlabeled sets) with equal numbers of images per class, putting SSL. settings to an unrealistic advantage at the same number of labeled images. Different levels of class-imbalance result in larger performance variance, which is especially critical in the low-data regime.
One difficulty arising from the ASSL setting is class imbalance. In contrast to standard AL settings that consider much larger query sizes, the small query size in ASSL significantly impacts the class distribution, resulting in occasional performance drop for certain query strategies. Entropy has repeatedly achieved state-of the performance (Gissin & Shalev-Shward
2019 Wang et al. 2017 Ash et al., (020) in AL settings despite its simplicity, and our experiments show the same holds for ASSL. Conforming with our motivation in section 2.1 CRC performed comparable better
7

---

Under review as a conference paper at ICLR 2021
Accunccy (8%)
Laheled
140
100
180
200
250
300
Kandom
56.0313.83
66.48_12.55
13.4611773
19
91011009
414511M
T1S7
0.74
45.1910.91
49.35=1.55
35.91
64.02-4.58
85.1445.01
91,44+023
41.87+145
0.59
50.16=0.37
Table 4: Mean teacher (SVHN: Q = 20) and FixMatch (CIFARI00: Q = 50) performances with 12 and 20 randomly sampled images per class in the first query.
than entropy although it does not explicitly enforce diversity on the labeled set. Furthermore, while both CRC and EGL scores instances by estimating how much they would affect the model's training dynamics, only CRC outperformed random sampling. Our results suggest that actively enlarging the labeled can definitively reduce the labeled sample complexity in the SSL setting, without having to construct a labeled set consisting of images representative of their class.
Existing DL-based AL algorithms have performed comparably to random sampling when using large query sizes, and our experiments show the same for entropy and CRC with Q 100 in the ASSL setting. A proper AL algorithm should achieve higher performance at the same number of labeled samples if the query size small since it would be taking more query steps in order to claim its superiority to random sampling; however, we observed that only CRC satisfies this property. EGL's low performance had been reported image classification tasks (Gissin & Shalev-Shwartz 2019
Sener & Savarese 2018 Ducoffe & Precioso 2018 under the AL setting. Our experimental design of retraiming networks from scratch may have had negative influence on EGL, similar how affected the NTK estimate over all layers. We attribute confidence's 's low performance to the poor calibration of DNNs (Guo et al. 2017), inadequately capturing the model's uncertainty unlabeled instances. A successful application of confidence-basd query may require incorporating calibration while training classification networks before performing such queries.
Randomly initialzee modela (Q+50)
improvements
10
30
Absoluto diferrncc (N)
14
EGL
CRC
Confidence
Acourary (%)
70
10
Contieece
images
Quary stop
Figure 2: Performances when the initial AL queries were performed using a randomly initialized model. The figure on the right underscores performance gains in consecutive query steps.
Ideally, AL algorithm should have nice transferrability property, constructing labeled sets that are useful to train other networks. This obviously holds for random sampling, as the queries do not depend the model's weights. To validate the transferrability of dataset constructions of AL. algorithms, we used randomly initialized model to query only the initial pool, trained the model using a different realization of initialization, and done previously for other experiments, queried additional labels using the model trained using SSL. As shown in Fig. 2 however, such initial queries adversely affected all subsequent queries. While entropy and CRC overcome this initial disadvantage after few query iterations, other baselines tend to under-perform random sampling due to this initial disadvantage. This phenomenon has not been reported in previous works, and whether this is an used deserves future notice.
artifact of our ASSL setting or the architecture/hypeparaae
4.4 CONVERGENCE RATE AND TIME HORIZON PREDICTION
The proposed CRC algorithm is designed to query unlabeled instances that improve the rate of convergence DNN in the following SSL phase. To see if our algorithm achieves this purpose, plot the empirical NTK's minimum eigenvalues used to score unlabeled instance groups against the number of training epochs until the test loss reaches its global minimum in Fig. (a) to show how the
8

---

Under review as a conference paper at ICLR 2021
Conversence rate orediction time abserved
aigendaoss
Rediamtion Reaiization
IRE
Epochs
Quary
Figure 3: Minimum eigenvalues' distribution in log-scale (Q 50). Left figure shows how in- formative the minimum eigenvalues are in terms of predicting the number of epochs required for convergence, and right figure illustrates how the minimum eigenvalues' distribution concentrates towards zero. Negative linear slope implies (a) exponential convergence as predicted by Eq. and (b) slower convergence rate with increasing labeled set size.
minimum eigenvalues are predictive of the time horizon. Global minimum here refers the value for which the loss never falls below until training completes. We additionally plot how the minimum eigenvalues' distribution progresses with query steps, where Fig.
3 (b) shows that the eigenvalue distribution concentrates towards 0 as the labeled set grows, implying slower convergence rates. A similar observation was made by Nitanda & Suzuki (2020) where the authors showed how the true NTK's s eigenvalues concentrate towards zero as the training set size increases, whereas our plot is over a union of labeled and queried groups. This figure illustrates how all candidate datasets will inevitably have eigenvalue distributions concentrated near zero, but the enlarged dataset chosen by CRC will have the fastest convergence rate among all considered candidates.
CONCLUSION
This work motivated the combination of AL with SSL, using the former for optimization and latter objective to restrict the hypothesis space to those that generalize well. We then proposed an AL algorithm inspired by the NTK, and demonstrated how controlling the convergence rate of the training dynamics can significantly improve sample efficiency. To the best of our knowledge, this work is the first practical application of NTT outside of supervised learning, where it has been shown that the true NTK is inferior to its DNN counterpart. In contrast to most DL-based AL experiments which use relatively small networks, this work demonstrates that DL can benefit from AL using modern architectures, Our algorithm outperformed uncertainty-based AL algorithms which enforce diversity and an AL algorithm with similar goal of maximizing the model's 's change. The proposed algorithm's superiority was also demonstrated in the batch-AL setting, where an optional hyperparameter can be used to control the trade-off between computational complexity and performance.
Our CRC algorithm is developed under the assumption that a well-optimized network f(x) induced by the SSL objective is good approximation of a model f* that generalizes well. Incorporating the interplay between AL and SSL seems promising in further reducing the sample complexity, designing either an SSL algorithm best fit for some fixed AL algorithm or joint ASSL scheme. For example, CRC provides an estimate on the number of epochs required for convergence, and learning rate schedule best fit for the estimated time horizon could be used (Ge et al. 2019).
The proposed CRC algorithm can be extended several directions, applying generalization guarantees characterized by the NTK to an online (streaming) setting where unlabeled instances cannot be stored. Another exciting direction to pursue would be to use the True NTK (Arora et al. 20119; Novak et al.) 2020) to estimate the training dynamics. While CRC is motivated by controlling the transient solution using an estimated proxy of the training dynamics, the true NTK would enable an exact computation of the ODE solution. Of utmost importance would be that this could allow AL queries to be performed offline, that is, without having to train a model between each query iteration, alleviating the long training times associated with ASSL..

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d/Accéé Buce E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8141-8888 81500 Curran Associates, Inc., 2019.
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.
Ben Athiwaratkun, Mare Finzi, Pavel Izmailov, and Andrew Gordon Wilson. There are many consistent explanations of unlaheled data: Why you should average. In International Conference on Learning Representations, 2019.
Maria-Florina Balcan and Ruth Umnr. Active Learning Modern Learning Theory, pp. 13. Springer New York, New York, NY, 2016. ISBN 1188-114999-2888 doi: 10.1007/978- 1-19-914-9---2-- 2864-4 769.
Maria-Florina Balcan, Steve Hanneke, and Jennifer Vaughan. The true sample complexity of active learning. Machine Learning, 80:1 11-19, 09 2010. doi: 10.1007/5109944000-511111
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Vaughan. A theory of learning from different domains. Machine Learning, 79:151-175, 2010.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin Raffel. Mixmatch: holistic approach to semi- supervuee learning. arXiv preprint arXiv: 190X.v pet.i/205599999 2019.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. 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.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. 02 2018.
Rong Ge. Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'lché- E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 14977-14988. Curran Associates, Inc., 2019.
Daniel Gissin and Shai Shalev-Shwartz. Discriminative active learning, 07 2019.
Christina Göpfert, Shai Ben-David, O. Bousquet, S. Gelly, I. Tolstikhin, and Ruth Urner. When can unlabeled data improve the learning rate? In COLT, 2019.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, pp. 1321-1330. JMLR. 2017
Jiaji Huang, Rewon Child, Vinay Rao, Hairong Liu, Sanjeev Satheesh, and Adam Coates. Active learning for speech recognition: the power of gradients. 12 2016.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 8571-8580. Curran Associates, Inc., 2018.
Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. F. BAlché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 7026-7037. Curran Associates, Inc., 2019.
Wallach, Larochelle, A. Beygelzimer,
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. In ICLR (Poster). OpenReview.net, 2017.
10

---

Under review as a conference paper at ICLR 2021
Nong-Hyun Lee. Pseudo-label: The simple and efficient semi- semi-supervised learning method for deep neural networks. ICML 2013 Workshop : Challenges in Representation Learning (WREPL), 07 2013.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34, 10 2006. doi: 10. 12 02000000000000000000777780
Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime, 06 2020.
Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In International Conference on Learning Representations, 2020.
Avital Oliver, Augustus Odena, Colin A Raffel, Ekin Dogus Cubuk, and Ian Goodfellow. Realistic evaluation of deep semi-super learning algorithms. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchii and R. Garnett (eds.), Advances in Neural Information Processing Curran Associates, Inc., 2018.
Systems 31, pp- -235-3246
Maithra Raghu, Justin Gilmer, Jason Yosinski, and Jascha Sohl-Dickstein, Sveca: Singular vector canonical correlation analysis for deep learning dynamics and interpretability. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 6076-6088 6085. Curran Associates, Inc., 2017.
Sylvestre-Alvise Rehuffi, Sebastien Ehrhardt, Kai Han, Andrea Vedaldi, and Andrew Zisserman. Semi-supervised learning with scarce annotations. Technical report, 2019.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018.
Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D. Cubuk,
Alex Kurakin, Han Zhang, and Colin Raffel. Fixmatch: Simplifying semi-supervisee learning with consistency and confidence. arXiv preprint arXiv:2001.07685 2020.
Shuang Song, David Berthelot, and Afshin Rostamizadeh. Combining mixmatch and active learning for better accuracy with fewer labels, 12 2019.
Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 1195-1204. Curran Associates, Inc., 2017.
Vladimir Vapnik and Rauf Izmailov. Learning using privileged information: Similarity control and knowledge transfer. Journal of Machine Learning Research, 16(61):2023-20) 2015.
D. Wang and Y. Shang. A new active labeling method for deep learning. In 2014 International Joint Conference on Neural Networks (IJCNN), pp. 112-119, 2014.
Keze Wang, Dongyu Zhang, Li, Ruimao Zhang, and L. Lin. Cost-effective active learning for deep image classification. IEEE Transactions on Circuits and Systems for Video Technology, 27: 2591-2600, 2017.

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 EXPERIMENTAL DETAILS
All experiments described samples equal numbers of images per class on the first query step. Those described as "using random sampling" uses the Random (passive) AL scheme, i.e. sampling uniformly random, and "randomly initialized models" refers transferrability, where the first query step is performed using randomly initialized model (e-g. confidence of a randomly initialized model when using the "Confidence" AL scheme), then performing SSL with another instance of random initialization. When random sampling performed,
several experiments and used the best models at query step O, since we observed (similar to transferrability experiments) that the first query step may highly influence subsequent steps, affecting the performance of different AL algorithms resulting in an unfair comparison. This is why all experiments with first query being random sampling (query step 0) excluded the first query step, as they all used identical models when performing the first actual AL query (query step 1). All subsequent queries were performed using the trained model obtained from the previous SSL step, regardless of transferrability. Taking "Confidence" on CIFARIO as an example for the AL scheme, a model trained using SSL at query step 1 is loaded to query the next 50 (when Q 50) labeled samples for query step 2.
Architectures used for the last is known requirement due to more classes. SVHN used leaky ReL.U with negative slope 0.1 for Mean Teacher, and the others used ReLU activations. "One epoch" is defined as the number of SGD steps between each validation, which we set as 1024 training iterations (far more frequent than the default parameters for Mean Teacher on SVHN), All other configurations were set in the original implementations.
WWWCCIIIARI/CIAARRIIII 100 are HAN-22-2/WRNY. 28 22-22/2--222---- where
A.2 PROOF OF PROPOSITION
Proof. Let K k((t) and denote A (-) the eigenvalues of some matrix of size n, listed in non-increasing order. Since K. and k(0) are Hermitian by definition, Weyl's inequality gives
A (6() +2, (NicO) S d (KOO +N710) S Ar (KE(0) + >o (NC:)) .i+J - k
This implies
Au (((() An (Arit)) s du (Ke() + +rr(t) s +(((())))((()))))).))))))))))))) wk E m......m.
and hence,
(K) A (((())= Mo (kin + trr))) do (x20)) s $1
where || |/2 is the spectral norm.
12


Reviews:
[{"review_id": "ouY9OB8_tcw", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper makes an attempt at combining semi-supervised and active learning. The authors note that in restricted settings, SSL and AL can achieve exponential improvements over standard supervised learning with random sampling. Instead, this work attempts to use active learning to speed up the convergence to the asymptotic classifier (in terms of epochs) and semi-supervised learning to achieve the exponential improvement in data efficiency. This work is inspired by a neural tangent kernel analysis.\n\nStrengths:\n - Integrating active learning into SSL techniques that perform well for image datasets is a good goal, as SSL techniques have dramatically improved for image datasets in the recent past.\n - Promising empirical performance against a few other algorithms.\n\nWeaknesses:\n - The empirical results are only reported for a single dataset (CIFAR10).\n - Although the proposed algorithm, Convergence Rate Control (CRC), is supposed to speed up convergence, only final accuracy is reported. Thus, the reason for the increase in performance is not validated.\n - The theory is perhaps limited because of crude approximations, which aren't validated in terms of approximation error, but overall performance (see table 1 and 2). In particular, the algorithm uses only using the gradient from the final layer parameters, a standard batch approximation, and a \"group\" approximation.\n\nQuestions:\n - Can the authors describe more the \"ill-posed nature\" of active learning?\n\n\n\nAfter reading author response ================================\n\nThank you for the response.\n\nIt's good to know that CRC outperforms random sampling on a couple other image datasets, but would be informative to see the results with respect to other AL techniques.\n\nI wasn't quite able to follow the logic of section 3.2, but this seems on the right track.\n\nThe issue I see with using the final layer is not performance related, it's that it seems to throw out the theory you claim to be using. For instance, the fact that the performance dramatically improves is troubling and makes me wonder if the algorithm is working because of the theory or for a different reason. On the other hand, if you aren't able to make the theoretical justification more compelling, I think it would be fine to say the theory is just for inspiration.\n\nI agree there is no batch approximation when G=Q. I might be missing something, but the paper says \"All experiments hereon use G = Q/10 considering the speed vs. performance trade-off\". \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "eZUi0uRWs7U", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper combines semi-supervised learning with active learning, arguing that we should try to focus on actively choosing to label points that improve the convergence rate of the model after adding that example to the training set. They argue that especially in pool-based active learning, where an unlabeled pool of candidate data points are available to choose from to label, methods should also use this unlabeled pool for semi-supervised learning. To optimize convergence rate, they try to select points that maximize the smallest eigenvalue of the empirical NTK over the final layer only, as an approximation (which the authors show seems to do similarly to computing the full NTK, when the next training episode of the active learning is warm-started with the weights of the previous episode.\n\nStrengths:\n- The method is general to any SSL method, and the authors consider one of the more recent SSL methods, FixMatch. \n- The use of SSL in the pool-based active learning setup makes good sense. \n- They use a nice tractable formulation of the convergence rate optimization objective through the eigenvalues of the NTK on the final layer only.\n- They show empirically that more positive eigenvalues of the last layer NTK leads to convergence in fewer training epochs.\n- The paper suggests a subtle difference between randomly initializing the networks between each phase of active learning and warm-starting from the previous model, noting that the confidence scores, etc. used to select examples for active sampling could be dependent on the random initialization, noise during optimization, among others, and thus may not transfer to the next phase if the model is then randomly re-initialized. \n\nWeaknesses: \n- The authors argue that since active learning and semi-supervised learning both have the potential to improve sample efficiency exponentially, their combined benefit is \"most likely marginal\". However, there is not much theoretical or empirical evidence for this beyond some intuitions. It's quite unclear whether the combined benefit is only marginal, since the assumptions on the data that are needed for semi-supervised learning and active learning are not really the same. This would seem to suggest that combining them still makes sense to robustify the gains in sample complexity, even ignoring potential stacking of the gains. \n- The convergence rate control method seems to be motivated by wanting the active learning component to \"optimize something different\" to the SSL component (which is optimizing for test generalization). It's unclear whether faster convergence rate is really different from improving sample complexity/test generalization. Consider running a learning algorithm on a stream of data examples sampled IID. Consider an algorithm that can learn to low test error with few samples; this means that with few samples, the model can get low loss on unseen samples from the distribution, leading to low loss if you continued optimization. This would mean that the training has more or less converged. Now consider a deep learning algorithm with fast convergence rate; this means that with few iterations (read: few samples seen), the algorithm converges to a solution that continues to have low loss if you continue optimization (and thus low error on IID samples from the same distribution => low test error). Could this method of selecting examples to improve the convergence rate be actually optimizing something similar to improving generalization, instead of doing something alternative?\n- In Algorithm 2, it seems like Q/G random groups of unlabeled data are considered, and the Q/G best groups are added to the dataset. Doesn't this mean that all the samples in the Q/G random groups will be added regardless of the NTK eigenvalue calculation? \n- Empirically, it's unsatisfying that even with more labeled images than FixMatch (with 250 labeled examples, they get 94\\%), this FixMatch + active learning method gets worse accuracy (85\\%, Table 3, 300 labeled examples). What is the performance of FixMatch without active learning using the training setup that the authors used, just for comparison? It seems surprising that some of the Fixmatch + active learning methods get only about 50% accuracy when Fixmatch itself can get >90\\%. If the labeled seed set were balanced, would we see results surpassing Fixmatch? \n\nOther:\n- Is it true that reinitializing the networks hurts CRC but doesn't hurt the Entropy method much? Why is that? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "N0jrPE61t_d", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\n\nThis paper introduces a novel method (CRC) to unify active learning (AL) and semi-supervised learning (SSL). The paper claims that designing labeled datasets by querying can control the convergence rate. To design queries, the proposed method selects unlabeled data points that maximize the smallest eigenvalue of Neural Tangent Kernel (NTK). Empirical results are presented.\n\n# Strengths\n\n1. I believe combining AL and SSL is an important research direction.\n1. This paper shows a novel use of NTK that has many potential use cases. \n\n# Weaknesses\n\n1. The authors say existing approaches that combine SSL and AL (e.g., MMA by Song+2019) are \"limited to independent combinations of SL and SSL.\" However, both MMA and CRC alternatively use SSL and AL.\n1. The authors say the performance of baseline (FixMatch, an SSL method) is upper bound because the model is trained longer (from 3x to 5x more than this paper) and labeled data are balanced. \n  - Can CRC achieve comparable performance to FixMatch if trained longer? Or is performance degeneration mostly due to NTK?\n  - I think AL methods can ideally query and obtain more useful labels of support vectors between difficult boundaries compared to SSL methods. Thus, if the same number of labels is available, shouldn't SSL be the lower bound?\n1. To use NTK, the method needs to train the model from random states every time labels are updated and thus, needs extra computational resource.\n1.  Queried labels depend on the current model developed from certain initial states. However, after querying, the model is reinitialized. I guess this degenerates performance.\n1. Despite the interesting concept, the empirical results are not appealing.\n\n# Feedback and Questions\n\n* Why some values in tables are with std and others are not? (e.g., Table 2) Also, a value in table3 for confidence in labeled images of 400 is missing.\n* $C$ on page 3 is not defined.", "extra_scores": {}, "extra_text": {}}, {"review_id": "8pGZOnwTm19", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed an active learning strategy to improve the convergence rate for the semi-supervised deep learning algorithm. When the SSL objective could learn a good approximation of the optimal model, the proposed method efficiently converges to the result with a few queries. The essential technique used here is the recent advance of the neural tangent kernel; that is, when the eigenvalue of the neural tangent kernel is large, the convergence rate is in turn fast. Inspired by this theoretical results, the authors provided the learning algorithm to maximize the smallest eigenvalue of the neural tangent kernel. Empirical studies show the effectiveness of the proposed algorithm. \n\n\n\npros\n1. The authors provide an interesting idea of using the theoretical results of the neural tangent kernel to improve the convergence rate by actively labeling the unlabeled data in semi-supervised learning. Such a design is simple but efficient.\n2. Compared with previous works, the proposed method also considers the influence of labeled data (calculate the eigenvalues jointly with labeled data) and uses the information provided by the SSL objective.\n\ncons\n1. This paper provides an insight into choosing the unlabeled data to improve the convergence rate of SSL methods. Empirical evidence shows the effectiveness of the proposed algorithm, but there lacks solid theoretical support.\n2. The improvement of the proposed algorithm over the baseline methods (query by entropy) is limited. As shown in Table 3, the proposed CRC is not the best choice in some cases. There lack the explanation of this phenomenon.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper investigates an active learning strategy for speeding up the convergence for SSL deep learning algorithms. When the SSL objective could learn a good approximation of the optimal model, the proposed method efficiently converges to the result with a few queries. The main idea is that when the eigenvalues of the NTK are large, the convergence rate is faster. The proposed algorithm maximizes the smallest eigenvalue of the NTK. An empirical investigation is also reported.
The reviewers appreciated the general idea, but questioned about the actual execution of this paper in terms of both experimental comparison and (lack of) supportive theoretical results. I would like to encourage the authors to consider improving their paper along one of these two lines.  Unfortunately, as it currently stands, this paper is not ready for publication.
Decision: Reject