Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes an active learning method for deep learning (named dynamicAL) that selects data points which maximize the training dynamics. The paper proves a relationship between the convergence speed of training and generalization and shows experimentally that dynamicAL can outperform other popular active learning baselines.
strengths_and_weaknesses: Strengths:
- The method proposed in the paper is novel and works well compared to other baselines.
- The experiments are extensive.
- The paper is well-written.

Weaknesses:
- The main theoretical results in Section 4.1 (Theorem 1 and 2) are only for iid data, which do not hold for the active learning setting. Although Section 4.2 gives some discussions for the active learning setting, the paper does not prove any formal results for the setting.
- Some notations can be simplified to make the formulas cleaner; for example in Eq 13, the subscript u for x, y, etc. can be dropped without affecting the meaning of the equation. The same is also true for other equations such as 12, 14, etc.
questions: - Can you prove formal results similar to Theorem 1 and 2 for the active learning setting in Section 4.2 and 4.3 ?
limitations: There is no potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: 1. The paper describes DynamicAL, an algorithm for active learning based on NTK-based analysis of training dynamics
2. The algorithm is based on the notion that fast training results in better generalization. The authors describe "alignment" as a measure of convergence rate and show that this term affects the generalization bounds derived in the NTK regime.
3. The authors then show that the proxy used in DynamicAL ("training dynamics") correlates with alignment and therefore could be used as a proxy
4. The paper propose a greedy variant of the proposed algorithm and show that it well approximates the non-greedy variant, while being significantly faster
5. The paper shows that the resulting algorithm outperforms existing baselines on a few models/datasets
strengths_and_weaknesses: Strengths:
1. Good presentation, well structured
2. Well motivated, main claims of the papers are well justified from theoretical point of view, and verified empirically (section 4)
3. Resulting algorithm is simple to implement and could be considered generalizations of existing methods (as mentioned in section 3.3)

Weaknesses:
1. Derivation and algorithm based heavily on NTK theory, but practical sized networks have been shown to deviate far from this regime (see [1, 2], for example). This paper does not address this issue. At least some discussion of it would be useful
2. Unclear computational requirements compared to other methods or runtime analysis (this part, while possible to interpret based on the algorithm description, could be stated more explicitly)
3. Improvements over baselines seem rather marginal (although this is somewhat expected in a somewhat saturated field)

[1] - https://arxiv.org/abs/2007.15801
[2] - https://arxiv.org/abs/2010.15110
questions: 1. What is the runtime of the algorithm? It appears that calculating equation 15 would scale linearly with |S|, which seems quite undesirable

2. Does the algorithm suffer from clustering due to the greedy approximation? As an example, suppose that every single item in the dataset is duplicated 10 times and the query size is 10. Will the algorithm not pick the exact same image 10 times? (see the distinction between BALD and BatchBALD, for example)

3. Is the experiment in section 4.3 calculating G using pseudo-labels or ground truth labels? It would be interesting to see the effect of changing pseudo-labels to ground-truth labels on the results in section 4.3

4. While section 4.3 shows that G (training dynamics) correlates with A (alignment), it would useful to see how well G correlates to the final generalization performance, as this is true objective of the active learning algorithm.
limitations: See the questions and strength/weaknesses section
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors address the problem of active learning in the setting where the learning model is over-parameterized with respect to the data.  They note that theories of active learning are based upon assumptions that hold for hypothesis classes with lower parameterizations may not hold in the over-parameterized setting, and propose to use newer tools from generalization theory to theoretically ground active learning for deep neural networks.  They propose to use tools for studying the relationship between training dynamics and generalization performance (such as the NTK) as the basis for new deep active learning heuristics to select unlabeled data points in the pooled setting, eschewing traditional methods that select points that maximize either labeled data diversity or model uncertainty.   They demonstrate that selecting data points which maximize the rate at which models train (the rate of descent of the training loss as a function of the number of parameter updates) is positively correlated with a lower generalization bound, thus establishing it as a bona fide heuristic for the acquisition function.  

strengths_and_weaknesses: Lines 49-52: Will definitely have to ensure that TD can be computed or well-estimated quickly, lest this be impractical

Line 100: $K^{i,j}(x,x’)$ is the inner product of the gradient of the $i$-th class probability and the gradient of the $j$-th class probability evaluated at {x} and {x’} respectively.  I think?  It's not totally clear, and having to flip back to the notation section much higher up is not ideal.  

Line 122: Similar criticism here.  This section includes a lot of notation, it would help the reader here to better understand equation (8) to recall that $K^{ij}(X,X)$ is the empirical NTK.

Line 150: This is a common issue in active learning.  This can bias the selection of points, since the point-wise contribution to G(S) is not necessarily additive.  See work by [Farquahr et al 2021](https://arxiv.org/abs/2101.11665) for an example in the case of using uncertainty to acquire labels.  A test to see how vulnerable G(S) is to this phenomenon would be to run selection with $b = 1$, and then with $b$ increasing in various intervals, to see how frequently the single points acquired with $b = 1$ appear in the  set of $b$ points acquired in a single batch selection.

Line 154: I presume that $\mathcal{K}^{ij}$ is the empirical NTK, but it would help the reader to specify what it represents, as it’s not super clear by the derivations from lines 149 - 155.

Lines 176-178: While using an IF derived acquisition function makes some sense (in the sense that high influence points will by identification provoke large magnitude changes in the model parameters), it’s not clear that it’s a better or more valuable way to acquire points.  

Line 194: “of” missing here

Lines 217-219: In theorem 1, the factor $\nu$ will change at $t -> \infty$, since it depends on the reciprocal of $n^2$.  Is this accounted for in the proof?

Line 260: I would reformulate this sentence here, since evaluating one experiment for two query rounds on one network and dataset does *not* do much to convince the reader that Lemma 2 holds.  I think the authors should broaden the datasets they use to establish the validity across other datasets, especially with different class imbalances.

Line 263: This figure is nice, but it lacks some context.  How good is the correlation between the training dynamics proxy and alignment?  What would help readers understand this better would be a comparison of different acquisition functions and how they correlate with alignment.  This correlation argument would become much stronger.

Section 5: There are two key points missing in the empirical analysis of dynamicAL versus other acquisition functions.  

The first is an analysis of the degree of overlap between the points selected by dynamicAL and other methods; how many of the same points are chosen, and does the membership of the sets of acquired points converge over time, or do they diverge as successive rounds of acquisition take place?

The second is that in both figure 3 and 5 we see only the means but not the variances of each set of retraining experiments.  I suspect that there are two components contributing to the performance of each algorithm: first is the selection of the points acquired, as well as the smaller differences in training dynamics for each network due to initialization, batch order in which the data is presented to the models, or even GPU noise.  It would be more convincing to see error bars, so that we can gauge how much of an effect the selection of points has on the accuracy.
questions: Lines 284-285: I would recommend trying this out on datasets with more severe class imbalances.  Each of CIFAR10, SVHN and Caltech 101 are rather well behaved and don’t exhibit any class imbalances, making them odd choices for active learning.  Perhaps this is why there does not seem to be much of a drastic difference in the results of Figure 3?

Line 162: The use of pseudo labeling in this paper connects this work to recent work on self-supervised learning.  I wonder if the authors have considered the implications of what current theories of self-supervised learning can do to inform this work, or what this work could do to transform a self-supervised learning method into a few-shot method that would preform better?

limitations: Yes, they have.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors prove that convergence speed of training and generalization are positively correlated. Based on this observation, the authors proposed a novel active learning algorithm (dynamicAL), which maximizes training dynamics. DynamicAL is theoretically motivated and generalizes existing methods such as uncertainty sampling methods and influence function methods.

strengths_and_weaknesses: Originality:

The paper examines the training dynamics of Neural Tangent Kernel, which is suitable for theoretical analysis. The authors proved that convergence speed and generalization are positively correlated.
The authors proposed a new objective for an active learning algorithm: optimize the speed of training convergence.

Quality:
The results are novel and interesting. However, the quality of the bound is not clear. For example, the authors introduce the notion of label alignment and show that label alignment is correlated with convergence and generalization. Based on this correlation, the authors conclude that convergence and generalization are positively correlated. While it is logical, I believe it oversimplifies the dependency between convergence and generalization given that the bound is an approximation and the quality of the bound was not assessed.
Experimental results can be improved by measuring performance for all rounds (> 10 rounds until the training set is exhausted). Currently, the authors evaluate and compared methods for less than 10 query rounds. It is not clear if the proposed method outperforms the baselines in all rounds.
The improvement is rather small (often less than 1%).

Clarity:
In general, the paper is easy to read. However, its flow and presentation can be improved. For example, the authors first present the method and later present a theoretical analysis of “Train faster → generalize better”. I suggest that some of the theoretical results can be presented together with the method to improve the presentation quality. Other, unnecessary lemmas should be moved to the appendix. Then, the authors can expand the theoretical section and discussion of related work sections.

Significance:
The authors’ idea of optimizing for convergence speed is interesting and of potential significance, as it can be explored by a wider community in other fields. However, the authors should improve the presentation and clarify of the paper, while also updating experimental results.

questions: Can you compare the proposed method with other baseline methods for rounds > 10?

Can you discuss the tightness of the bound in the relationships between convergence and generalization?

limitations: Yes
review_title: null

Meta-review: metareview: It is the consensus of the reviewers that this paper makes a worthwhile contribution to active deep learning. The author(s)' idea of optimizing for convergence speed is interesting and of potential significance. The meta-reviewer would recommend acceptance of the paper as a poster.
confidence: Certain
Decision: Accept