Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: ### After rebuttal ###
Thanks a lot for the authors' extensive experiments and good explanation to my questions. I would increase my score. The basic idea of this paper is promising and useful. However, there are still several problems after reading the rebuttal. 

Figure 2 shows that GD can distinguish different noisy levels, however, it is not a very realistic setup when training with a noisy dataset, to be specific, the dataset only has one noisy lever rather than multiple. Furthermore, GD is not able to give an early-stopping criterion on noisy datasets from Figure 2 where test error keeps decreasing but GD is increasing. Including noisy datasets analysis seems not a significant contribution.

### Original comment ###
This paper aims to provide an early stopping criterion measured by gradient disparity when training with limited data.  The authors also provide theoretical insights on inducing the gradient disparity and empirically show the proposed method is robust to label noise.

However, there are several points not clear to me.
1. In the main content, comparison between CV and GD are all based on a 1.28K dataset from CIFAR100/10 and MNIST, is there an experiment showing the performance on the full dataset baseline with label noise. 
2. Regarding Figure 9 in the appendix, the figure failed to explain the correlation between GD (2nd column) and test accuracy (4th column) where GD goes up. Still, accuracy has various behaviors. Is the method *only* work with a small dataset?
3. Based on Figure 3, I assume the authors do not use data augmentation in their experiment (ResNet18 has 78% accuracy on full CIFAR10); however, data augmentation is a very basic technic in model training. Will data augmentation affects the performance of GD?
4. Figure 2 is not clear to me. What is the difference between Test error and Generalization error? How do you compute them? In Figure2. (b), the scale of the Y-axis seems too large. Nothing can be observed from this figure.
5. Although the authors state the correlation \pho in their results, there's no explicit figure showing the correlation in main content like Figure 13. I believe adding them can be a good bonus.
review_title: Good idea but need improvement on explaination and exepriments

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes using gradient disparity between two batches for early stopping, and explains the reason by showing its connection with the generalization error. Experiments on limited-size dataset and noisy dataset are presented. 

My main concern is related to the experimental setting: The experiments in Section 5 compares 

(a) k-CV with (1-1/k)N training samples + N/k validation samples; with

(b) Gradient Disparity (GD) using  N training samples. 


Why not also compare with 

(x1) Gradient Disparity (GD) using (1-1/k)N training samples; or maybe even

(x2) use k-CV to determine stopping epoch, take an average to estimate the best stopping epoch \hat{n}, then re-train using all samples and stop at epoch \hat{n}. 

It seems unclear to me whether the advantage of GD comes from (i) better characterization of the generalization or (ii) sample size advantage. 

(x1) v.s. (a) and (x2) v.s. (b) could show whether GD better captures the generalization under same number of samples. 

(x1) v.s. (b) and (x2) v.s. (a) could show the benefit of increasing sample size. 

Finally, the experimental setting uses k-fold CV instead of a fixed validation set, and it is not clear what the standard deviation of the experimental results for k-CV means, e.g., the standard deviation describes (i) randomness due to data splitting; or (ii) randomness due to training algorithm? 
review_title: On the fairness of experimental comparison between CV and GD due to different sample size

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:
The paper proposed to use the average of l_2 distance between stochastic gradients called gradient disparity as a metric to predict generalization. Early stopping is achieved by monitoring such a metric without needing a validation set. Some theoretical results are also given to motivate the use of gradient disparity as a generalization metric.

Pros:
Overall the paper is well written. The use of a generalization metric to replace the validation set is an interesting idea. From the experiments in the paper, it seems the proposed metric indeed shares a similar trend as the test error. Also, the paper compared with a few other generalization metrics in Appendix H and showed the proposed one performs better than the baseline metrics when used as early stopping criteria. The experiments look quite comprehensive to me and the effects of different factors (label noise, batch size, network width, etc) on the gradient disparity are studied. 

Cons:
1. It looks like gradient disparity can be more correlated to generalization error instead of test error on some datasets (e.g., in Figure 13 for MNIST). This could make the algorithm stop too early since in some cases, the generalization error is increasing, but the training error decreases even faster and overall the test error is decreasing. However, gradient disparity has a similar trend with generalization error and when it increases for 5 epochs, we will terminate the algorithm while the test error is still decreasing. In addition, using test error + gradient disparity as a proxy for test error is not valid since gradient disparity has a different scale instead of while test error is between 0 and 1.

2. The scale of gradient disparity may change with gradient magnitude and the authors used a re-scaling heuristic to stabilize the scale. I think the metric scale is an important issue when the metric is used for early stopping. However, the effect of re-scaling is not comprehensively studied and discussed in the experiments. 



review_title: A new generalization metric as an early stopping criterion

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a novel early-stopping criterion called gradient disparity, which is the the l2 norm of the difference between two gradient vectors on two different batches from the training set. In contrast to typical early stopping techniques that require validation error on a held-out dataset, the proposed criterion fully operates on the training set. 

The gradient disparity is theoretically motivated by an upper bound of the newly introduced concept called “generalization penalty”, which measures how much the loss on a batch of points increases due to model updating with another batch instead of itself. The upper bound takes the form of KL divergence between the two posterior model distributions conditioned on the respective batches. The posterior distributions are assumed to be Gaussian with mean being the gradient-updated weights, hence the KL divergence boils down the l2-norm difference between the gradient vectors of the two batches. 

In practice, the algorithm take, say, five batches and compute the average pair-wise GD as the early-stopping criterion, where the GD is computed with the loss values of each point rescaled by the standard deviation of the loss values in the batch. 

Overall I vote for accept. 

Pros: 

The method appears to be well motivated both theoretically and intuitively; empirically results show that the proposed gradient disparity strongly correlates with generalization error. The experiments are quite extensive. 

Cons: 

There are some aspects not clear to me. What exactly is your early-stopping algorithm? Do you randomly sample, e.g., five batches, from the training set after each model update, and then compute the pairwise GD and then average? Do you early-stop when the GD metric increases, or there is some kind of threshold (I suppose this metric would be noisy)?    

As a sanity check, maybe add an experiment comparing early-stopping with no early-stopping?

review_title: theoretically motivated and easy-to-compute metric for early stopping using only training set, extensive experiments 

Meta-review: This paper proposes an early stopping strategy based on the disparity of gradients between two batches from the *training set*. Such a criterion would make the held-out validation set unnecessary. The idea is motivated by theoretical arguments and benchmarked on experiments, but some issues still need to be worked on. 

Regarding theory, the theorems here assume implicitly the independence of the gradients computed on two different batches of training data, but the conditions where gradients on independent examples computed *on trained weights* are independent (or close to being independent) should be discussed. Regarding experiments, the protocol is unusual in that the proposed stopping criterion is compared to a stopping criterion relying on k-fold cross-validation, instead of the usual stopping criterion on held-out validation. What is the motivation for this protocol? Why should we expect a small variability in the optimal number of iterations over the k runs?  In addition, the experiments consider a normalized definition of gradient disparity for which no theory is provided. Although there is an interesting correlation between this normalized gradient disparity and generalization error, this link does not seem strong enough to pick the right number of iterations. 

Detail: 
Still regarding independence, reporting the empirical standard errors on k-fold cross-validation is debatable since it is not related to the theoretical standard error (see e.g. [Bengio et al.: No Unbiased Estimator of the Variance of K-Fold Cross-Validation. J. Mach. Learn. Res. 5: 1089-1105 (2004)])

Decision: Reject