Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Strengths:
 - 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.
 - Promising empirical performance against a few other algorithms.

Weaknesses:
 - The empirical results are only reported for a single dataset (CIFAR10).
 - 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.
 - 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.

Questions:
 - Can the authors describe more the "ill-posed nature" of active learning?



After reading author response ================================

Thank you for the response.

It'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.

I wasn't quite able to follow the logic of section 3.2, but this seems on the right track.

The 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.

I 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". 

review_title: A new active semi-supervised learning algorithm based on NTK theory

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 



pros
1. 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.
2. 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.

cons
1. 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.
2. 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.
review_title: An active learning based strategy to improve the convergence rate for semi-supervised learning inspired by the neural tangent kernel

final_score: rating: 5: Marginally below acceptance threshold
review_content: # Summary

This 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.

# Strengths

1. I believe combining AL and SSL is an important research direction.
1. This paper shows a novel use of NTK that has many potential use cases. 

# Weaknesses

1. 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.
1. 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. 
  - Can CRC achieve comparable performance to FixMatch if trained longer? Or is performance degeneration mostly due to NTK?
  - 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?
1. To use NTK, the method needs to train the model from random states every time labels are updated and thus, needs extra computational resource.
1.  Queried labels depend on the current model developed from certain initial states. However, after querying, the model is reinitialized. I guess this degenerates performance.
1. Despite the interesting concept, the empirical results are not appealing.

# Feedback and Questions

* 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.
* $C$ on page 3 is not defined.
review_title: This paper is interesting but has a large room to improve

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Strengths:
- The method is general to any SSL method, and the authors consider one of the more recent SSL methods, FixMatch. 
- The use of SSL in the pool-based active learning setup makes good sense. 
- They use a nice tractable formulation of the convergence rate optimization objective through the eigenvalues of the NTK on the final layer only.
- They show empirically that more positive eigenvalues of the last layer NTK leads to convergence in fewer training epochs.
- 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. 

Weaknesses: 
- 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. 
- 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?
- 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? 
- 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? 

Other:
- Is it true that reinitializing the networks hurts CRC but doesn't hurt the Entropy method much? Why is that? 
review_title: Review

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