Early Stopping by Gradient Disparity
Authors: mahsa forouzesh
Patrick Thiran
Venue:  (2021)
Keywords: Supervised Representation Learning
Deep Neural Networks
Generalization
Early Stopping

Abstract: Validation-based early-stopping methods are one of the most popular techniques used to avoid over-training deep neural networks. They require to set aside a reliable unbiased validation set, which can be expensive in applications offering limited amounts of data. In this paper, we propose to use \emph{gradient disparity}, which we define as the $\ell_2$ norm distance between the gradient vectors of two batches drawn from the training set. It comes from a probabilistic upper bound on the difference between the classification errors over a given batch, when the network is trained on this batch and when the network is trained on another batch of points sampled from the same dataset. We empirically show that gradient disparity is a very promising early-stopping criterion when data is limited, because it uses all the training samples during training. Furthermore, we show in a wide range of experimental settings that gradient disparity is not only strongly related to the usual generalization error between the training and test sets, but that it is also much more informative about the level of label noise.  

Under review as a conference paper at ICLR 2021
EARLY STOPPING BY GRADIENT DISPARITY
Anonymous authors Paper under double-blind review
ABSTRACT
Validation-based early-stopping methods are one of the most popular techniques used to avoid over-training deep neural networks. They require to set aside a reliable unbiased validation set, which can be expensive in applications offering limited amounts of data. In this paper, we propose use gradient disparity, which we define as the & norm distance between the gradient vectors of two batches drawn from the training set. It comes from probabilistic upper bound on the difference between the classification errors over given batch, when the network is trained on this batch and when the network is trained on another batch of points sampled from the same dataset. We empirically show that gradient disparity is very promising early-stopping criterion when data limited, because it uses all the training samples during training. Furthermore, we show in wide range of experimental settings that gradient disparity not only strongly related to the usual generalization error between the training and test sets, but that it is also much more informative about the level of label noise.
INTRODUCTION
Early stopping is a commonly used regularization technique to avoid under/over fitting deep neural networks trained with iterative methods, such as gradient descent (Prechelt) 1998: Yao et al.) [007]] Gu al., 2018). To have unbiased proxy on the generalization error, early stopping requires a separate accurately labeled validation set. However, labeled data collection is an expensive and time consuming process that might require domain expertise (Roh al.] 2019). Moreover, deep learning is becoming popular to use for new and critical applications for which there is simply not enough available data. Hence, it advantageous to have signal of overfitting that does not require a validation set, then all the available data can be used for training the model.
Let S1 and S2 be two batches of points sam- pled from the available (training) dataset. Sup- pose that Si is selected for an iteration (step) of stochastic gradient descent (SGD), which then updates the parameter vector to W1- The aver- age loss over S₁ is in principle reduced, given a sufficiently small learning rate. However, the average loss over the other batch Sa (i.e., Ls, (hw,)) )) is not as likely to be reduced. It will remain on average larger than the loss com- puted over S2, if it was Sn instead of S₁ that had been selected for this iteration (i.c., Ls, (hw,) )). The difference is the penalty R2 that we pay for choosing S₁ over S2 (and similarly, R2 is the penalty that we would pay for choosing S2 over S)). R₂ is illustrated Figure [ for a hypo- thetical non-convex loss as a function of a one dimensional parameter. The expected penalty measures how much, in an iteration, model updated on one batch (S1) is able to generalize on average another batch (S2) from the dataset.
L52
L
Loss
L (hwn)
R₂
(t+1)
w (441)
10
Figure 1:
An illustration of the penalty term R2, where the y-axis is the loss, and the x-axis indi- cates the parameters of the model. Ls, and Ls, are the average losses over batches Sj and S2, re- spectively. (t()) is the parameter at iteration & and wift (((+))) is the parameter at iteration + 1 if batch S; was selected for the update step at iteration 4, with E (1,2).
Hence, call R. the generalization penalty.

---

Under review as a conference paper at ICLR 2021
We establish probabilistic upper- bound on the sum of the expected penalties E [R1] E [R2] by adapting the PAC-Bayesian framework (McAllester 1999a b 2003) given a pair of batches S and S2 sampled from the dataset (Theorem D Interestingly, under some mild assumptions, this upper bound is essentially a simple expression driven by l19 - 92ll2- where fi and 92 are the gradient vectors over the two batches S1 and S2, respectively. We call this gradient disparity: it measures how a small gradient step on one batch negatively affects the performance on another one.
Gradient disparity is simple use and it is computationally tractable during the course of train- ing. Our experiments on state-of-the-art configurations suggest very strong link between gradient disparity and generalization error; we propose gradient disparity as an effective early stopping cri- terion. Gradient disparity is particularly useful when the available dataset has limited labeled data, because it does not require splitting the available dataset into training and validation sets so that all the available data can be used during training, unlike for instance k-fold cross validation. We observe that using gradient disparity, instead of an unbiased validation set, results in at least 1% predictive performance improvement for critical applications with limited and very costly available data, such as the MRNet dataset that is a small size image-classffication dataset used for detecting knee injuries (Table IT..
Task
Method
Test loss
Test AUC score (in percentage)
5-fold CV
0.284 + 0.016 (0.307 + 0.057)
71.016 = 3.66 (87.44 + 1.35)
abnormal
GD
0.274 + 0.004 (0.275 + 0.053)
72.67 : 3.85 (88.12 + 0.35)
5-fold CV
0.973 = 0.111 (1.246 + 0.142)
79.80 = 1.23 (89.32 + 1.47)
ACL
GD
0.842 = 0.101 (1.136 0.121)
81.81 = 1.64 (91.52 = 0.09)
5-fold CV
0.758 = 0.04 (1.163 + 0.127)
73.53 = 1.30 (72.14 = 0.74)
meniscal
GD
0.726 = 0.019 (1.14 = 0.323)
74.08 = 0.79 (73.80 = 0.24)
Table 1:
The loss and area under the receiver operating characteristic curve (AUC score) on the MRNet test set (Bien et al. 2018), comparing 5-fold cross validation (5-fold CV) and gradient dis- parity (GD), when both are used as early stopping criteria for detecting the presence of abnormally. ACL tears, and meniscal tears from the sagittal plane MRI scans. The corresponding curves during training are shown in Figure 10 The results of early stopping are given, both when the metric has increased for 5 epochs from the beginning of training and between parenthesis when the metric has increased for 5 consecutive epochs.
Moreover, when the available dataset contains noisy labels, the validation set no longer a reliable predictor of the clean test set (see e.g.. Figure | (a) (left)), whereas gradient disparity correctly pre- diets the performance on the test set and again can be used as a promising early-stopping criterion. Furthermore, we observe that gradient disparity is better indicator of label noise level than general- ization error, especially at early stages of training. Similarly to the generalization error, it decreases with the training set size, and it increases with the batch size.
Paper Outline. Section 2 we formally define the generalization penalty. In Section 3 we give the upper bound on the generalization penalty. In Section 4 we introduce the gradient disparity metric. In Section [5] we present experiments that support gradient disparity as an early stopping criterion. In Section [ we assess gradient disparity as generalization metric. Finally, in Section 7 we further discuss the observations and compare gradient disparity to related work. A detailed comparison related work is deferred to Appendix[H] For our experiments, we consider four image classification datasets: MNIST, CIFAR-1O, CIFAR-T00 and MRNet, and we consider a wide range of neural network architectures: ResNet, VGG, AlexNet and fully connected neural networks.
2 GENERALIZZTION PENALTY
Consider a classification task with input E X == Rn and ground truth label y E 21, k).
where A is the number of classes. Let hw E H X' + y = R² be a predictor (clas- sifier) parameterized by the parameter vector 1 (z), y) = 1 [x)]()) < max h [x] for all h E H and (z, E X x 21, ... k).. The expected loss and the empirical loss over the training set S of size are respectively defined as
E Rd. and I(:,-) be the 0-1 loss function
2

---

Under review as a conference paper at ICLR 2021
m
I(hro) = ( (hww))) v)]
and
Ls(ww) =
(2x),
(1)
where D is the probability distribution of the data points and (I;; M4) are i.i.d. samples drawn from S D Ls (kw) is also called the training classification error. Similar to the notation used in (Diiugaite & Roy| 2017), distributions on the hypotheses space H. are simply distributions on the underlying parameterization. With some abuse of notation, VLs, refers to the gradient with respect to the surrogate differentiable loss function, which in our experiments is the cross entropy.
In mini-batch gradient descent (SGD) setting, consider two batches of points, denoted by S₁ and S2, which have respectively my and m2 number of samples, with m. + m2 I m. The average loss functions over these two sets of samples are (hm.) and Ls, (h.),, respectively. Let w = w(() be the parameter vector at the beginning of an iteration L. If S1 is selected for the next iteration, w gets updated to (+++1) with
W1 = w 10--1 Ls,, (Nir),
where y is the learning rate. Conversely, if S2 had been selected instead of S1. the updated param- eter vector at the end of this iteration would have been W22 = w 7 Ls, (frz) ). Therefore, the generalization penalty on batch S2 is defined as R2 Lss, (hwz) Lsg (hwr)) which is the gap between the loss over S2, Ls, (hwn), and its target value, Ls, (, at the end of iteration t.
When selecting S for the parameter update, Equation (2) makes step towards learning the input- output relations of batch Sr. If this negatively affects the performance on batch S2, R2 will be large; the model is learning the data structures that are unique to S and that do not appear in S2- Because S₁ and S2 are batches of points sampled from the same distribution D, they have data structures in common. If, throughout the learning process, we consistently observe that, in each update step, the model learns structures unique to only one batch, then it is very likely that the model is memorizing the labels instead of learning the common data-structures. This captured by the generalization penalty R.
3 BOUND ON THE GENERALIZATION PENALTY
We adapt the PAC-Bayesiaa framework McAAllstter 1999a b) to account for the trajectory of the learning algorithm; For each learning iteration we define a prior, and two possible posteriors depend- ing on the choice of the batch selection. Let w ~ P be an initial parameter vector that follows prior distribution P which is F--measurable function, where F, denotes the filtration of the available information at the beginning of iteration f. Let hwy hug be the two learned single predictors, at the end of iteration t, from S and S2, respectively. In this framework, for E {1, 2). each predictor hw, is randomized and becomes he, with 1/1 w; + ug. where u, is random variable whose distribution might depend on S,. Let Q; be the distribution of Ds, which is a distribution over the predictor space H that depends on S, via wi and possibly u,. Let Gj be a- a-field such that (Sa) U.F G; and that the posterior distribution Q; is G.-measurable for E {1,2}. We further assume that the random variable in Qi is statistically independent from the draw of the batch S2 and, vice versa, that U2 ~ Q2 is independent from the batch S S i.e.ie,,, 91 IL o(2)) and G2 11 (S1).
Theorem 1. For any 8 E (0, 1}, with probubility at least ô over the sampling sets sets Si and S2. the sum of the expected penalties conditional on S₁ and S2, respectively, satisfies
2KL(Q21 + 21 2upa
(KL(Q1))Q2) +2 2m1
E R E
(3)
m2 -
m1 2
Theorem I whose proof is given in Appendix B shows why generalization penalties are better suited to our setting where the two batches S1 and S2 are both drawn from the training set S than the usual generalization errors. After iteration, the network learns posterior distribution Q on its parameters from S,, yielding to the parameter vector
Q1- The expected generalization
Batches S1 and S2 are drawn without replacement, and the random selection of indices of batches S1 and S2 is independent from the dataset S. Hence, similarly to Negrra et al. 2019); Dziugaite al. (2020), we have (Si) II. (82).
3

---

Under review as a conference paper at ICLR 2021
error at that time is defined GE₁ EvinQ; [L(hr,]] }] Bnnn Ls, (hvn )]. In practice, (( is estimated by the test loss over a batch of unseen data, which is independent from 1/1 ~ Q1- If S2 is this batch, then ther"GE, GE, z Evi~Q. [Ls, (h,,, )1 - Eu,~q, [Ls, (hv,), )] However, this estimate requires to set S2 aside from S not only during that step but also during all the previous steps, because otherwise the model hyg would not be independent from S2, making the estimate of GE, biased. Therefore S₂ must be sampled from the validation set, and cannot be used during training. In contrast, Theorem iss valid even if the trained model hu, depends on the samples within the batch S2. Therefore, the bound on the sum of the (expected) generalization penalties does no longer require to set S2 aside from S in previous iterations: all data previously reserved for validation can now be used for training. This is what makes these penalties appealing to measure generalization especially when the available dataset is limited and/or noisy, as we will see in Section [
Theorem D remains valid if batch S2 was sampled from the validation set, in which case it can be compared with known generalization error (GE) bounds, as now hy, does not depend on samples of S2. Similarly to GE,, let GE2 be the generalization error when S2 is the training set, while S is the test set. By adding GE, and GE2 we obtain E [R,] + E [R2]. hence Theorem [ alss upper bounds an estimate of GE, + GEg. We could have obtained another upper bound by directly applying the bounds from (McAllester 2003
Neyshabur et al. 2017b), which gives
2KL((Q21|)) + 21
2una o
2KI(Q: + 21n 2m11 8
IE [R]] +E [22] 21
+ 21
(4)
M2 -
ml
The main difference between Equations 3 and (4 is that the former needs the difference only be- tween the two posterior distributions, Q1 and Q2, whereas the latter requires the difference between the prior distribution P and the posterior distributions Q1 and Q2. Besides the minor difference of the multiplicative factor 2, the upper bound in Equation (3) is non-vacuous for larger class of distributions than the upper bound Equation 4 When Q and Q2 are close to each other but not to P. the upper bound in Equation 3 is much tighter than the one in Equation (4). Moreover, in the next section, we show that, under reasonable assumptions, the upper bound in Equation (3) boils down to very tractable generalization metric that we call gradient disparity.
4 GRADIENT DISPARITY
The randomness modeled by ui conditioned on the current batch S,, comes from (i) the parameter vector at the beginning of the iteration w, which itself comes from the random parameter initializa- tion and the stochasticity of the parameter updates until that iteration, and (ii) the gradient vector Lss. which may also be random because of the possible additional randomness the network structure due for instance to dropout (Srivastava et al. 2014). A common assumption made in the literature is that the random perturbation и; follows a normal distribution (Bellido & Fiesler 1993] Neyshabur al. 20176). The upper bound in Theorem [ takes a particularly simple form if we assume that for (u, (O, o² r)), and that w; is fixed, as in the setting of (Dziugaite & Roy 2017). <l.(QI||2> is then the KL--divergence between two multivariate normal distributions.
{1,2} the random perturbations u, are zero mcan i.i.d. normal distributions
Let us denote Lss, (hw) by 91 E Rd and LLs, (hw) by I2 E Rd.. As w; w 22g for E {1. 2}. the KL-divergence between Q N(w,, o² I) and Q2 ~N o² (Lemma 1 in Appendix A simply
1
KL
= 2 0 |6 - 92ll2
102--92122 = (L(Q211Q1).
(5)
which shows that, keeping a constant step size y and assuming the same variance for the random perturbations o² in all the steps of the training, the bound in Theorem I is driven by ll91 92ll2-
Moore formally,
GE Bun Lss (hs, En [ss, (he, }] + (Bm [L(hr, )] - Emnaei (Lss (he, I)) where from Hoeffding's bound (Theorem in Appendix A P([| 2 t) S exp (-2mpt?) and GE, is approx- imated with the first term.
4

---

Under review as a conference paper at ICLR 2021
This indicates that the smaller the Eg distance between gradient vectors is, the lower the upper bound on the generalization penalty is, and therefore the closer the performance of a model trained on one batch is to model trained on another batch.
For two batches of points S; and SJ. with gradient vectors Jr and 9j. respectively, we define the gradient disparity (GD) between S; and Sj as
(6) Gradient disparity is empirically tractable, and provides a probabilistic guarantee the of the generalization penalties of S, and SJ. modulo the Gaussianity assumptions made in this section. Gradient disparity be computed within batches of the training or the validation set. As discussed in 3 we focus on the first case to have a generalization metric that does not require validation data and that provides an early stopping criterion with all the available data used for training.
Di, = l9 -9
We focus on the vanilla SGD optimizer. In Appendix G we extend the analysis to other adaptive optimizers: SGD with momentum (Qian 1999), Adagrad (Duchi et al.) 2011), Adadelta (Zeiler) 2012), and Adam (Kingma & Ba 2014). In all these optimizers, we observe that gradient disparity (Equation (6)) appears (L(Q1 Q2) with other factors that depend on a decaying average of past
gradient vectors. Experimental results support the use of gradient disparity as an early stopping metric also for these popular optimizers (see Figure 22 Appendix Gi..
Computing the gradient disparity averaged over B batches requires all the B gradient vectors at each iteration, which computationally expensive if B is large. We approximate it by computing it over only a much smaller subset of the batches, of size < B, D Σi= Ej=1,y Dig/s(s In the experiments presented in this paper, = 5; we observed that such a small subset is already sufficient (see Appendix C.2 for an experimental comparison of different values of 8). We also present an alternative approach that relies on the distribution of gradient disparity instead of its average in Appendix F to have a finer-grain signal of overfitting.
1).
As training progresses, the gradient magnitude starts to decrease, and therefore the value of gradient disparity might decrease not necessarily because the distance between two gradient vectors is de- creasing, but because their magnitudes of training. we re-scale the loss values within each batch, before computing gradient disparity in D (refer to Appendix C.T for more details). Moreover, we consider the mean square error (MSE) for the choice of the surrogate loss in Appendix correlated with the MSE test loss well.
decreasing. Hence, in order to compare different stages
C.3 C.3 and we observe that gradient disparity is positively
5 GRADIENT DISPARITY AS AN EARLY STOPPING CRITERION
Comparison to k-fold Cross Validation. Early stopping is popular technique used in practice to avoid overfitting (Prechelt 1998] Yao et al. 2007 Gu et al. 2018). The optimization is stopped when the performance of the model the training set. Early stopping is of particular interest in the presence of label noise, because the model first learns the samples with correct labels, and next the corrupted samples (Li al. 2019). To emphasize the particular application of gradient disparity. we compare it to k-fold cross validation in two settings: (i) when the available dataset is limited and (ii) when the available dataset has corrupted labels. We simulate the limited data scenario by using a small subset of three image classification benchmark datasets: MNIST, CIFAR-10 and CIFAR-100, and the noisy labeled data scenario is simulated by using a corrupted version of these datasets. We also evaluate gradient disparity on medical dataset (MRNet dataset) with limited available data and in this setting, we use the entire dataset for training.
validation set starts diverge from its performance on
(i) We compare gradient disparity with k-fold cross validation (Stone 1974h used as an early stop- ping criterion in Table (top) when there is limited labeled data. We observe that gradient disparity performs well as an early stopping criterion, especially when the data is complex (CIFAR- -00 is more complex than CIFAR-10). As it uses every available sample, instead of only 1 1 portion of the dataset, it results in a better performance on the final unseen (test) data (see also Table 4 and Figure X in Appendix[] (D.
In many real-world applications. collecting (labeled) data is very costly. In some medical applica- tions, it requires high costs of patient data collection and medical staff expertise. For an example
5

---

Under review as a conference paper at ICLR 2021
of such application, we consider the MRNet dataset (Bien al. 2018), which contains limited number of MRI scans to study the presence of abnormally, ACL tears and meniscal tears in knee injuries. We observe that using gradient disparity instead of validation set, results in over 1% im- provement (on average over all three tasks) in the test AUC score, and therefore additional correct detection for more than one patient for each task (see Tad Figure TQ Appendix (D).
(ii) When the labels of the available data are noisy, the validation set is no longer a reliable estimate of the unseen set (this can be clearly observed in Figure (left column)). Nevertheless, and although it is computed over the noisy training set, gradient disparity reflects the performance on the test set quite well (Figure / (middle left column)). As a result (see Table 2 (bottom)), gradient disparity performs better than k-fold cross validation as an early stopping criterion. The same applies to two other datasets (see Table 6 and Figure Appendix D
Label noise
Method
Test loss
Test accuracy
Top-5 test accuracy
5-fold CV
4.249 = 0.028
6.79 = 0.49
22.19 + 0.77 27.84 + 1.30
0%
GD
4.057 + 0.043
9.99 1 0.92
10-fold CV
5.023 = 0.083
1.59 = 0.15
6,47 + 0.52
50%
GD
4.463 + 0.038
3.68 + 0.52
15.22 + 1.24
Table 2: The final test loss and accuracy when using gradient disparity (GD) and k-foold cross vali- dation (CV) as early stopping criteria, (top) when the available dataset is limited and (bottom) when the available data has noisy labeled samples. To simulate limited-data scenario, we consider training set a subset of 1280 samples of the CIFAR-100 dataset. The configurations in the top row and the bottom row ResNet-34 and ResNet- 188, respectively. In both methods, the optimization is stopped when the metric (validation loss or GD) increases for 5 epochs.
VALIDATING GRADIENT DISPARITY AS A GENERALIZATION METRIC
0% latel noise
Generalization enor
Gradient disparity
25%
25% label noise
25% label noise
30% lobel noise
139
50% label hoise
75t
75% label noise
75% label nuie
20
10
10' terations
10'
herations
teeaaiinn
(a) Test error
(b) Generalization error
(c) D
Figure 2: The error percentage and D during training with different amounts of randomness in the training labels for an AlexNet trained on subset of 12.8 points of the MNIST training dataset. Pearson's 's correlation coefficient between gradient disparity and test error (TE)test loss (TL) over all the iterations and over all levels of randomness are PD,TE = 0.861 and PD.IL = 0.802. The generalization error (gap) is the difference between the train and test errors.
In this section, we demonstrate that factors that contribute to improve or degrade the generalization performance of model (e.g., label noise level, training set size and batch size), have an often strikingly similar effect on the value of gradient disparity as well.
Label Noise Level. Deep neural networks, trained with the SGD algorithm, achieve excellent gen- eralization performance (Hardt et al., (2015), while achieving zero training error on randomly labeled data in classification tasks (Zhang et al. (2016). Understanding what distinguishes the model when it is trained on correct labels and when is trained on randomly labeled data is still an evolving area of research. We conjecture that as label noise level increases, the gradient vectors diverge more. Hence, when the network is trained with correctly labeled samples, the gradient disparity is low, whereas when it is trained with corrupted samples the gradient disparity is high. The experimental results support this conjecture in a wide range of settings and show that gradient disparity is indeed very sensitive to label noise level (see also Figures 12
1.5 19
and 20)

---

Under review as a conference paper at ICLR 2021
T the test enror for networks trained with different amounts of label noise. Interestingly, observe that for this setting the test error for the network trained with 75% label noise remains relatively small, indicating the good resistance of the model against memorization of corrupted samples. As suggested both from the test error (Figure 2
(a)) and the average gradient disparity (Figure (c)), there is no proper early stopping time for these experiments. The generalization error (Figure 2 (b)) remains close to zero, regardless of the level of label noise, and hence fails to account for label noise. In contrast, the average gradient disparity is very sensitive the label noise level in all stages of training as shown in Figure 2 (c), as desired for a metric measuring generalization.
Training Set Size. The test error decreases with the size of the training set (Figure[]]eeft) and a reliable generalization metric should therefore reflect this property. Many of the previous metrics fail to do so, as shown by (Neyshabur et al. 2017aa Nagarajan & Kolter 2019). In contrast, the average gradient dispar- ity indeed clearly decreases with the size of the training set, as shown in Figure (right) (see also Figure 17 in Appendix
+ Restiet 18, CIPA-13
+ Neshet-18, CFAR-D
Grodeemy
Tarning S01
Tartnng Sot 5000
The test error (T and average gradient disparity (D) for networks that are trained (until reaching the training loss value of 0.01) over train- ing sets with different sizes. We observe a very strong positive correlation: PD. TR 0.984.
Figure 3:
Batch Size. In practice, the test error increases with the batch size (Figure We observe that gradient disparity also increases with the batch size (Figure([rrigh))) This observation is counter-intuitive because one might expect that gradient vectors get more similar when they are averaged over a larger batch. This might be the explanation behind the decrease in gradient dis- parity from batch size 256 to 512 for the VGG- 19 network. Observe also that gradient dispar- ity correctly predicts that VGG-19 generalizes better than ResNet-34 for this dataset. Gradient disparity matches the ranking of test errors for different networks, trained with different batch sizes, long as the batch sizes are not too large (see also Figure 18 in Appendix
Resttut VGG-19
RasMo6-34
Betth
120
Dotch 122
254
Figure 4: The test error and average gradient dis- parity for networks that are trained with different batch sizes. A ResNet-34 and VGG-19 net- work that are trained on the CIFAR-IO dataset. The correlation between D and test error (TE) for ResNet-34, VGG-19, and both graphs com- bined are PD.
0.985, PD, 0.926, and PD. TE 0.893, respectively.
Width. In practice, the test served to decrease with the network width. We observe that gradient disparity (normalized with respect to the number of parameters) also decreases with network width for ResNet, VGG and fully connected neural networks that are trained on the CIFAR- 10 dataset (see Figure 14jin Appendix EE.2)
has been ob-
7 DISCUSSION AND RELATED WORK
Finding a practical metric that completely captures the generalization properties of deep neural net- works, and in particular indicates the level of randomness in the labels and decreases with the size of the training set, is still an active research direction (Dziugaite & Roy| 2017 Neyshabur et al.] 2017aj Nagarajan & Kolter 2019). A very recent line of work assesses the similarity between the gradient updates of two batches (samples) in the training set. The coherent gradient hypothesis (Chatterjee) 2020) states that the gradient is stronger in directions where similar examples exist and towards which the parameter update is biased. He & Su (2020) presents the local elasticity phenomenon, which measures how prediction over sample changes, the network is updated on another sample. The generalization penalty introduced in our work measures how the prediction over one sample (batch) changes when the network is updated the same sample instead of being updated on another sample, which can signal overfitting implicitly within the training set.
Tracking generalization by measuring the similarity between gradient vectors is particularly ben- eficial as it is empirically tractable during training and does not require access to unseen data. Sankararaman et al. (2019) proposes gradient confusion, which is a bound on the inner product
7

---

Under review as a conference paper at ICLR 2021
of two gradient vectors, and shows that the larger the gradient confusion is, the slower the conver- gence takes place. Gradient interference (when the inner product of gradient vectors is negative) has been studied in multi-task learning, reinforcement learning and temporal difference learning (Riemer et al. 2018 Liu et al., 2019: Bengio et al., 2020). Yin et al. (2017) studies the relation between gradient diversity, which measures the dissimilarity between gradient vectors, and the con- vergence performance of distributed SGD algorithms. Fort et al. (2019) proposes a metric called stiffness, which is the cosine similarity between two gradient vectors, and shows empirically that it is related to generalization. Fu et al. (2020) studies the cosine similarity between two gradient vectors for natural language processing tasks. Mehta et al. (2020) measures the alignment between the gradient vectors within the same class (denoted by S2,), and studies the relation between Q2 and generalization as the scale of initialization increased.
Another interesting line of work is the study of the variance of gradients in deep learning settings. Negrea et al. (2019) derives mutual information generalization error bounds for stochastic gradient Langevin dynamics (SGLD) as function of the sum (over the iterations) of square gradient incoher- ences, which is closely related to gradients variance. Two-sample gradient incoherences also appear in |Haghifam et al. 22200), there are taken between training sample and "ghost" sample that is not used during training and therefore taken from a validation set (unlike gradient disparity). The upper bounds in Negrea et al. (2019); Haahhffmm et al. (2020) are not intended to be used early stopping criteria and are cumulative bounds that increase with the number of iterations. As shown in Appendix [ gradient disparity can be used as an early stopping criterion not only for SGD with additive noise (such as SGLD), but also other adaptive optimizers, JJastzebskii et al. (2020) studies the effect of the learning rate on the variance of gradients and hypothesizes that gradient variance counter-intuitive
increases with the batch size, which is consistent with our observations. How- ever, Qian & Klabjan| (2020) shows that the variance of gradients is a decreasing function of the batch size. JJastzzbskki et al. (2020); Qian & Klabjan| (2020) mention the connection between vari- ance of gradients and generalization as promising future directions. Our study shows that variance of gradients used an early stopping criterion outperforms k-fold cross validation (see Table 8).
Mahsereci et al. 2017) proposes an early stopping criterion called evidence- based criterion (EB) that climinates the need for held-out validation set, similarly to gradient disparity. The EB crictiien is negatively related to the signal-to-note ratio (SNR) of the gradient vectors. Liu et al. (2020) also proposes relation between gradient SNR (called GSNR) and the one-step generalization error, with the assumption that both the training and the test sets are large, whereas gradient disparity targets limited datasets. Nevertheless, we have compared gradient disparity to these metrics (namely, EB, GSNR, gradient inner product, sign of the gradient inner product, variance of gradients, cosine similarity, and fee) in Appendix H In Table 8] we observe that gradient disparity and variance of gradients used as early stopping criteria are the only metrics that consistently outperform k-fold cross validation, and that are more informative of the level of label noise compared to other metrics. We observe that the correlation between gradient disparity and the test loss is however in general larger than the correlation between variance of gradients and the test loss (Table
A common drawback of the metrics based on the similarity between two gradient vectors, including gradient disparity, that they are not informative when the gradient vectors are very small. In practice however, we observe (see for instance Figure T3) that the time at which the test and training losses start to diverge, which is the time when overfitting kicks in, does not only coincide with the time at which gradient disparity increases, but also occurs much before the training loss becomes infinitesimal. Hence, this drawback is unlikely to cause a problem for gradient disparity when is used as an early stopping criterion. Nevertheless, Theorem T Tuiiiallyy holds when the gradient values are infinitesimal.
Conclusion. In this work, we propose gradient disparity, which is the &2 norm of the difference between the gradient vectors of pairs of batches in the training set. Our empirical results on state-of- the-art configurations show indeed strong link between gradient disparity and generalization error. Gradient disparity, similar to the test error, increases with the label noise level, decreases with the size of the training set and increases with the batch size. We therefore suggest, particularly when the available dataset is limited or noisy, gradient disparity as promising early stopping criterion that does not require access to a validation set.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
I Bellido and Emile Fiesler. Do backpropagation trained neural networks have normal weight dis- tributions? In International Conference on Artificial Neural Networks, pp. 772-775. Springer, 1993.
Emmanuel Bengio, Joelle Pincau, and Doina Precup. Interference and generalization in temporal difference learning. arXiv preprint 2tte:2003,0635500 2020.
Nicholas Bien, Pranav Rajpurkar, Robyn L Ball, Jeremy Irvin. Allison Park, Erik Jones, Michael Bereket, Bhavik N Patel, Kristen W Yeom, Katie Shpanskaya, et al. Deep-learning-ssee assisted diag- nosis for knee magnetic resonance imaging: development and retrospective validation of mrnet. PLoS medicine, 15(1 1):e 2018.
Sat Chatterjee. Coherent gradients: An approach to understanding generalization in gradient descent-based optimization. In International Conference on Learning Representations, 2020.
URL
net Eorum? wtw.://wwwweee/outeeeeeeeeeeee.e ddm.eeeyyrreeeer.......
John Duchi, Elad Hazan, and Yoram Singer, Adaptive subgradient methods for online learning and stochastic optimization. Journal machine learning research, 12(Ju)):121-2155) 2011.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703. 2017.
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, and Daniel M Roy. On the role of data in pac-bayes bounds. arXiv preprint arXiv:2006.1092) 2020.
Stanislav Fort, Pawel Krzysztof Nowak. Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: A perspective generalization in neural networks. arXiv preprint arXiv: wrXiv:1901.0949/, 2019.
Jinlan Fu, Pengfei Liu, Qi Zhang, and Xuanjing Huang. Rethinking generalization of neural models: A named entity recognition study. arXiv preprint urXiv:2001.03844 2020.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.
Jiuxiang Gu, Zhenhua Wang, Jason Kuen, Lianyang Ma, Amir Shahroudy, Bing Shuai, Ting Liu, Xingxing Wang, Gang Wang, Jianfei Cai, al. Recent advances in convolutional neural networks. Pattern Recognition, 77:354-377, 2018.
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. arXiv preprint arXiv:2004. 12983, 2020.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. arXiv preprint arXiv:1509.01244 2015.
Hangfeng He and Weijie Su. The local elasticity of neural networks. International Confer- ence on Learning Representations, 2020. URL httpth:://pppseeeeeeeeeee ew. net formm/?
HJJMYYNEPPH
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-leve performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy in classification tasks. arXiv preprint arXiv:2006.07322 2020.

---

Under review as a conference paper at ICLR 2021
Stanislaw Jastrzebski, Maciej Szymezak, Stanislav Fort, Devansh Arpit, Jacek Tabor, Kyunghyun Cho, and Krzysztof Geras. The break-even point on optimization trajectories deep neural networks. arXiv preprint arXt::2002.09572, 2020. 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.698) 2014.
Douglas M Kline and Victor L. Berardi. Revisiting squared-error and cross-entropy functions for training neural network classifiers. Neural Computing Applications, 14(4):310-318, 2005.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Mingehen Li. Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stop- ping is provably robust to label noise for overparameterized neural networks. arXiv preprint arXiv: 16800 2019.
Jinlong Liu, Yunzhi Bai, Guoqing Jiang, Ting Chen, and Huayan Wang. Understanding why neural networks generalize well through gsnr of parameters. In International Conference on Learning Representations, 2020. URL
Vincent Liu, Hengshuai Yao, and Martha White. Toward understanding catastrophic interference in value-based reinforcement learning. Optimization Foundations for Reinforcement Learning Workshop at NeurlPS, 2019.
Maren Mahsereci, Lukas Balles, Christoph Lassner, and Philipp Hennig. Early stopping without validation set. arXiv preprint arXiv: arXiv:1703.09580 2017.
David McAllester. Simplified pac-bayesian margin bounds. In Learning theory and Kernel ma- chines, pp. 203-215. Springer, 2003.
David A McAllester. Pac-bayesian model averaging. In Proceedings of the twelfth annual confer- ence on Computational learning theory, pp. 164-170, 1999a.
David A McAllester. Some pac-bayesian theorems. Machine Learning, 37(3):355-333, 1999b.
Harsh Mehta, Ashok Cutkosky, and Behnam Neyshabur. Extreme memorization via scale of initial- ization. arXiv preprini arXiv:2008. 13363, 2020.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generaliza- tion in deep learning. In Advances in Neural Information Processing Systems, pp. 11611-11622, 2019.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. -nformation-theorrtiee generalization bounds for sgld via data-dependent estimates. In Advances in Neural Information Processing Systems, pp. 11013-1102,, 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956,
2017a.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally-normalized margin bounds for neural networks. arXiv preprint arXiv:1707.09564, 2017b.
Lutz Prechelt. Early stopping-but when? In Neural Networks: Tricks of the trade, pp. 55-69. Springer, 1998.
Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks, 12 (1):145-151, 1999.
Xin Qian and Diego Klabjan. The impact of the mini-batch size on the variance gradients in stochastic gradient descent. arXiv preprint 1334:2004.13146 2020.
10

---

Under review as a conference paper at ICLR 2021
Matthew Riemer, Ignacio Cases, Robert Ajemian, Miao Liu, Irina Rish, Yuhai Tu, and Gerald Tesauro. Learning to learn without forgetting by maximizing transfer and minimizing interfer- ence. arXiv preprint arX1v:1810.11110, 2018.
Yuji Roh, Geon Heo, and Steven Euijong Whang. A survey on data collection for machine learning: a big data-ai integration perspective. IEEE Transactions on Knowledge and Data Engineering, 2019.
Sebastian Ruder.
overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747, 2016.
Karthik A Sankararaman, Soham De, Zheng Xu, W Ronny Huang. and Tom Goldstein. The impact of neural network overparameterizzttion on gradient confusion and stochastic gradient descent. arXiv preprint arXiv: (0..1944400999 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822-2877 2018.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-1958, 2014.
Mervyn Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society: Series B (Methodological), ( 36(2):1
1974.
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learn- ing. Constructive Approximation, 26(2):289-315, 2007.
Dong Yin, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter Bartlett Gradient diversity: key ingredient for scalable distributed learning. arXiv preprint
arXiv:1006.05699, 2017.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.035300 2016.

---

Under review as a conference paper at ICLR 2021
A ADDITIONAL THEOREM
Hoeffding's s bound is used in the proof of Theorem 1 and Lemma 1 is used in Section
Theorem 2 (Hoeffding's Bound). Let Zi..... nn be independent bounded random variables on [a, (i.e., Z, [a. b] for all 1 S S with -00
< 20). Then
2nt²
P
Σ n1
Z - E|Z,)) 2t) $ exx (- (b - a)²
and
P
-
1
Σ
74
B(ZZ)) $ -1) S exx
(T(b 0)²
2nt²
i=1
for all t 0.
Lemma 1 If N1 (M1 E and N2 = (u 222) are two multivariate normal distributions in Rd where Σj and Σg are positive definite,
det Στ det Σ
(L(N)]|N2) (tr - d +( 22 21) + In
B PROOF OF THEOREM 1
Proof. We compute the upper bound in Equation (3) using a similar approach as in McAllester (2003). The main challenge in the proof is the definition of function Xs, of the variables and parameters of the problem, which can then be bounded using similar techniques as in McAllester 2003). S₁ is batch of points (with size my) that is randomly drawn from the available set S at the beginning of iteration f, and S2 is batch of points (with size m2) that is randomly drawn from the remaining set S S₁. Hence, S₁ and S2 are drawn from the set S without replacement (S) S2 = 0). Similar to the setting of Negrea et al. (2019): Dziugaite et al. (2020), as the random selection of indices of S1 and S2 is independent from the dataset S, (S1) (S2). and as a result,
Gi TT or (S2) and G2 IL or (SS)) Recall that is the random parameter vector at the end of iteration t that depends on S, for i E {1,2) For a given sample set S,, denote the conditional probability distribution of 1/2 by Qs For ease of notation, we represent Qs, by Q..
Let us denote
A (hyn hpp))) 2 (Lsg (hrr) - L(hva)) (Lis (Nrva) - L(hrz)),
and
(7 -1) Bui~ei (Eug~eaa [(A (Reng ) (L(Q2)1Q1).
172
X 52
sup Q1.Q²
(8)
Note that Xs, is a random function of the batch S2. Expanding the KL-divergence, we find that
m2
-1 1
Ey Qu
[Eunqq (A (her 1 KL(Q2|1Q1)
2
m2 -1
Exz~Ca (A (Hbr 1er))) )) + ExgnQa In (12)
Eni~e -2
2
Q2(12)
m+ m))
Qı (1(2))
< ERy ~
In Buz~Qz
Q2(12)
m2 (A
Ev1~Qu
In Bug
where the inequality above follows from Jensen's 's incquality as logarithm is concave function. Therefore, again by applying Jensen's inequality
Xs, S In Eyno, Bugne, é (A(m
( [e4))
12

---

Under review as a conference paper at ICLR 2021
Taking expectations over S2, have that
e c== 12 (1)(( ) 27
B [x I Esg Enn
Qui Bug B Byg Qu Esg
( (=)-))(S(h))pe
where the change of order in the expectation follows from the independence of the draw of the S2 from in ~ Qi and v ~ Q1, i.e. Qi is me-masuurble and Gi IL (S2)).
Now let
Z; a 1hh, (at). mi) 1hhi (z:). wi),
for all 1 s m2- Clearly, Z, [-1, 1] and because of Equations and of the definition of in Equation 77.
A (hv, Mot)
Z E[
m2
Hoeffding's 's bound (Theorem) 2 implies therefore that for any 2 0,
Ps.. (ID (h h,, 2 S 2e 2
(10)
Denoting by p(A) the probability density function of A (hw, he; ) inequality (10) implies that for any 2 0,
p(A)dA 2 m2
(11)
The density p(A) that maximizes of the upper bound Equation p(A)= = 2m = As a result,
el
pl A dA (the term in the first expectation is the density achieving equality in which is
Esg e
1)
C 2mz Ae
1)A3
2ug 2
dA = f
00
2mz -ddA
dA m2
and consequently, inequality becomes
Es₁ [e Xsa] S m2,
Applying Markov's inequality Xss, have therefore that for any 0 5 1,
In 2mz
2m2
5
5 2
Psa
Xsa
Ps
X52
Esg
X32
2m2
Replacing Xs, by its expression defined in Equation 88. the previous inequality shows that with probability at least 1 - 15/2
m2 11 (m²
2mz Eu,~Q, Busnes [(A (Nen Mwr (L(Q211Q1) < In 8
2
Using Jensen's inequality and the convexity of (A (Mey )2 and assuming that m2 > 2, we therefore have that with probability at least 8822
(Bui~Qi Euz (A (N hw, )1) < Ev, Q, Busng (A (h,, 12 KL (L(Q221Q1) + In 2mz
3
Replacing A(hen hyn) by its expression Equation 7 in the above inequality, yields that with prob- ability at least 1 - 6/2 over the choice of the sample set S2.
2KL(Q2IIQ) Q1) + 21n 2mz
Buy~ [Lss(hun) L(hwz)] 5 Buz~Ra (bso (1iz)) L(hwz)) +
m2
(12)
13

---

Under review as a conference paper at ICLR 2021
Similar computations with S1 and S2 switched, and considering that my probability at least 1 - 6/2 over the choice of the sample set St,
2, yields that with
2KL Q2) + In
2
Bug~Q2 [ss (1wn)) - L(hvz)) Bui~es LLs, (lez) L(hw))
m1 -
(13)
The events in Equations 12 and (3) jointly hold with probability at least over the choice of the sample sets Si and S2 (using the union bound and De Morgan's law), and by adding the two inequalities we therefore have
B [Ls, Euy~ Qu Lss (hw,)) S EurrQq [L (hrz)) + Eu [Ls, (Ntv))
2KL((221Q11) + 21 2mp
(QL((1)1Q22) + 22 2m1
m2
m1
which concludes the proof.
C COMMON EXPERIMENTAL DETAILS
The training objective in experiments is minimize the cross-entropy loss, and both the cross entropy and the error percentage are displayed. The training error is computed using Equation (T over the training set. The empirical test error also follows Equation T but is computed over the test set. The generalization loss (respectively, error) is the difference between the test and the training cross entropy losses (resp., classification errors). The batch size in our experiments 128 unless otherwise stated, the SGD learning rate is = 0.01 and no momentum is used (unless otherwise stated). All the experiments took most few hours on one Nvidia Titan Maxwell GPU. All the reported values throughout the paper are an average over at least 5 runs.
To present results throughout the training, in the x-axis of figures, both epoch and iteration are used: an epoch is the time spent to pass through the entire dataset, and an iteration is the time spent to pass through one batch of the dataset. Thus, each epoch has iterations, where batches. The convolutional neural network configurations
the number of are: AlexNet (Krizhevsky al., 2012). VGG (Simonyan & Zisserman| 2014) and ResNet (He et al.] 2016). In those experiments with varying width, of hidden units in convolutional and fully connected layers, respectively. The default configuration is with scaling factor =
scaling factor to change both the number of channels and the number
In experiments with a random labeled training set, we modify the dataset similar to Chatterjee 2020). For fraction of the training samples, which is the amount of noise (0%, 25%, 50%, 75%. 100%), we choose the labels at random. For a classification dataset with a number k of classes, the label noise 25%, then on average 75% 25% * 1/k of the training points still have the correct label.
C.I RE-SCALING THE LOSS
Let us track the evolution of gradient disparity (Equation (6) during training. As training progresses, the training losses of all the batches start to decrease when they get selected for the parameter up- date. Therefore, the value of gradient disparity might decrease, not necessarily because the distance between the two gradient vectors is decreasing, but because the value of each gradient vector is itself decreasing. To avoid this, a re-scaling or normalization of the loss is needed to compare gradient disparity different stages of training. Note that this re-scaling or normalization does not affect the training algorithm, only the computation of gradient disparity.
14

---

Under review as a conference paper at ICLR 2021
We perform both re-scaling and normalization. The re-scaling of the loss values is given by
1.50
350
1.25
4
250
Dradient Disparitt
Lg,
std, (4)
g.75
200
where with some abuse of notation, 4 is the cross entropy loss for the data point in the batch Sy. The normalization of the loss values is given by
0.50
150
0.25
generalizate zation loss
gradient disparity normalized
gradient disperity re scaled
10a
10
10'
epochs
1 my
4 - Min, (4)
Ls,
Max; (4: Min; (4.)
Figure 5: Normalizing versus re-scaling loss be-
fore computing average gradient disparity 'D for VGG-11 trained 12.8 k points of the CIFAR-10 dataset.
We experimentally compare these two ways of computing gradient disparity in Figure Both the re-scaled and normalized losses, might get unbounded if within each batch the loss values are very close each other. However, in our exper- iments, do not observe gradient disparity becoming unbounded either way. In the presence of outliers, re-scaling is more reliable than normalizing, because with normalization non-outlier data might end up in very small interval between 0 and 1. This might explain the mismatch between the normalized gradient disparity and generalization loss at the end of training in Figure 5 Therefore, in all experiments presented in the paper, re-scale the loss values before computing the gradient disparity 33
C.2 THE HYPER-PARAMETER
In this section, we briefly study the choice of the size of the subset of batches to compute average gradient disparity
1.75
average gradient oi disparity Poarityy
250
1.25
200
1.00
D=
1
D.j.
0.75
generalization loss
3(3
j=1
0.50
s-2
100
0.25
5-5
Figure 6 shows the average gradient dispar- ity when averaged over number of batche When s = 2, gradient disparity is the le norm distance of the gradients of two randomly se- lected batches and has a quite high variance. Although with higher values of the results have lower variance, choosing a higher s is more computationally expensive (refer Ap- pendix D for more details). Therefore, we find the choice of 5 to be sufficient enough track down overfitting: in all the presented experiments in this paper, we use = 5.
s=10
5-20
-0.5
epochs
Figure 6: Average gradient disparity for differ- ent averaging parameter s for a ResNet- 18 that has been trained 12.8k points of the CIFAR-I0 dataset.
'Note that in Figure both the gradient disparity and the generalization loss are increasing from the very first epoch. If we would use gradient disparity as an early stopping criterion, optimization would stop at epoch 5 and would have 0.36 drop in the test loss value, compared to the loss reached when the model achieves 0 training loss.
'n the setting of Figure 6 if using gradient disparity as an early stopping criterion, optimization would stop epoch 9 and we would have 0.28 drop in the test loss value compared to the loss reached when the model achieves 0 training loss.
15

---

Under review as a conference paper at ICLR 2021
C.3 THE SURROGATE Loss FUNCTION
It has been shown that cross entropy is better suited for computer-vision classification tasks com- pared the mean square error (Kline & Berardi 2005; Hui & Belkin 2020). Hence, we choose the cross entropy criterion for all our experiments to avoid possible pitfalls of the mean square error, such as not tracking the confidence of the predictor.
Soudry et al. (2018) argues that when using cross entropy, as training proceeds, the magnitude of the network parameters increases. This can potentially affect the value of gradient disparity. Therefore, we compute the magnitude of the network parameters over iterations in various settings. We observe that this increase is very low both the end of the training and, more importantly, at the time when gradient disparity signals overfitting (denoted by GD epoch in T). Therefore, it is unlikely that the increase in the magnitude the network parameters affects the value of gradient disparity.
Furthermore, we examine gradient disparity for models trained on the mean square error, instead of the cross entropy criterion. We observe a high correlation between gradient disparity and test error/loss (Figure 7). which is consistent with the results obtained using the cross entropy criterion. Therefore, the applicability of gradient disparity as a generalization metric is not limited to settings with the cross entropy criterion.
Setting
at epoch 0
at GD epoch
at epoch 200
AlexNet, MNIST
1.00034
1.00123
AlexNet, MNIST, 50% random
1.00019
1.00980
VGG-16, CIFAR-10
1.00107
1.00127
VGG-16, CIFAR-10, 50% random
1.00222
1.00233
Table 3: The ratio of the magnitude of the network parameter vector at epoch to the magnitude of the network parameter vector at epoch 0, for & {0, GD, 200 where GD stands for the epoch when gradient disparity signals to stop the training.
+ VSG 16, CIFAR 10
+ VGG 16, CIFAR 10
Gradient disparitt
412
+ VGS 16, CIFAR
Test locc
1655
600
120k
255
5.1k
12.2
50x
2004
12.04 Training set size
2,58c
12.54
23.36
Taininn set 9ize
Training Seft size
Figure 7: Test error (TE), test loss (TL), and gradient disparity (D) for VGG-16 trained with different training set sizes to minimize the mean square error criterion the CIFAR-10 dataset. The Pearson correlation coefficient between TE and D and between TL and D are PT.TE = 0.976 and PT. 0.943, respectively.
16

---

Under review as a conference paper at ICLR 2021
D k-FOLD CROSS VALIDATION
k-fold cross validation is done by splitting the available dataset into sets, training on k of them and validating on the remaining one. This is repeated k times that every set is used once
as the validation set. We can adopt two different early stopping approaches: stop the optimization either (i) when the validation loss (respectively, gradient disparity) has increased for
5 epochs and 9 or (ii)
from the beginning of training (which is marked by the gray vertical bar in Figures g
when the validation loss (resp., gradient disparity) has increased for 5 consecutive epochs (which is indicated by the magenta vertical bar in Figures g and 99. When there is low variations and a sharp increase in the value of the metric, the two coincide (for instance, Figure g (b) (middle left)). In our experiments, we observe that gradient disparity appears to be less sensitive to the choice of the approaches (i) and (ii) compared k-fold cross validation. Moreover, in Table we study different
values of m, which is usually referred to as patience among practitioners.
Early stopping should optimally occur when there is a minimum valley throughout the training the test loss/error curves, or when the generalization loss/error starts to increase. In those experiments where such a minimum in the test loss curve exists, we compare gradient disparity to the test loss. Otherwise, we compare gradient disparity to the generalization loss. For k-fold cross validation, we compare validation loss to the test loss, because validation loss is expected to predict the test loss. Note that in the experiments with noisy labeled data, all the available data contains corrupted samples, hence both validation loss and gradient disparity are computed over sets which may contain corrupted samples.
Limited Data. We present the results for limited data scenario in Figure g and Table for MNIST, CIFAR-10 10 and CIFAR-101 100 datasets, where simulate the limited data scenario by using small subset of the training set. For the CIFAR-100 experiment (Figure g (a) and Table E (top row), we observe (from the left figure) that validation loss predicts the test loss pretty well. We observe (from the middle left figure) that gradient disparity also predicts the test loss quite well. However, the main difference between the two settings is that when using cross validation, 1/k of the data is set aside for validation and 1 - 1/k of the data is used for training. Whereas when using gradient disparity, all the data (1 1/k + 1/k) used for training. Hence, the test loss in the leftmost and middle left figures differ. The difference between the test accuracy (respectively, test loss) obtained in each setting is visible in the rightmost figure (resp., middle right figure). We observe that there is over 3% improvement in the test accuracy when using gradient disparity an early stopping criterion. This improvement is consistent for MNIST and CIFAR-10 10 datasets (Figures (b) and (c) and Table 4 We conclude that in the absence of label noise, both k-fold cross validation and gradient disparity predict the optimal early stopping moment, but the final test loss/error is much lower for the model trained with all the available data (as when gradient disparity is used), than the model trained with (1 (1-1/4 1/kk) portion of the data (as in k-fold cross validation). To further test on a dataset that is itself limited, a medical application with limited labeled data is empirically studied later in this section (Appendix D.T. The same conclusion is made for this dataset.
Noisy Labeled Data. The results for datasets with noisy labels are presented in Figure Jand Table for MNIST, CIFAR-10 and CIFAR-I00 datasets. We observe (from Figure 9 (a) (left)) that for the CIFAR-100 experiment, the validation loss does no longer predict the test loss. Nevertheless, although gradient disparity is computed on a training set that contains corrupted samples, it predicts the test loss quite well (Figure (a) (middle left)). As a result, there is a 2% improvement in the final test accuracy (for top-5 accuracy there is a 9% improvement) (Table (top two rows)) when using gradient disparity instead of a validation set as an early stopping criterion. This is also consistent for other configurations and datasets (Figure 9 and Table (). We conclude that, in the presence of label noise, k-fold cross validation docs no longer predict the test loss and fails as an early stopping criterion, unlike gradient disparity.
Computational Cost. Denote the time, in seconds, to compute one gradient vector, to compute the l norm between two gradient vectors. to take the update step for the network parameters, and to evaluate one batch (find its validation loss and error) by t,, 12. to and t4, respectively. Then, one epoch of f-ll cross validation takes
( Btt + 13) +
(k-1
B
CV CV opoch = k x
-
17

---

Under review as a conference paper at ICLR 2021
seconds, where B is the number of batches. computing the gradient disparity takes
Performing epoch of training the network and
GDspahh = B(t, + t3) + s ti + s 1--111 1/
2
seconds. In our experiments, we observe that 1 R 5.1 = 100ts = 3.4t4, hence the approximate time to perform one epoch for each setting is
CV cpoch (K: 1),
and
opoch R (B + s)tı.
Therefore, as < B, we have CV apoch
>>
GD
epoch
la:00 lss
Stkd
gadat Expar
arred mx drop Separity
3
tuc 5 802 60
16
1
opocts
apoc
opacts
speets
(a) Re trained on 1.28 k points of CIFAR- 100
2.4
bost
validaiinn los S-ddd
grau err Seqaiity
24
las
lss 3/M
S
Tist los 5D
itation
18
gesient dxpprity
14
epochs
sper
esocts
opects
(b) VGG-13 trained 1.28 k points of CIFAR-10
last lou 30
arhilann degarity
ka: less 3
sox CD
perena laatinn less 5D
sox fo
515
320
velddtion los 5-661
epach
(c) AlexNet trained on 256 points MNIST
Figure 8: Comparing 5-fold cross validation (CV) with gradient disparity (GD) as an early stopping criterion when the available dataset is limited. (left) Validation loss versus test loss in 5-fold cross validation. (middle left) Gradient disparity versus test and generalization losses. (middle right and right) Performance on the unseen (test) data for GD versus 5-fold CV. (a) The parameters are initialized by Xavier techniques with uniform distribution. (b. e) The parameters are initialized using He technique with normal distribution. (c) The batch size is 32. The gray and magenta vertical bars indicate the epoch in which the metric (the validation loss or gradient disparity) has increased for epochs from the beginning of training and for 5 consecutive epochs, respectively. In (b) the middle left figure, these two bars meet each other.
D.1 MRNET DATASET
So far, we have presented the improvement of gradient disparity over cross validation for limited subsets of MNIST, CIFAR-10 and CIFAR-100 datasets. In this sub-section, we present the results for when the available dataset by itself limited. We consider the MRNet dataset [Benn et al. (2018) for diagnosis of knee injuries. The dataset contains 1370 magnetic resonance imaging (MRT) exams to study the presence abnormality, anterior cruciate ligament (ACL) tears and meniscal tears. The labeled data in MRNet dataset is therefore very limited. Each MRI scan is a set of S slices of images stacked together. Each patient (case) has three MRI scans: sagittal, coronal and axial. The MRNet dataset is split into training (1130 cases), validation (120 cases) and test sets (120 cases). The test set is not publicly available. We need however to set aside some data to evaluate both gradient disparity and k-fold cross validation, hence, in our experiments, the validation set becomes the unseen (test)
18

---

Under review as a conference paper at ICLR 2021
Setting
Method
Test loss
Test accuracy
5-fold CV
4.249 = 0.028
6.79 + 0.49 (top-S: 5: 22.19 = 0.77)
CIFAR-100, ResNet-34
GD
4.057 = 0.043
9.99 + 0.92 (top-5: 27.84 + 1.30)
5-fold CV
1.846 0.016
35.982 + 0.393
CIFAR-10, VGG-13
GD
1.793 = 0.016
36.96 + 0.861
5-fold CV
1.123 + 0.25
62.62 + 6.36
MNIST, AlexNet
GD
0.656 = 0.080
79.12 + 3.04
Table 4: The loss and accuracy on the test comparing 5-fold cross validation and gradient dispar- ity as early stopping criterion when the available dataset limited. The corresponding curves during training are presented in Figure The above results are obtained by stopping the optimization when the metric (either validation loss or gradient disparity) has been increased for five epochs from the beginning of training.
Patience
10
15
20
25
Method
5-fold CV GD
41.15 1 5.68
62.62 1. 6.36
81.39 3.64
80.39 L 2.88
84.84 1. 2.53
83.55
2.84 1.31
30.19 + 6.21
79.12 + 3.04
84.82 + 2.14
85.35 2.09
87.28 + 1.24
86.69
(a) MNIST, AlexNet, limited dataset (Figure
8 (c)
Patience
10
15
20
25
Method
10-fold CV
96.54 = 0.15
97.28: 0.20
97.35 + 0.23
97.22+ 0.19
96.60 = 0.33
94.69 + 0.87
GD
97.07 + 0.16
97.32 1 0.15
97.41 + 0.15
96.571 0.64
95.44 + 0.96
92.58 +: 0.65
(b) MNIST, AlexNet, noisy dataset (Figure
Table 5: The test accuracies achieved by using k-fold cross validation (CV) and by using gradient disparity (GD) as early stopping criteria for different patience values. For a given patience value of m, the training is stopped after increases in the value of the validation loss in k-fold CV (top rows) and of GD (bottom rows). Throughout the paper, we have chosen m = 5 as the default patience value for all methods without optimizing it even for GD.. However, in this Table, we observe that even if we tune the patience value for k-fold CV and for GD separately (which is indicated in bold), GD still outperforms k-fold CV.
set. To perform cross validation, we split the set used for training in Bien et al. (2018) into first subset used for training our experiments, and a second subset used as validation set. Note that, in this dataset, because slice S changes from one case to another, it is not possible to stack the data into batches, hence the batch size is 1, which may explain the fluctuations of validation loss and gradient disparity in this setting. We used the SGD optimizer with the learning rate 10-1 for training the model. Each task in this dataset is a binary classification with unbalanced set of samples and hence we report the area under the curve of the receiver operating characteristic (AUC score).
The results for three tasks: detecting ACL tears, meniscal tears and abnormality, are shown in Figure [0] and Table 7 We can observe that both the validation loss, despite small bias, and the gradient disparity predict the generalization loss quite well. Yet, when using gradient disparity, the final test AUC score is higher (Figure [0] (right)). As mentioned earlier, for this dataset, both the validation loss and gradient disparity vary a lot. Hence, in Table Z we present the results of early stopping, both when the metric has increased for 5 epochs from the beginning of training, and (in parenthesis) when the metric has increased for 5 consecutive epochs. We conclude that with both approaches, the use of gradient disparity as an early stopping criterion results in more than 1% improvement in the test AUC score. Because the test set used in Bien et al. (2018) is not publicly available, it is not possible to compare our predictive results with Bien et al. 20188. Nevertheless, com. ahme
baseline may be the results presented in https: /tte:://qittue which report a test AUC score of 88.5% for the task of detecting ACL tears, whereas we observe in Table that stopping training after consecutive increases in gradient disparity leads to 91.52%
mrnet,
19

---

Under review as a conference paper at ICLR 2021
Setting
Method
Test loss
Test accuracy
10-fold CV
5.023 = 0.083
1.59 - 0.15 (top-5: 6.47=0.550
CIFAR-100, ResNet-
GD
4.463 0.038
3.68 + 0.52 (top-5: 15.22 1.24)
Plug-in
4.964 0.057
1.68 + 0.24 (top-5: 7.05 + 0.71)
10-fold CV
4.062 = 0.091
9.62 + 1.08 (top-5: 32.06 + 1,47)
CIFAR-100, ResNet-34
GD
4.592 = 0.179
10.41 + 1.40 (top-5: 36.92 1.20)
Plug-in
4.1341 0.185
10.11 = 1.60 (top-5: 34.19 + 2.10)
10-fold CV
2.126 = 0.063
34.88 + 1.66
CIFAR-10, VGG-13
GD
2.519 = 0.062
36.98 + 0.77
Plug-in
2.195 + 0.142
35.40 + 3.00
10-fold CV
0.656 0.034
97.28 + 0.20
MNIST, AlexNet
GD
0.654 = 0.031
97.32 + 0.27
Plug-in
0.639 0.029
97.31 + 0.15
Table 6: The loss and accuracy on the test set comparing 10-fold cross validation and gradient dis- parity as early stopping criterion when the available dataset is noisy. In all the experiments, 50% of the available data has random labels. The corresponding curves during training presented in Figure 9 The above results are obtained by stopping the optimization when the metric (either vali- dation loss gradient disparity) has been increased for five epochs from the beginning of training. The last row in each setting, which we call plug-in, refers to when we plug-in the epoch suggested by 10-fold CV and then report the test loss and accuracy at that epoch for network trained on the entire set. In all these settings, using GD would still result in higher test accuracy and therefore the advantage of GD over 10-fold CV is better characterization of overfitting.
test AUC score for this task. With further tuning, and combining the predictions found on two other MRI planes of each patient (axial and coronal), our final prediction results could even be improved.
Task
Method
Test loss
Test AUC score
5-fold CV
0.973 = 0.111 (1.246 = 0.142)
79.80 + 1.23 (89.32 + 1.47)
ACL
GD
0.842 = 0.101 (1.136 0.121)
81.81 + 1.64 (91.52 + 0.09)
5-fold CV
0.758 + 0.04 (1.163 + 0.127)
73.53 + 1.30 (72.14 + 0.74)
meniscal
GD
0.726 = 0.019 (1.14 0.323)
74.08 = 0.79 (73.80 = 0.24)
5-fold CV
0.284 = 0.016 (0.307 0.057)
71.016 3.66 (87.44 1.35) 72.67 = 3.85 (88.12 + 0.35)
abnormal
GD
0.274 = 0.004 (0.275 0.053)
The loss and AUC score on the test set, comparing 5-fold eross validation to gradient disparity both as early stopping criterion for the MRNet dataset for three different tasks using the sagittal plane MRI seans. Note that an unassisted general radiologist gives on average 92%, 84% and 89% accuracy for detecting ACL tears, meniscal tears and abnormality, respectively (Bien al.) 2018). The corresponding curves during training are presented Figure IO We present the results of early stopping, both when the metric has increased for 5 epochs from the beginning of training, and in parenthesis when the metric has increased for consecutive epochs.
Table 7:
20

---

Under review as a conference paper at ICLR 2021
3.0
IsL guadeer
grec exz Separty
30.
Losk occurery
Sap 10-8d
0.75
5400
4.2
400
175
coocss
spocts
cpadts
opeets
(a) ResNet- 18 trained on 1.28 points of CIFAR- 100 dataset with 50% label noise
voll pilliition los fold
grsd umdeen: Sapanig
las 10 fold
general gradeet sparty
top-
tpoch
spechs
esodt
epects
(b) ResNet-34 trained the entire CIFAR-100 dataset with 50% label noise
lass
loss 33-fo
los 10-i6
vuil diitóon oel (0-akl
geierral grddle: Spariy
10-ked
VGG-13 13 trained on the entire CIFAR-10 dataset with 50% label noise
rest eror 60
Gracient Fleu
1.
lass 50
10
lslt los 16-lad valiaaiion tis sol
825
10-60
12'
12
03.0
12
apochs
(d) AlexNet trained on the entire MNIST dataset with 50% label noise
Figure 9: Comparing 10-fold cross validation with gradient disparity early stopping criteria when the available dataset is noisy. (left) Validation loss versus test loss in 10-fold cross validation. (mid- dle left) Gradient disparity versus test and generalization losses. (middle right and right) Perfor- mance on the unseen (test) data for GD versus 10-fold CV. (a) The parameters are initialized by Xavier techniques with uniform distribution. (b, c, and The parameters are initialized using He technique with normal distribution.
21

---

Under review as a conference paper at ICLR 2021
test less S-fald
1.2
icetion gradient disparity
0.9
NUC GD AUC 5-fold
validitiin loss S-fold
1.00
AUC score
2.0
1.5
C.775
600
0.
400
1.0
200
10'
10
30" epochs
10
eoochs
epochs
(a) Task: detecting ACL tears
1.75
test loss S-fold
2.0
genera ization loss GD gredient disprrity
AUC
150
velidetion
seete
1.25
$1.0
2200
100
gredtee
0.700
323
6.675
0.75
0.550
10
10a coochs
10
epochs
opachs
(b) Task: detecting meniscal tears
test loss S-fold
genera izstra izetion loss GD gredient dispanity
422
AUC GD
0.35
velidation loss f-lald
Test AUC score
0.8
AUC S-fold
S0.
0
0.25
0.0
0.0
10F
18a epachs
10'
10
72 spochs
10
10'
30 epochs
10'
(c) Task: detecting abnormality
Figure 10: Detecting three tasks from the MRNet dataset from the sagittal plane MRI scans. (left) Validation loss versus loss in 5-fold cross validation. (middle) Gradient disparity versus gener- alization loss. (right) Performance comparison on the final unseen data when applying 5-fold CV versus gradient disparity.
22

---

Under review as a conference paper at ICLR 2021
E ADDITIONAL EXPERIMENTS
2.5
test loss
generaization
Generel elizttetiition errrr
40
generalization emar
3.0
tro it loss
test loss
Gradient disparity
gradient disperity
g
Gradient Redientt disperity
entragy
izabion Icss
gradient dispaitt
1.5
3.
Cross
1op
20
2.5
0.0
0.0
10>
Iteraaionns
Iter ons
herations
(a) Cross entropy loss
(b) vs. loss
(c) D vs. error
3.0
ta n loss
1.5
lest loss
generaliation
Grold seeeent elispa 3t Sa
disspinity
Error pert perceented eentage
lest enoor
generaizationn emror
Choss entropy
ger eera lzation loss
Crogs extegey
gr gradient disperity
gradient disparity
1.0
05
05
00
10'
10 Iterations
109
10'
100
teeations
Iterations
(d) Cross entropy loss
(e) D vs. loss
(I) 2> vs. error
Figure 11: The cross entropy loss, the error percentage and the average gradient disparity during training. (a-c): A ResNet-18 trained on a subset of 12.8 k points of the CIFAR-10 training set (the parameter initialization is Xavier (Glorot & Bengio 2010)). Pearson's correlation coefficient p between D and generalization loss/error over all the training iterations are PD.gen loss 0.755 and (DDgen error
= 0.846. (d-f): An AlexNet trained on subset of 12.8 k points of the MNIST training set (the parameters are initialized according to the He (He et al. 2015) method with Normal distributions). For this experiment, PD gen loss = 0.465 and PD emror
0.457. The blue, orange, green, and red curves are the test loss/error, train loss/error, generalization loss/error, and the average gradient disparity D. respectively.
To investigate the relation between the average gradient disparity D and generalization, we compare two sets of experiments. The first one exhibits clear overfitting, whereas in the second one, the model generalizes quite well. To test gradient disparity it have very different values for each of these two sets of experiments, but it should also be well aligned with the generalization error. This is indeed what the experiments show.
generalization metric, not only should
In the first set of experiments, the network configuration ResNet-18 (He et al. 2016) and it is trained on the CIFAR-10 dataset (Figure 1T (top)). Around iteration 500 (which is indicated by thick gray vertical bar in the figures), the training and test losses (and errors) start to diverge, and the test loss reaches its minimum. This should be the early stopping point as the model starting to overfit. Interestingly, around the same time (indicated in Figures (b) and (c)), we observe a sharp increase in D.
The second set of experiments is on an AlexNet (Krizhevsky et al., 2012) trained on the MNIST dataset (Figure IT (bottom)). This model generalizes quite well for this dataset. We observe that, throughout the training, the test curves are even below the training curves, which is due to the dropout regularization technique (Srivastava al. 2014) being applied during training and not dur- ing testing. The generalization loss/error is almost zero, until around iteration 1 1100 (indicated in the figure by the gray vertical bar), which is when overfitting starts and the generalization error becomes non-zero. At approximately the same time, the average gradient disparity (Figures [ (e) and (f) starts to slightly increase, but much more slowly compared to Figures IT (b) and (c). In both these experiments, we observe that overfitting starts, the gradient vectors start to diverge, resulting in larger gradient disparity. These observations suggest gradient disparity as an effective early stopping criterion, as it is well aligned with the generalization error.
23

---

Under review as a conference paper at ICLR 2021
E. MNIST EXPERIMENTS
Figure [ shows the results for a 4-layer fully connected neural network trained on the entire MNIST training set Figures 12 (e) and (f) show the generalization losses. We observe that the early stages of training, generalization losses do not distinguish between different label noise levels, whereas gradient disparity (Figures 12 (g) and (h)) does so from the beginning. At the middle stages of training we can observe that, surprisingly in this setting, the network with 0% label noise has higher generalization loss than the networks trained with 25%, 50% and 75%, and this is also captured by average gradient disparity. The final gradient disparity values for the networks trained with higher label noise level are also larger. For the network trained with 0% label noise we present the results with more detail in Figure 13 and observe again how gradient disparity is well aligned with the generalization loss/error. In this experiment, the early stopping time suggested by gradient disparity is epoch 9, which is the exact same time when the training and test losses/errors start to diverge, which signals therefore the start of overfitting.
50%
75%
line
lobel
18
12
12"
19
Exccss
(a) Training loss
(b) Test loss
(c) Training error
(d) Test error
label nolse
0% label noise
25% labal nolse
0.3
25% label
Cenerali zation
50% label noise
Ganaralizaton
50% label no
75% labal noise
0.2
75% label noise
0.3
0.0
10
16
102
Epochs
Epochs
(e) Generalization loss
(f) Generalization loss for epoch 80
Average gradient dispprtty
120
Avarage gradient dispariy
label
20
noise
200
25% label noise
25% label noise
00
50% label noise
15
50% label noise
75% label noise
75% label noise
50
20
5
10
16
10
12
10:
Epachs
Epochs
(g) D
(h) D for epoch < 80
Figure 12: The cross entropy loss, error percentage, and average gradient disparity during training with different amounts of randomness in the training labels for 4-layer fully connected neural network with 500 hidden units trained on the entire MNIST dataset. The parameter initialization is the He initialization with normal distribution.
httpp://yann 1 lecun, wwwp////ww///////ooooooo/oeeeee/ / st./
24

---

Under review as a conference paper at ICLR 2021
Cross Entropy Loss
0.7
train loss
30
Average gradient disparity
20.0
17.5
train error
Average gradient disparity
test loss
Error Percentage
test error
:5.0
generalization loss
generalization error
0.5
12.5
8 t. 8.
gradient disparity
gradient disparity
0.4
10.0
15
0.3
7.5
0.2
10
0.1
2.5
0.0
10a
10
10'
13P
10
10'
Epochs
Epochs
(a) Loss vs gradient disparity
(b) Error gradient disparity
Figure 13: The cross entropy loss, error percentage, and average gradient disparity during training for 4-layer fully connected neural network with 500 hidden units trained on the entire MNIST dataset with 0% label noise. The parameter initialization the He initialization with normal dis- tribution. Pearson's correlation coefficient p between D and generalization loss/error over all the training iterations are DD.gen loss = 0.967 and pe.gen emor = 0.734. The gray vertical bar indicates when GD increases for 5 epochs from the beginning of training. The magenta vertical bar indicates when GD increases for consecutive epochs. We observe that the gray bar signals when overfitting is starting, which is when the training and testing curves are starting to diverge. The magenta bar would be good stopping time, because if train beyond this point, although the test error remains the same, the test loss would increase, which would result in overconfidence on wrong predictions.
E.2 CIFAR-10 10 EXPERIMENTS
Width. To compare models with different number of parameters using gradient disparity, need to normalize it. The dimension of a gradient vector is the number d of parameters of the model. Gradient disparity being the fn-norm of the difference of gradient vectors will thus grow proportionally to dd, hence compare different architectures, we propose use the normalized gradient disparity D D/ Vd. We observe Figure 14 both the Pormalized@eradiceee disparity and test error decrease with the network width (the scale is hyper-paramete used to change both the number of channels and hidden units each configuration).
'Note that the normalization with respect to the number of parameters is different than the normalization mentioned in Section C. which was with respect to the loss values. The value of gradient disparity reported everywhere is the re-scaled gradient disparity; further if comparison between two different architectures is taking place the normalization with respect to dimensionality will also take place.
25

---

Under review as a conference paper at ICLR 2021
leste-11
Reste-11
Realee33
Redhee-3
165
168
V53 16
VB8 to
Scale
Scale
Scale
Scale
(a) CNN; (left): PB,T. 0.970, PB,TE = 0.939, (right): PB, 0.655, PB,TE 0.958
4Hayer
4-ayer FC
Slayer FC
5-ayer FC
8
(30
1200
175
1238
1728
Width
Witth
(b) FCNN; P5,n. 0.771, P5, 0.601
Figure 14: Test егrоr and normalized gradient disparity for networks trained on the CIFAR-10 dataset with different number of channels and hidden units for convolutional neural networks (CNN) and fully connected neural networks (FCNN). The correlation between normalized gradient dispar- ity and test loss PB.n. and between normalized gradient disparity and test error Po. are reported in the captions.
26

---

Under review as a conference paper at ICLR 2021
Figure 15 shows the results for 4-layer fully connected neural network, which is trained on the entire CIFAR-10 10 training se 7 We observe that gradient disparity reflects the test error at the early stages of training quite well. In the later stages of training we observe that the ranking of gradient disparity values for different label noise levels matches with the ranking of generalization losses and errors. In all experiments the average gradient disparity is indeed very informative about the test error. Figure 16 shows the effect of adding data augmentation on both the test error and gradient dis- parity, Figure 17 shows test error and gradient disparity for networks that are trained with different training set sizes, In Figure 18] we observe that, as discussed in Section [ gradient disparity, similar to the test error, increases with the batch size for not too large batch sizes, and as expected, when the batch size is very large (512 for the CIFAR-10 10 experiment and 256 for the CIFAR-100 100 experiments) gradient disparity starts to decrease, because gradient vectors are averaged over large batch. Note that even with such large batch sizes, gradient disparity correctly detects the early stopping time, but the value of gradient disparity can no longer be compared to the one found with other batch sizes.
7%
lite tncite
latal inciee
25% labas (nciss
(1 lbbl
35% ated
lasel
59% atel
losel
label
75% abel
75% loail
label
1perts
12
121
Ppechs
Epoct
(a) Training loss
(b) Test loss
(c) Training error
(d) Test error
label
0% noise
25% label noise
25% label noise
Generalization
50% label noise
Conerraization
60
50% label noise
75% label noise
75% label noise
40
20
Epochs
Epochs
(c) Generalization loss
(f) Generalization error
Average gradient disparity
Average gradient dispority
label noise
0% noise
2000
25% label noise
50
25% label noise
1500
50% label noise
75% label noise
40
50% label noise
75% lobel noise
3000
80
500
20
16
10
10
18'
Epochs
Epochs
(g) D
(h) D for epoch > 20
Figure 15: The cross entropy loss, error percentage, and average gradient disparity during training with different amounts of randomness in the training labels for 4-layer fully connected neural network with 500 hidden units trained on the entire CIFAR- 10 dataset. The parameter initialization is the Xavier initialization with uniform distribution. The training is stopped when the training loss gets below 0.01.
html
27

---

Under review as a conference paper at ICLR 2021
+ Vit DA
2.21
Without
Graccent diserryy
Wiltour
3.20
532
7504
04
1334
755
12.
15.6
56
1250
7.56
5336
1204
755c
300
+ Ver
Without
With DA Withor
error
Taining
Triining 60m
Tiitning
(a) With DA, PD.TE 0.984
(b) Without DA, PD,TE 0.983
(c) Both, PD.m 0.619
Figure 16: The test error (bottom row) and gradient disparity (top row) for a ResNet- 18 trained on the CIFAR-10 dataset with different training set sizes. (a) Results with data augmentation (DA) (we use random crop with padding = 4 and random horizontal flip with probability = 0.5). (b) Results without using any data augmentation technique. (c) Combined results of (a) and (b). We observe strong positive correlation between gradient disparity (D) and test error (TE) regardless of using
data augmentation or not. We also observe that using data augmentation decreases the values of both gradient disparity and the test error.
+ V0G-5 OTN-38
Grardont diseritt
+ 100-5 OIVR33
Noilet N1.1
Gradient disgovitt
Nollet NI.5
Test CHOOP
Tra
Traning
(a) VGG-16, CIFAR-10, PB.. 0.972
(b) ALexNet, MNIST, PT.IK 0.929
Figure 17: Test enror and gradient disparity for networks that are trained with different training set sizes. The training is stopped when the training loss is below 0.01.
Rachee1-15
Saclic1-1
3.45
555
Grvedleent
Refte:33 Redhi:344
Reshee33
Rethah
115
115
115
15
s2e
52e
220
(a) CIFAR-10, PB.1E
0.631
(b) CIFAR-100, PB,
0.909
Figure 18: Test error and gradient disparity for networks that are trained with different batch sizes trained on 12.8 k points of the CIFAR-10 and CIFAR-100 datasets. The training is stopped when the training loss is below 0.01.
28

---

Under review as a conference paper at ICLR 2021
E.3 CIFAR- 100 EXPERIMENTS
Figure 19 shows the results for a ResNet-18 that is trained on the CIFAR-100 training se Clearly, the model is not sufficient to learn the complexity of the CIFAR- dataset: It has 99% error for the network with 0% label noise, as if it had not learned anything about the dataset and is just making a random guess for classification (because there are 100 classes, random guessing would give 99% ervor on average). We observe from Figure 19 (f) that as training progresses, the network overfits more, and the generalization error increases. Although the test error high (above 90%), very surprisingly for this example, the networks with higher label noise level, have a lower test loss and error (Figures 19 (b) and (d)). Quite interestingly gradient disparity (Figure 19 (g)) captures also this surprising trend well.
lnsel molte
lobel noiee
1%,
1380
57% vilo
75% siee ne
79% lotel sode
75% stel mole
5% libdl hols
henaties
(a) Training loss
(b) Test loss
(c) Training error
(d) Test error
13
100
300
5% lobel nolse
0% lebel moise
Generalization lo5s
iabel roise
80
250
25% notse
6
75% aael roise
50% abel roise
Generalization
60
Average gradient
200
75%
50%
label noise
0% label noise
330
40
25% label noise
320
20
50% label noise
50
75% label roise
10
18' Iteretions
10
Rterations
Hteaaions
(e) Generalization loss
(1) Generalization error
(g) Average gradient disparity D
Figure 19: The cross entropy loss, eтror percentage, and average gradient disparity during training with different amounts of randomness in the training labels for a ResNet-18 18 trained on the CIFAR- 100 training set. The parameter initialization is the Xavier initialization.
F NUMBER OF BATCHES WITH Low GRADIENT DISPARITY
In this paper. the upper bound in Theorem is tracked by computing the average gradient disparity D over subset of batches. In this section, to gain some finer-grain signal of overfitting during the training process, we track down the distribution of this bound by studying the distribution of the gradient disparity, i.c., PPD < () for some threshold Ç.
We find the number of pairs of batches in the training set, denoted by Te, whose gradient dis- parity below the given threshold Ç. For these pairs of batches, the upper bound in Theo- rem [ with probability at least 1 - o and for two batches with the same size m, is below 2 /= (n(2m/0)) ('m 2j. The lower Te is. the higher the average upper bound is, hence the more likely overfitiing becomes. As before, for the sake of computational tractability, instead of going through all the possible pairs, we only compare s(s - 1) pairs of batches (s = 5 for our experiments), so 0 5= T S s(s - 1). We empirically estimate P(D,,, < () over s batches by (</(s(8 1)). In our experiments, we compute T for ( E 203.
We show that an early stopping criterion, Te is sometimes (slightly) more accurate than D. For instance, in Figure 20 (d) we highlighted in gray the minima valley of the test error for the network trained with 25% noise and we observe that this aligns with the drop in T/g for Ç 20 (light pink curve in Figure 20 (g)) better than the increasing time of D (Figure 20 (f)). Also, the slow increase in the generalization loss for the AlexNet (green curve in Figure
(a) is captured by the drop in
29

---

Under review as a conference paper at ICLR 2021
25% atdd rase
25% nole
313
29t
(a) Training loss
(b) Test loss
(c) Training error
(d) Test error
#Palis of baacches with Dr, D
100
Average gredeett deperiy
120
0% incel noice
noisa 25% lobel naise
0% lacel noiée
25%
25%
50
10
100
10
12
30'
Beralions
Generalization
(f) Average gradient disparity D
(g) Te for Ç 20
Figure 20: The cross entropy loss, error percentage, average gradient disparity and Te for = 20 during training with different amounts of randomness in the training labels for ResNet-18 18 trained on subset of 12.8 k points of the CIFAR-I0 training set. We can observe that, in this setting, average gradient disparity distinguishes different label noise levels from the beginning of training, unlike generalization enror.
Cross entropy loss
test loss
Gradient diape-10
20
1.
generalbation loss
65
08
10'
12
10
terations
teeaaions
Iterations
(a) Loss
(b) D
(c) T: for < 10
Figure 21: The cross entropy loss, average gradient disparity D, and T/ for for an AlexNet trained on a subset of 12.8 k points of the MNIST training set.
10 during training
Tg for Ç = 10 (Figure 21 (c)) slightly better than the increase in the average gradient disparity (Fig- ure 21 (b)). The drawback of Te compared to is that introduces an additional nypee-paramettr which requires tuning. In our experiments, as rough rule of thumb, we observe that setting around 10% of the initial gradient disparity works well. Further empirical investigation on Te is left as future work.
G BEYOND SGD
In the following, we discuss how the analysis of Section can be extended for other optimizers (refer to Ruder (2016) for an overview on popular optimizers).
G.1 SGD WITH MOMENTUM
The momentum method Qian 1999) is variation of SGD which adds a fraction of the update vector of the previous step the current update vector accelerate SGD:
y (f+1) (p(()) + (")
un (1+1) (t) (1+1)
30

---

Under review as a conference paper at ICLR 2021
where g( is either 91 or 92 depending on the selection of the batch S1 or S2 for the current update step. As ((() remains the same for either choice, the KI.-divergence between Q1 and Q2 for SGD with momentum, is the same as Equation
G.2 ADAGRAD
Adagrad (Duchi et 2011 performs update steps with a different learning rate for each individual parameter. By denoting each coordinate of the parameter vector w by d, one update step of the Adagrad algorithm is
((+1) w' w'd
(e)
9d
(14)
G
+
where the vector glt) is either 91 or I2 depending the selection of the batch for the current update step, and Git) is the accumulative squared norm of the gradients up until iteration Hence, for Adagrad, Equation (5) is replaced by
1 2 GO
1 1
(L(Q)11
+ O (g) 92)
11 -22112
(15)
2 2
G
+
where @ denotes the element-wise product of two vectors, where division is also taken element- and where is small positive constant that avoids possible division by O. To compare the upper bound in Theorem [ from one iteration to the next one (as needed to determine the early stopping moment in Section 5). gradient disparity is not the only factor in Equation
(15) that evolves over
time. Indeed G(+) is an increasing function of f. However, after a few iterations when the gradients become small, this value becomes approximately constant (the initial gradient values dominate the sum in G(t). Then the right hand side of Equation (15) varies mostly as function of gradient disparity, and therefore gradient disparity approximately tracks down the generalization penalty upper bound.
G.3 ADADELTA AND RMSPROP
Adadelta Zeiler 2012) is an extension of Adagrad, which computes decaying average of the past gradient vectors instead of the accumulative squared norm of the gradients dur- ing the previous update steps. G(t) in Equation (14) is then replaced by uz wf(t1) where 2d (+++) = .uu + (1 () As training proceeds, the gradient magnitude decreases. Also, is usually close to Therefore, the dominant term in v/d (t+1) becomes ( Then, if we approximate ii [t++1 = (t) (1 7) (01)² = no(t)) + (1 17) (gz) ug
(t+1) (squares done element-wist wise),
then for Adadelta we have
172 nz v(++1)
KL(QI
11
92 9211.
(16)
+E
where again the division done element-wise The denominator in Equation (16) is smaller than the denominator in Equation (15). In both equations, the first non-constant factor in the upper bound of (LL(Q1 [[22) decreases as a function of I, and therefore an increase the value of KI.(Q1 l22)
should be accounted for by an increase in the value of gradient disparity. Moreover, as training proceeds, gradient magnitudes decrease and the first factor on the upper bound of Equations ([5)
and (16) becomes closer to constant. Therefore, upper bound on the generalization penalties can be tracked by gradient disparity.
The update rule of RmsProp is very similar to Adadelta, and the same conclusions be made.
https: httpss//www..ccccaooooeee///a//a
pdf
31

---

Under review as a conference paper at ICLR 2021
G.4 ADAM
Adam (Kingma & Ba, 2014) combines Adadelta and momentum by storing an exponentially decay- ing average of the previous gradients and squared gradients:
m (++1) = f) (1) + (1)
((11)) =B2 + (1 (0/00)
=
(t+1)
ult+1)
m(++1)
((++1) 1 - (32)²
((+1) =w())
m (1+1))
- (3))*
Vol++1 +e
All the operations in the above equations are done wlement-wise. As B2 is usually very close to 1 (around 0.999), and as squared gradient vectors at the current update step are much smaller than the accumulated values during the previous steps, we approximate: (squares are done element- Vi ((+1) Bgu(t) + (1-3g) (11-3)) (g1) x B2el(t) + +11 32) (92)² Uz wise). Hence, Equation becomes
(I+1)
1 1 1-
1
(L(Qi)lQ2) - 2 (81)²
1911 --21122
(17)
Vi(+1) + 2
The first non-constant factor in equation above decreases with (because B1 1). However it is not clear how the second factor varies as training proceeds. Therefore, unlike previous optimizers, it is more hazardous to claim that the factors other than gradient disparity Equation (17) become constant as training proceeds. Hence, tracking only gradient disparity for the Adam optimizer may be insufficient. This is empirically investigated in the next sub-section.
G.5 EXPERIMENTS
Figure 2 shows gradient disparity and test loss curves during the course of training for adaptive optimizers. The epoch which the fifth increase in the value of the test loss and gradient disparity has happened is presented in the caption of each experiment. We observe that the two suggested epochs for stopping the optimization (the one suggested by gradient disparity (GD) and the other
one suggested by test loss) are extremely close to each other except in Figure 22 (c) where the fifth epoch with an increase in the value of gradient disparity is much later than the epoch with the fifth
increase in the value of test loss. However, in this experiment, there 23% improvement in the test accuracy if the optimization is stopped according to GD compared to test loss, due to many variations of test loss compared to gradient disparity.
As an early stopping criterion, the increase in the value of gradient disparity coincides with the increase in the test loss in all our experiments presented in Figure 22] In Figure 22 (h), for the Adam optimizer, we observe that after around 20 epochs, the value of gradient disparity starts to decrease, whereas the test loss continues to increase. This mismatch between test loss and gradient disparity might be due to the effect of the other factors that appear in Equation (17). Nevertheless, even in this experiment, the increase in the test loss and the gradient disparity coincide, and hence gradient disparity can correctly detect early stopping time. These experiments a first indication that gradient disparity can be used as an early stopping criterion for optimizers other than SGD.
32

---

Under review as a conference paper at ICLR 2021
2.4
22
p 0.83
gradient disparity
sgdm
2.2
gradient disparity
adagrad
gradient despenty
2.0
10
1.8
p= 0.704
1.66
1.4
1.2
1.0
0.8
1.2 10
10:
40
60
epochs
(a) SGD with Momentum, test loss epoch: 11,
(b) Adagrad, test loss epoch: 19,
GD epoch: 10
GD epoch: 18
loss mmsrrop
loss adam
2.50
gradient disparity
2.5
2.0
gradient disparity
2 25
0.438
gradnent disparng fty
1.8
0.781
gradient disper fty
1.6
1.5
1.4
1.50
1.2
1.0
1.00
epochs
(c) RmsProp, test loss epoch: 15 (loss: 1.43, en:: 54%).
(d) Adam, test loss epoch: 19,
GD epoch: (loss:1.16, err: 31%) %)
GD epoch: 20
2.2
test loss adegrad
2,00
Lest loss edadella
gradient disparity
2.75
gradient disparity
2.0
p 0.821
p= 0.58
gradient oisport cisporttyy
1.8
E 2.00
gredient
1.4
1.75
1.2
1.0
1.00
epachs
(c) Adagrad, test loss epoch: 21, GD epoch: 21
Adadelta, test loss epoch: 12, GD epoch:
2.75
loss mmsprpp
gradient disparity
2.50
gradient disparity
Gradiant desparity
2.25
p= 0.601
00
2.00
3.75
p= 0.115
150
1.50
125
100
1.00
10a
30-
307
epochs
(g) RRmsProp, test loss epoch: 20, GD epoch: 18
(h) Adam, test loss epoch: 12, GD epoch: 10
Figure 22: (a-d) VGG-19 configuration trained on 12.8 k training points of CIFAR-10 dataset. (e-h) VGG-11 configuration trained on 12.8 points of the CIFAR-10 dataset. The training is stopped when the training loss gets below 0.01. The presented results are an average over 5 runs. The captions below each figure give the epoch number where test loss and gradient disparity have re- spectively been increased for 5 epochs from the beginning of training. The Pearson correlation coefficient p presented each figure between gradient disparity and test loss.
33

---

Under review as a conference paper at ICLR 2021
H COMPARISON TO RELATED WORK
Min
GD/Var
EB
GSNR
9i 9j
sign(gs Mj) cos(g; 9j)
Oc
k-fold
No ES
TE TL
4.84
4.84
4.84
12.82
22.30
12.82
18.31
8.30
4.84
4.96
0.18
0.18
0.18
0.46
0.82
0.46
0.69
0.32
0.18
0.22
(a) MNIST, AlexNet
Min
GD/Var
EB
GSNR
9j
sign(g: 9j) cos 95)
k-fold
No ES
TE TI.
13.76
16.66
24.63
35.68
37.92
24.63
35.68
29.40
17.86
25.725
0.75
1.08
0.86
1.68
1.82
0.86
1.68
1.46
1.09
0.91
(b) MNIST, AlexNet, 50% random
Min
GD/Var
EB
GSNR
Ji 9j
sign( gj)
cos(g: 93)
k-fold
No ES
TE TL
45.54
45.95 1.45
61.76
70.46
70.46
55.84
67.09
67.37
51.64
64.19
1.32
1.68
1.92
1.92
1.52
1.83
1.85
1.49
1.98
(c) CIFAR-10. 10. ResNet-18
Min
GD/Var
EB
GSNR
9:
sign(g: 9j) cos(g; 9j)
k-fold
No ES
TE TL
59.77
71.97
73.17
77.08
75.91
65.80
75.43
77.71
72.56
75.96
1.75
2.00
2.03
2.12
2.13
1.93
2.07
2.13
2.02
2.30
(d) CIFAR-10, ResNet-18, 50% random
Table 8: Test error (TE) and test loss (TL) achieved by using various metrics as early stopping criteria. On the leftmost column, the minimum values of TE and TL over all the iterations are re- ported (which not accessible during training). The results of 5-fold cross validation are reported on the right-most column, which serve baseline. For each experiment, we have underlined those metries that result better performance than 5-fold cross validation. We observe that gradient disparity (GD) and variance of gradients (Var) consistently outperform k-fold cross validation, un- like other metrics. On the rightmost column (No ES) we report the results without performing early stopping (ES) (training is continued until the training loss below 0.01).
In Table 8 we compare gradient disparity (GD) to number of metrics that were proposed either directly as an early stopping criterion, or as a generalization metric. For those metrics that were not originally proposed early stopping criteria, we choose similar method for early stopping the one we use for gradient disparity. We consider two datasets (MNIST and CIFAR-10), and two levels of label noise (0% and 50%). Here is list of the metries that we compute in each setting:
Gradient disparity (GD) (ours): we report the error and loss values at the time when the value of GD increases for the 5th time (from the beginning of the training).
2. The EB-criterion (Mahsereci et al. 2017;: we report the error and loss values when EB becomes positive.
3. Gradient signal to noise ratio (GSNR) (I Liu et al.
2020 : report the error and loss values
when the value of GSNR decreases for the time (from the beginning of the training).
4. Gradient inner product, 9: 9j (Fort al. 2019):
report the error and loss values when the value of g; 9y decreases for the 5th time (from the beginning of the training).
5. Sign of the gradient inner product, sign(g: 95) (Fort al. 2019) report the error and loss values when the value of sign(g; 9j) decreases for the 5th time (from the beginning of the training).
2019): we report the 6. Cosine similarity between gradient vectors, cos(g: 9j) (Fort et al.
error and loss values when the value of cos(y; 93) decreases for the 5th time (from beginning of the training).
7. Variance gradients (Var) (Ngreea et al. 2019 we report the error and loss values when the value of Var increases for the 5th time (from the beginning of the training). Variance is computed over the same number of batches used to compute gradient disparity, in order to compare metrics given the same computational budget.
34

---

Under review as a conference paper at ICLR 2021
8. Average gradient alignment within the class, Ω Meehta et al. 2020): report the error and loss values when the value of She decreases for the 5th time (from the beginning of the training).
On the leftmost column of Table & we report the minimum values of the test error and the test loss over all the iterations, which may not necessarily coincide. For instance, setting (c), the test error is minimized at iteration 196, whereas the test loss is minimized at iteration 126. On the rightmost column of Table S we report the values of the test error and the test loss when using 5-fold cross validation, which serves as baseline.
interesting to observe that gradient disparity and variance of gradients produce the exact same results when used early stopping criteria (Table Sp. Moreover, these two are the only metrics that consistently outperform k-fold cross validation. However, in Section H.I] we observe that the correlation between gradient disparity and the test loss is in general larger than the correlation between variance of gradients and the test loss.
The EB-criterion, sign(g: gý)) and cos(g: 93) are metries that perform quite well as early stopping criteria, although not as well as GD and Var. In Section H.2 we observe that these metrics are not informative of the label noise level.
H.1 GRADIENT DISPARITY VERSUS VARIANCE OF GRADIENTS
It has been shown that generalization is related to gradient alignment experimentally Fort et al.) (2019), and to variance of gradients theoretically in Negrea et al. (019). Gradient disparity can be viewed as bringing the two together. Indeed, one can check that E [D,]] = 20 + +22 Pg - 2E [aT 9, given that Mo = E = E[g,] and o² = (Cov [od]) tr (Cov [z,l). This shows that gradient variance o and gradient alignment g
9 9j both appear as components of gradient disparity. We conjecture that the dominant term in gradient disparity is the variance of gradients, hence as early stopping criteria these two metrics almost always signal overfitting simultaneously. This is indeed what experiments show; show that variance of gradients is also a very promising early stopping criterion (Table However, because of the additional term in gradient disparity (the gradients inner product), gradient disparity emphasizes the alignment or misalignment of the gradient vectors. This could be the reason why gradient disparity in general outperforms variance of gradients in tracking the value of the general- ization loss; the positive correlation between gradient disparity and the test loss is often larger than the positive correlation between variance of gradients and the test loss (Table
Setting
PT.TL
PVar,
AlexNet, MNIST
0.433
0.169
AlexNet, MNIST, 50% random labels
0.535
0.161
VGG-16, CIFAR-10
0.190
0.324
VGG-16, VGG-16,CIFAR- CIFAR-10, 50% random labels
0.634
0.623
VGG-19, CIFAR-10
0.685
0.508
VGG-19, 10, 50% random labels
0.748
0.735
ResNet-18, CIFAR-10
0.975
0.958
R88Net-18, CIFAR-10, 50% random labels
0.471
0.457
Table 9: Pearson's correlation coefficient between gradient disparity (D) and test loss (TL) over the training iterations is compared to the correlation between variance of gradients (Var) and test loss.
35

---

Under review as a conference paper at ICLR 2021
H.2 CAPTURING LABEL NOISE LEVEL
In this section, we show in particular three metrics that even though perform relatively well as early stopping criteria, fail account for the level of label noise, contrary gradient disparity.
The sign the gradient inner product, sign(g: gj), should be inversely related to the test loss; it should decrease when overfitting increases. However, we observe that the value of sign(g. 9j) is larger for the setting with the higher label noise level; it incorrectly detects the setting with the higher label noise level as the setting with the better generalization performance (see Figure 23).
The EB-criterion should larger for settings with higher overfitting. In most stages of training, the EB-criterion does not distinguish between settings with different label noise levels, contrary to gradient disparity (see Figure (3). At the end of the training, the EB- criterion even mistakenly signals the setting with the higher label noise level as the setting with the better generalization performance.
The cosine similarity between gradient vectors, cos(g: .j)). should decrease when overfit- ting increases and therefore with the level of label noise in the training data. But cos(g: 9g) appears not be sensitive the label noise level, and in some cases (Figure (a) even increases with the noise level. Gradient disparity is much more informative of the label noise level compared to cosine similarity and the correlation between gradient disparity and the test error is larger than the correlation between cosine similarity and the test accu- racy (see Figure
2.4
random
0% random
Gradient disparity
2.2
50% random
50% random
l055
2.0
T0st
1.4
10
10a
eoochs
epochs
criteriion
-0.05
0.8
-0.10
signlg.
0.6
0% random
0% random
-0.20
50% random
50% random
-0.25
10
101
epochs
epochs
Figure 23: Test loss, gradient disparity, EB-criterion Mahsereci et (2017), and sign(g: gj) for ResNet- 18 trained on the CIFAR-10 dataset, with 0% and 50% random labels. Gradient disparity, contrary to EB- EB-criterion and sign(g: gy), clearly distinguishes the setting with real labels from the setting with random labels.
36

---

Under review as a conference paper at ICLR 2021
Average gradient disparit
b00
0% label noise
25% lebel noise
0.3
orror
400
50% noise
cosig: 91
10
0%
label nuise
02
0% label
50
25% lobel noise
200
25% label noise
50% label noise
50% label noise
75%
lobal noise
75% lobel noise
0.0
10
10a herations
10'
10
10a
10
16 keretions
18a
lterations
(a) CIFAR-10, 10, ResNet-18
Average gradient disparity
0% label noise
100
gradient disparity
0% label noise
25% label nolse
25% label noise 50% label noise
25% label noise
50% label noise
150
cosig 91
50% lebel noise
0.4
0.2
12
10 tteraiion
12
10
10
16
10
10
10'
Iterations
Ferations
(b) MNIST, AlexNet
Figure 24: The test error (TE), average gradient disparity (D), and cosine similarity (cos(g: O3 )) dur- ing training with different amounts of randomness in the training labels for sets of experiments. (a) ResNet-18 18 trained on 12.8k points of the CIFAR- 10 training set. The Pearson correlation coeffi- cient between all the iterations is Pcos, TA = -0.0088, whereas the correlation between test error/generalization error and gradient disparity PT. 0.2029 and P 0.5268, respectively. (b) AlexNet con- figuration trained on 12.8k points of the MNIST dataset. The correlation between the test accuracy and cosine similarity is Poos.TA 0.7521 which is positive and relatively high for this experi- ment. Yet, is still lower than the correlation between test error and gradient disparity which (D = 0.8019. 9.
accuracy (TA) and cosine similarity (cos) over all levels of randomness and over
37


Reviews:
[{"review_id": "tBS9OjDAnfN", "reviewer": "AnonReviewer3", "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": "### After rebuttal ###\nThanks 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. \n\nFigure 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.\n\n### Original comment ###\nThis 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.\n\nHowever, there are several points not clear to me.\n1. 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. \n2. 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?\n3. 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?\n4. 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.\n5. 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "kiA3o9QHwf", "reviewer": "AnonReviewer4", "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": "Summary:\nThe 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.\n\nPros:\nOverall 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. \n\nCons:\n1. 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.\n\n2. 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. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "aeMJsGSkbC", "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": "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. \n\nMy main concern is related to the experimental setting: The experiments in Section 5 compares \n\n(a) k-CV with (1-1/k)N training samples + N/k validation samples; with\n\n(b) Gradient Disparity (GD) using  N training samples. \n\n\nWhy not also compare with \n\n(x1) Gradient Disparity (GD) using (1-1/k)N training samples; or maybe even\n\n(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}. \n\nIt seems unclear to me whether the advantage of GD comes from (i) better characterization of the generalization or (ii) sample size advantage. \n\n(x1) v.s. (a) and (x2) v.s. (b) could show whether GD better captures the generalization under same number of samples. \n\n(x1) v.s. (b) and (x2) v.s. (a) could show the benefit of increasing sample size. \n\nFinally, 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? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "MRIgTPZDYH0", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 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. \n\nThe 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. \n\nIn 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. \n\nOverall I vote for accept. \n\nPros: \n\nThe 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. \n\nCons: \n\nThere 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)?    \n\nAs a sanity check, maybe add an experiment comparing early-stopping with no early-stopping?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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