Optimization Variance:  Exploring Generalization Properties of DNNs
Authors: Xiao Zhang
Dongrui Wu
Haoyi Xiong
Bo Dai
Venue:  (2021)
Keywords: Double Descent
Neural Networks
Generalization

Abstract: Unlike the conventional wisdom in statistical learning theory, the test error of a deep neural network (DNN) often demonstrates double descent: as the model complexity increases, it first follows a classical U-shaped curve and then shows a second descent. Through bias-variance decomposition, recent studies revealed that the bell-shaped variance is the major cause of model-wise double descent (when the DNN is widened gradually). This paper investigates epoch-wise double descent, i.e., the test error of a DNN also shows double descent as the number of training epochs increases. Specifically, we extend the bias-variance analysis to epoch-wise double descent, and reveal that the variance also contributes the most to the zero-one loss, as in model-wise double descent. Inspired by this result, we propose a novel metric called optimization variance to measure the diversity of model updates caused by the stochastic gradients of random training batches drawn in the same iteration. This metric can be estimated using samples from the training set only but correlates well with the test error. The proposed optimization variance can be used to predict the generalization ability of a DNN, and hence early stopping can be achieved without using any validation set.

Under review as a conference paper at ICLR 2021
OPTIMIZATION VARIANCE: EXPLORING GENERAL- IZATION PROPERTIES OF DNNS
Anonymous authors Paper under double-blind review
ABSTRACT
Unlike the conventional wisdom in statistical learning theory, the test error of a deep neural network (DNN) often demonstrates double descent: as the model complexity increases, it first follows classical U-shaped curve and then shows a second descent. Through bias-variance decomposition, recent studies revealed that the bell-shaped variance is the major cause of model-wise double descent (when the DNN is widened gradually). This paper investigates epoch-wise double descent, i.e., the test error of DNN also shows double descent the number of training epoches increases. Specifically, we extend the bias-variance analysis to epoch-wise double descent, and reveal that the variance also contributes the most to the zero-one loss, as in model-wise double descent. Inspired by this result, we propose novel metric, optimization variance (OV). to measure the diversity of model updates caused by the stochastic gradients of random training batches drawn in the same iteration. OV can be estimated using samples from the training set only but correlates well with the (unknown) test error. It can be used to predict the generalization ability of a DNN when the zero-one loss is used in test, and hence early stopping may be achieved without using a validation set.
INTRODUCTION
Deep Neural Networks (DNNs) usually have large model capacity, but also generalize well. This violates the conventional VC dimension (Vapnik 1999) or Rademacher complexity theory (Shalev- Shwartz & Ben-David] 2014), inspiring new designs of network architectures (Krizhevsky et al.
Simonyan & Zisserman 2015 He et al. 2016 Zagoruyko & Komodakis 2016) and reconsid-
eration of their optimization and generalization (Zhang et al. 2017 Arpit et al. 2017 Wang et al,, 2018
Kalimeris et al. 2019 Rahaman et al. 2019
et al. 2019).
Model-wise double descent, i.c., as a DNN's model complexity increases, its test eтror first shows
classical U-shaped curve and then enters second descent, has been observed on many machine learning models (Advani & Saxe 2017]: Belkin et al., 2019a; Geiger et al., 2019 Maddox et al.,
2020 Nakkiran et (0200). Multiple studies provided theoretical evidence of this phenomenon
in some tractable settings (Mitra 2019 Hastie et al. 2019 Belkin et al. 2019b Yang et al. 2020
Bartlett et al. 2020 Muthukumar et al., 2020). Specifically, Neal al. (2018) and Yang et 2020
performed bias- variance decomposition for mean squared error (MSE) and the cross-entropy (CE)
loss, and empirically revealed that the bell-shaped curve of the variance the major cause of model-
wise double descent. Maddox et al. (2020) proposed to measure the effective dimensionality of the
parameter space, which can be further used to explain model-wise double descent.
Recently, a new double descent phenomenon, epoch-wise double descent, was observed, when in- creasing the number of training epochs instead of the model complexity (Nakkiran et al. 2020). Compared with model-wise double descent, epoch-wise double descent relatively less explored. Heckel & Yilmaz (2020) showed that epoch-wise double descent occurs in the situation where dif- ferent parts of DNNs are learned at different epochs, which can be eliminated by proper scaling of step sizes. ZZhang & Wu (2020) discovered that the energy ratio of the high-frequency components of DNN's prediction landscape, which reflect the model capacity, switches from increase to
In practice, some label noise is often added to the training set to make the epoch-wise wise double descent more conspicuous.

---

Under review as a conference paper at ICLR 2021
decrease at certain training epoch, leading to the second descent of the test enror. However, this metric fails to provide further information on generalization, such as the early stopping point, or how the size of DNN influences its performance.
This paper utilizes bias-variance decomposition of the zero-one (20) loss (CE loss is still used in training) to further investigate epoch-wis, mooch-wise double descent. By monitoring the behaviors of the bias and the variance, we find that the variance plays an important role in epoch-wise double descent, which dominates and highly correlates with the variation of the test error.
Though the variance correlates well with the test error, estimating its value requires training models on multiple different training sets drawn from the same data distribution, whereas in practice usually only one training set is available Inspired by the fact that the source of variance comes from the candom--smpler training sets, we propose a novel metric, optimization variance (OV). measure the diversity of model updates caused by the stochastic gradients of random training batches drawn in the same iteration. This metric can be estimated from a single model using samples drawn from the training set only. More importantly it correlates well with the test error, and thus can be used to determine the early stopping point DNN training, without using any validation set.
Some complexity measures have been proposed to illustrate the generalization ability of DNNs, such as sharpness (Keskar et 2017) and norm-based measures (Neyshabur et al.] (2013). However, their values rely heavily on the model parameters, making comparisons across different models very dif- ficult. Dinh et al. (017)) shows that by re-parameterizing a DNN, one can alter the sharpness of its searched local minima without affecting the function it represents; Neyshabur that these measures cannot explain the generalization behaviors when the size of a DNN increases. Our proposed metric, which only requires the logit outputs of DNN, is less dependent on model parameters, and hence can explain many generalization behaviors, e.g., the test error decreases as the network size increases. Chatterji et (2020) proposed metric called Model Criticality that can explain the superior generalization performance of some architectures over others, yet it is unex- plored that whether this metric can be used indicate generalization the entire training procedure, especially for some relatively complex generalization behaviors, such as epoch- double descent.
al. (2018) shows
To summarize, our contributions are:
We perform bias-variance decomposition the test error to explore epoch-wiss double descent. We show that the variance dominates the variation of the test classification error.
We propose novel metric, OV, which is calculated from the training set only and correlates well with the test classification error.
Based the OV, we propose approach to search for the early stopping point without using a validation set, when the zero-one loss is used in test. Experiments verified its effectiveness.
The remainder of this paper is organized as follows: Section 2 and variance over training epochs. Section SectionB]propose proposes the OV and demonstrates its ability to indicate the test behaviors. Section draws conclusions and points out some future research directions.
introduces the details of tracing bias
2 BIAS AND VARIANCE IN EPOCH- WISE DOUBLE DESCENT
This section presents the details of tracing the bias and the variance during training. We show that the variance dominates the epoch-wise double descent of the test error.
2.1 A UNIFIED BIAS- VARIANCE DECOMPOSITION
Bias-variance decomposition widely used to analyze the generalization properties of machine learning algorithms (Geman et al., 1992, Friedman et al. 2001). It was originally proposed for
2 AAssume training set has n samples. can partition it into multiple smaller training sets, each with m samples (m < n)), and then train multiple models. However, the variance estimated from this case would be different from the one estimated from training sets with samples. We can also bootstrap the original training set into multiple ones, each with n samples. However, the data distribution of each bootstrap replica is different from the original training set, and hence the estimated variance would also he different.
2

---

Under review as a conference paper at ICLR 2021
the MSE loss and later extended to other loss functions, e.g., CE and ZO losses (Kong & Dietterich 1998). Our study utilizes a unified bias variance decomposition that was proposed by Domingos (2000) and applicable arbitrary loss functions.
1993 Tibshirani 1996; Kohavi et al.
Let (a, t) be a sample drawn from the data distribution D, where æ E IR denotes the d- dimensional input, and t E R the one-hot encoding of the label in classes. The training set T = ( ++) ~ "D' is utilized to train the model f I2d + R Let y = f(=; E IR be the probability output of the model f trained on T. and L(t. y) the loss function. The expected loss [[t, y)] should be small to ensure that the model both accurately captures the regularities in its training data, and also generalizes well unseen data.
According to Domingos (2000), unified bias- -las-variance decomposition of (T is:
Ey [t v)]
C(t, 9) +3 E
(C(.
Bias
Variance
where B takes different values for different loss functions, and y is the expected output:
y arg min
Eyl"("",
y' Σi- 10
minimizes the variance term in which can be regarded as the "center" or "ensemble" of y w.r.t different T.
Table [ shows specific forms of L, y. and | for different loss functions (the detailed derivations can be found in Appendix [A). This paper focuses on the bias-variance decomposition of the ZO loss, because epoch-wise double descent of the test error is more obvious when the 70 loss is used (see Appendix Cp. To capture the overall bias and variance, we analyzed Ezz, E y)), i.e., the expectation of ET y)] over the distribution D.
Table 1: Bias- decomposition for different loss functions. The CE loss herein is the com- plete form of the commonly used one, originated from the Kullback-Leibe Leibler divergence. Z = Ek=1 exp(EE {E, yul) is normalization constant independent of k. H(-) is the hard-max which sets the maximal element to 1 and others to 0. con } is an indicator function which equals 1 its argument true, and 0 otherwise. log and exp are element-wise operators.
Loss
C(t, y)
B
MSE CE
v1 k==1 to log la
Eyy (ET log 2
1
1
1
yi
1 if t, otherwise
ZO
1 (H(t) * H(v)}
H(E)(H(y))
- PP (H(y) = t/ / H(y))
2.2 TRACE THE BIAS AND VARIANCE TERMS OVER TRAINING EPOCHS
Pa,eBy To trace the bias term Ez.e [Lt,, 7)) and the variance term E., By (C y) w.r.t the training epoch, we need to sample several training sets and train models on them respectively, so that the bias and variance terms can be estimated from them.
Concretely, let T denote the test set, f(x; T,.9) the model f trained on T, ~ D= (j = 1, 1,,,... K) for q epochs. Then, the estimated bias and variance terms the q-th epoch, denoted as B(g) and V(g), respectively, can be written as:
B(g)= B(a,)JT--
C (t,
(3)
K Σ
(gg) E(
(4)
K
j=1
II real-world situations, the expected loss consists of three terms: bias, variance, and noise. Similar to Yang al. 2020), view the groundtruth and ignore the noise term.
3

---

Under review as a conference paper at ICLR 2021
where
f(x:9) =
Σ [H(f(=:T,)))
(5)
the voting result of (f(z;; ({:))))
We should emphasize that, in real-world situations, D cannot be obtained, hence T, in our exper- iments was randomly sampled from the training set (we sampled 50% training data for each T,), As result, despite of showing the cause of epoch- wise double descent, the behaviors of bias and variance may be different when the whole training set is used.
We considered ResNet (He al. 2016) and VGG (Simonyan Zisserman, 2015) model trained on SVHN (Netzer et al. 2011). CIFARIO (Krizhevsky) 2009), and CIFARTOU 1O0 (Krizhevsky 2009). SGD and Adam (Kingma & Ba 2014) optimizers with different learning rates were used. The batchsize was set to 128, and all models were trained for 250 epochs with data augmentation. Prior
to sampling {T,} (K = 5) from the training set, 20% labels of the training data were randomly shuffled to introduce epoch-wise double descent.
Figure M shows the expected ZO loss and its bias and variance. The bias descends rapidly at first and then generally converges to low value, whereas the variance behaves almost exactly the same as the test error, mimicking even small fluctuations of the test error. To stabilize that, we performed additional experiments with different optimizers, learning rates, and levels of label noise (see Appen- dices [ and G All experimental results demonstrated that it is mainly the variance that contributes epoch-wise double descent.
VGG11
VGG13
VGG16
0.40
loss/blssvar
0.25
loss/biasiva
0.35
loss/blas/var
blas
loss
0.20
var
0.15
0.25
0.6
0.20
0.10
0.05
0.10
59
100
350
200
250
50
100
150
200
250
50
100
150
200
250
epoch
epoch
epoch
ResNet18
ResNet18
ResNet34
loss/bias/var
0.25
(oss/bias/var
0.35
loss/blas/var
0.30
0.20
0.20
0.5
0.10
0.15
0.4
0.10
50
100
150 epoch
200
250
50
100
150
200
250
50
100
150
200
250
epoch
epoch
(a) SVHN
(b) CIFARIO
(c) CIFAR100
Figure 1: The expected test 70 loss and its bias and variance. The models were trained with 20% label noise. Adam optimizer with learning rate 0.0001 was used.
2.3 DISCUSSION
Contradicting the traditional view that the variance keeps increasing because of overfitting, our experimental results show more complex behavior: the variance starts high and then decreases rapidly, followed by bell curve. The difference at the beginning (when the number of epochs is small) is mainly due to the choice of loss functions (see experimental results of bias-variance de- composition for MSE and CE losses in Appendix(F). CE and MSE losses, analyzed the traditional
from http://ss///ttttooooooooooaoo/gs

---

Under review as a conference paper at ICLR 2021
learning theory, can reflect the degree of difference of probabilities, whereas the ZO loss only the labels. At the early stage of training, the output probabilities are close to random guesses, and hence small difference in probabilities may lead to completely different labels, resulting in the distinct variance for different loss functions. However, the reason why the variance begins to diminish at the late phase of training is still unclear. We will explore this problem in our future research.
OPTIMIZATION VARIANCE (OV)
This section proposes new metric, OV, to measure the diversity of model updates introduced by random training batches during optimization. This metric can indicate test behaviors without any validation set.
3.1 NOTATION AND DEFINITION
Section 2 verified the synchronization between the test error and the variance, but its application is limited because estimating the variance requires: 1) a test set, and, 2) models trained on different training sets drawn from the same data distribution. It'd be desirable to capture the test behavior of a DNN using a single training set only, without a test set.
According to the definition in TT. the variance measures the model diversity caused by different training samples drawn from the same distribution, i.c., the outputs of DNN change according to the sampled training set. As the gradients to models during the optimization of DNN, we need to measure the variance of a DNN introduced by the gradients calculated from different training batches. More specifically, we'd 'dd like to develop a metric to reflect the function robustness of DNNs to sampling noises. If the function captured by
usually the only information transferred from training sets
DNN drastically varies w.r.t. different training batches, its generalization error is very likely to be poor due to large variance introduced by the optimization procedure. A similar metric is the sharpness of local minima proposed by Keskar al. (2017) which measures the robustness of local minima as an indicator of the generalization error. However, this metric is only meaningful for local minima and hence cannot be applied the entire optimization process.
Mathematically, for sample (ax, t) ~ D, let f(z; 0) be the logit output of DNN with parameter TB + IR ( the optimizer outputting the
O. Let TB ~ Dm be a training batch with m samples, update of based on TB. Then, we can get the function distribution Fi (TB) over a training batch TB. i.e., f(=; 0 - (TBB) ~ Fz (TB). The variance of F. (TB) reflects the model diversity caused by different training batches. The formal definition of OV is given below.
Definition (Optimization Variance (OV)) Given an input x and model parameters 0g at the q-th training epoch, the OV on a at the q-th epoch is defined as
ET [I 02 + g(TB)) - fx; 0g + ((BB))
(v₂(x)
(6)
ET (ax 0g + g(TB)))
Note that (z)) measures the relative variance, because the denominator in eliminates the influence of the logit's norm. In this way, (V,(z) at different training phases can be compared. The motivation here comes from the definition of coefficient of variation F (CV) in probability theory and statistics, which is also known the relative standard deviation. CV defined as the ratio between the standard deviation and the mean, and is independent of the unit in which the measurement is taken. Therefore, CV enables comparing the relative diversity between two different measurements.
In terms of OV, the variance of logits, i.e., the numerator of OV, is not comparable across epochs due to the influence of their norm. In fact, even if the variance of logits maintains the same during the whole optimization process, its influence on the decision boundary is limited when the logits are large. Consequently, by treating the norm of logits as the measurement unit, following CV we set OV to E, of/ E; 14, where a; and μ4 represent the standard deviation and the mean of the i-th logit, respectively. If we remove the denominator, the value of OV will no longer has the indication ability for generalization error, especially at the early stage of the optimization process.
https://en http:://ewwwiiiidiiaaaoooeo
5

---

Under review as a conference paper at ICLR 2021
Intuitively, the OV represents the inconsistency of gradients' influence the model. If OV₂(2)) is very large, then the models trained with different sampled TB may have distinct outputs for the same input, leading to high model diversity and hence large variance. Note that here we emphasize the inconsistency of model updates rather than the gradients themselves. The latter can be measured by the gradient variance. The gradient variance and the OV different, because sometimes diverse gradients may lead to similar changes of the function represented by DNN, and hence small OV. More on the relationship between the two variances can be found in Appendix B
3.2 EXPERIMENTAL RESULTS
We calculated the expectation of the OV over æ; i.e., E.z (OV, which was estimated from 1,000 random training samples. The test set was not involved at all.
Figure 2 shows how the test accuracy (solid curves) and E= (dashed curves) change with the number of training epochs. Though sometimes the OV may not exhibit clear epoch- double descent, e.g., VGGI6 in Figure 2(c) the symmetry between the solid and dashed curves generally exist, suggesting that the OV, which calculated from the training set only, is capable of predicting the variation of the test accuracy. Similar results can also be observed using different optimizers and learning rates (see Appendix I].
VGG11
VGG13
VGG16
0.0225
0.0025
0.0025
0.6-
0.-
-0.022
0.0020
+0.0020
0%
0.8
-0.0335
0.8
0.0015
SEC
0.4
OV, 0%
-0.0015
0.7
0.0000
0.7
0.0010
acc, 20%
0.0010
0.6
0.0005
0.6
0.0005
0.0005
50
100
150
200
0.0000
0.5
160
200
0
0000
5.0
50
100
200
0. 0.0000
epoch
epoch
epoch
ResNet18
ResNet18
ResNet33
0.0025
0.0025
0.0025
0.0220
0.0020
0.6
0.0020
0.8
0.0355
0.0015
0.0015
0.7
0.7
0.001
-0.0000
0. 0.0010
0.6
Trap An
0.0005
0.0005
0.0075
0.5
50
200
0.0000
0.
100
200
0 0000
3.0
200
0.0000
epoch
epoch
epoch
(a) SVHN
(b) CIFARIO
(c) CIFAR100
Figure 2: Test accuracy and OV. The models were trained with Adam optimizer (learning rate 0.0001). The number in each legend indicates its percentage of label noise.
Note that epoch-wise double descent is not necessary condition for applying OV. As shown in Figure 2 (blue curves), we compared the values of OV and generalization errors of DNNs when there are 0% label noises, from which we can see the curves of generalization errors have no epoch- wise double descent, yet the proposed OV still works pretty well.
(V2(z) in Figure 2 was estimated on all training batches; however, this may not be necessary: small number of training batches are usually enough. To demonstrate this, we trained ResNet and VGG on several datasets using Adam optimizer with learning rate 0.0001, and estimated OV₂(*) from different number of training batches. The results in Figure show that we can well estimate the OV using as few as 10 training batches.
Another intriguing finding is that even unstable variations of the test accuracy can be reflected by the OV. This correspondence is clearer on simpler datasets, e.g., MNIST (LeCun et al. 1998) and FaSHionMNIST (Xiao et al. 2017). Figure 4 shows the test accuracy and OV for LeNet-5 (LeCun jet al. 1998) trained on MNIST and FashionMNIST without label noise. Spikes of the OV and the test accuracy happen simultaneously the same epoch.

---

Under review as a conference paper at ICLR 2021
VGG11
VGG13
VGG16
0.0025
0.0025
0.0025
100
0.0020
0.0020
20
200
0.0015
0.000
0.0015
50
0.0010
0.0010
0.0010
0.0005
0.0005
0.0005
0.0000
0.0000
0.0000
50
100
150
200
250
50
100
150
200
250
50
100
150
200
250
epoch
epoch
epach
ResNet18
ResNet18
ResNet34
0.0025
0.0025
0.0025
0.0020
0.00220
0.0020
0.0015
0.0033
0.0015
0.0010
0.0010
0.0010
0.0005
0.0008
0.0005
0.0000
5o
1000
150
200
250
0.0000
100
150
200
250
0.0000
100
150
200
250
epoch
epoch
epoch
(a) SVHI
(b) CIFARIO
(c) CIFARI00
Figure 3: OV estimated from different number of training batches. The models were trained with 20% label noise. Adam optimizer with learning rate 0.0001 was used.
0.0020
0.94
0.0020
0.99
0.0015
0.92
0.0015
acc
0.0010
A0
acc
0.90
acc
0.0010
00
OV
OV
0.0005
0.88
0.0005
0.97
0.0000
0.86
0.0000
50
100
150
200
250
50
100
150
200
250
epoch
epoch
(a) MNIST
(b) FaShionMNIST
Figure 4: Test accuracy and OV. The model was LeNet-5 trained on MNIST and FashionMNIST with Adam optimizer (learning rate 0.0001).
Our experimental results demonstrate that the generalization ability DNN can be indicated by the OV during stochastic training. without using validation set. This phenomenon can be used to determine the early stopping point, and beyond.
3.3 EARLY STOPPING WITHOUT A VALIDATION SET
The common process to train DNN involves three steps: 1) partition the dataset into training set and a validation set; 2) use the training set to optimize the DNN parameters, and the validation set to determine when stop training, i.c.. carly stopping, and record the carly stopping point; 3) train the DNN on the entire dataset (combination of training and validation sets) for the same number of epochs. However, there is guarantee that the early stopping point the training set is the same as the one on the entire dataset. So, an interesting questions is: is it possible to directly perform early stopping the entire dataset, without validation set?
The OV can be used for this purpose. For more robust performance, instead of using the OV directly, may need smooth it to alleviate random fluctuations.

---

Under review as a conference paper at ICLR 2021
As example, smoothed the OV by moving average filter of 10 epochs, and then performed early stopping on the smoothed OV with a patience of 10 epochs. As a reference, early stopping with the same patience should be noted that the latter unknown in real-world applications. is provided for verification purpose only.
also performed directly on the test accuracy to get the groundtruth. However,
We trained different DNN models on several datasets (SVHN: VGG11 and ResNet18; CIFARIO: VGG13 and 8 CIFARI00: VGGI6 and ResNer34) with different levels of label noise (10% and 20%) and optimizers (Adam with learning rate 0.001 and 0.0001, SGD with momentum 0.9 and learning rate 0.01 and 0.001). Then, we compared the groundtruth early stopping point and the test accuracy with those found by performing early stopping Figure 5 The true early stopping points and those found from the OV curve were generally close, though there were some exceptions, e.g., the point near (40, 100) in Figure ((a) However, the test errors, which are what a model designer really cares about, were always close.
the OV The results are shown in
90
0.5
70
0.4
Found
Found
0.3
50
SVHN, VGG
SVHN, Res
0.2
cr10, VGG
30
CF10, Res
0.1
CF100, VGG
10
30
50
90
0.0
0.1
0.2
0.4 0.5
True
True
(a) Early stopping point
(b) Test error
Figure 5: Early stopping based test error (True) and the corresponding OV (Found). The shapes represent different datasets, whereas the colors indicate different categories of DNNs ("CF" and "Res" are short for "CIFAR" and "ResNet", respectively).
3.4 SMALL SIZE OF THE TRAINING SET
For large datasets, validation set can be casily parti- tioned from the training set without hurting the gener- alization performance. Therefore, OV is more useful in the case of small datasets. To this end, we performed ex- periments with small numbers (2000, 4000, 6000) of the training samples in CIFAR10 to verify the effectiveness of OV this situation. Considering the limited numbers of training samples, we trained small Convolution Neu- ral Network (CNN) using Adam optimizer with learning rate 0.0001, whose detailed information can be found in Appendix H
0.0040
0.6
0.0635
0.0030
acc
2000
0.0025
acc, 4000
OV. 4000
6000
0.0020
0.3
0.0015
02-
0.0005
50
100
150
200
250
epoch
Figure 6: Test accuracy and OV using small sizes of training sets. The num- bers represent how many training sam- ples are used for training.
The experimental results are shown in Figure 6 It can be observed that: a) When the size of the training set is small, OV still correlates well with the generalization per- formance as a function of the training epochs, which ver- ifies the validity of our results on small datasets; b) As expected, more training samples usually lead to better generalization performance, which can also be reflected by comparing the values of OV.
Training VGG11 SVHN with Adam optimizer and learning rate 0.001 was unstable (see Appendix D did not include its results in Figure
8

---

Under review as a conference paper at ICLR 2021
3.5 NETWORK SIZE
In addition to indicating the early stopping point, the OV can also explain some other generalization behaviors, such the influence of the network size. To verify that, we trained ResNet18 with different network sizes on CIFARIO for 100 epochs with no label noise, using Adam optimizer with learning rate 0.0001. For each convolutional layer, we set the number of filters k/4 (k: = 1,2.... times the number of filters in the original model. We then examined the OV of ResNer18 with different network sizes to validate its correlation with the test accuracy. Note that we used SGD optimizer with learning rate 0.001 and no momentum calculate the OV, so that the cumulative influence during training can be removed to make the comparison more fair.
The results shown in Figure 7 As k increases, the OV gradually decreases, i.c., the diversity of model updates introduced by different training batches decreases when widening ResNet18, suggesting that increasing the net- work size can improve the model's 's' resilience to sampling noise, which leads to better generalization performance. The Pearson correlation coefficient between the OV and the test accuracy reached - -0.94 (p 0.0006).
0.92
0.0008
0.0006
0.0004
0.0002
0.86
width
Lastly, we need to point out that we did not observe strong cross-model correlation between the OV and the test accuracy when comparing the generalization ability of significantly different model architectures, e.g., VGG and ResNet. Our future research will look for more universal cross-model metric to illustrate the generalization performance.
Figure 7: Test accuracy and OV w.r.t the network size.
CONCLUSIONS
This paper has shown that the variance dominates the epoch-wise double descent, and highly cor- relates with the test error. Inspired by this finding, we proposed a novel metric called optimization variance, which is calculated from the training set only but powerful enough to predict how the test error changes during training. Based on this metric, we further proposed an approach to perform early stopping without any validation set. Remarkably, we demonstrated that the training set itself may be enough to predict the generalization ability of a DNN, without dedicated validation set.
Our future work will: 1) apply the OV to other tasks, such as regression problems, unsupervised learning, and on; 2) figure out the cause of the second descent of the OV; and, 3) design regular- ization approaches to penalize the OV for better generalization performance.
REFERENCES
Madhu S Advani and Andrew M Saxe. High-dimensional dynamics of generalization error in neural networks. CoRR, abs/1710.036677 2017.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In Proc. 36th Int'l Conf. on Machine Learning, pp. 242-252, Long Beach, CA, May 2019.
Devansh Arpit, Stanislaw Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxin- der S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien. A closer look at memorization in deep networks. In Proc. 34th Int'l Conf. on Machine Learning, volume 70, pp. 233-242, Sydney, Australia, August 2017.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020. In press.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learn- ing practice and the classical bias fias-variance trade-off. Proceedings of the National Academy of Sciences, 15632)):5549-1155 2019a.

---

Under review as a conference paper at ICLR 2021
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. CoRR, abs/1903.07571, 2019b.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Niladri Chatterji, Behnam Neyshabur, and Hanie Sedghi. The intriguing role of module criticality in the generalization of deep networks. In Proc. Int'l Conf. on Learning Representations, Addis Ababa, Ethiopia, April 2020.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In Proc. 34th Int'l Conf. on Machine Learning, volume 70, pp. 1019-1028, Sydney, Australia, August 2017.
Pedro Domingos. A unified bias-variance decomposition for zero-one and squared loss. In Proc. of the 17th National Conf. on Artificial Intelligence, pp- 564-569, Austin, TX, July 2000.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. The Elements of Statistical Learning, vol- ume 1. Springer series in statistics New York, second edition, 2001.
Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' A'Acolii, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number of parameters in deep learning. CoRR, abs/1901.01 608, 2019.
Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/variance dilemma.
Neural Computation, 4(1):1-58, 1992.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. CoRR, abs/1903 18000900,,,,,, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 770-778, Las Vegas, NV, June 2016.
Reinhard Heckel and Fatih Furkan Yilmaz. Early stopping deep networks: Double descent and how to eliminate it. CoRR, 0oss2007.11099, 2020.
Tom Heskes. Bias/variance decompositions for likelihood-bart based estimators. Neural Computation, 1066):1425-143, 1998.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. SGD on neural networks learns functions of increasing complexity. In Proc. Advances in Neural Information Processing Systems, pp. 3491-3501, Vancouver, Canada, December 2019.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In Proc. Int'l Conf. on Learning Representations, Toulon, France, April 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Proc. Int' I Conf. on Learning Representations, Banff, Canada, April 2014.
Ron Kohavi, David Wolpert, al. Bias plus variance decomposition for zero-one loss functions. In Proc. 13th Int'l Conf. on Machine Learning, volume 96, pp. 275-283, Bari, Italy, July 1996.
Eun Bae Kong and Thomas G Dietterich. Enror-correcting output coding corrects bias and variance. In Proc. 12th Int'l Conf. on Machine Learning, pp. 313-321, Tahoe City, CA, July 1995.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009. URL https:
7/ //www.com cs. toronto. wetpoott.edu//kkiii... /tw.:co..ooorccccc//////////eeaa feat ures- 2009 TR. pdf
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet classification with deep volutional neural networks. In Proc. Advances in Neural Information Processing Systems, pp. 1097-1105, Lake Tahoe, NE, December 2012.
10

---

Under review as a conference paper at ICLR 2021
Yann LeCun, Léon Bottou, Yoshua Bengio. and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-22 23244, 1998.
Wesley J Maddox, Gregory Benton, and Andrew Gordon Wilson. Rethinking parameter counting in deep models: Effective dimensionality revisited. CoRR, abs/2003.02139, 2020.
Partha Mitra. Understanding overfitting peaks generalization error: Analytical risk curves for l2 and ( penalized interpolation. CoRR, abs/ hess/996.03667, 2019.
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpo- lation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1(1): 67-83, 2020.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In Proc. Int'l Conf. on Learning Representations, Addis Ababa, Ethiopia, April 2020.
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and Ioannis Mitliagkas. A modern take on the bias-variance tradeoff in neural networks. CoRR, abs/ 100008800,,,91, 2018.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning- In Proc. NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, Granada, Spain, December 2011.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Proc. of the 28th Conf. Learning Theory, pp. 1376-1401, Paris, France, July 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring gener- alization in deep learning. In Proc. Advances in Neural Information Processing Systems, pp- 5947-5956, Long Beach, CA, January 2018.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In Proc. 36th Int'l Conf. on Machine Learning, pp. 5301-5310, Long Beach, CA, May 2019.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithns. Cambridge University Press, 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogmition. In Proc. Int'l Conf. on Learning Representations, San Diego, CA, May 2015.
Robert Tibshirani. Bias, variance and prediction error for classification rules. Technical report, Department of Preventive Medicine and Biostatisties and Department of Statisties, University of Toronto, Toronto, Canada, 1996.
Vladimir N Vapnik. An overview of statistical learning theory. IEEE Trans. on Neural Networks, 10(5):988 1999.
Huan Wang, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. Identifying generalization properties neural networks. CORR, abs/1809.07402., 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNNIST: novel image dataset for bench- marking machine learning algorithms. CoRR, abs/1708.007447, 2017.
Zitong Yang, Yaodong Yu, Chong You, Jacob Steinhardt, and Yi Ma. Rethinking bias-variance trade-off for generalization of neural networks. CoRR, abs/2002.1 1328, 2020.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. CoRR, abs/1605.07146, 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. Proc. Int'l Conf. on Learning Representa- tions, Toulon, France, April 2017.
Xiao Zhang and Dongrui Wu. Rethink the connections among generalization, memorization and the spectral bias of DNNs. CoRR, abs/2004. 13954, 2020.

---

Under review as a conference paper at ICLR 2021
A BIAS- VARIANCE DECOMPOSITION FOR DIFFERENT LOSS FUNCTIONS
This section presents detailed deduction of bias-variance decomposition for different loss functions.
A.1 THE MEAN SQUARED ERROR (MSE) Loss
For the MSE loss, we have [tt, y) = || 21ı. and need to calculate ý based on We first ignore the constraints and solve the following problem:
ÿ
arg min Ey y y122).
/'
whose solution is 9 = Ery. y. It can be easily verified that ý satisfies the constraints in and hence y Ery.
Then, we can decompose the MSE loss as:
Ey yااا E t y 7 1ー
E, t
y)
|L y 12 + Eylly - 0,
(8)
where the first term denotes the bias, and the second denotes the variance. We can also get 33 =
1.
A.2 CROSS-ENTROPY (CE) LOss
For C(t. Σi= 4x log 1 y can be obtained by applying the Lagrange multiplier
method (Boyd & Vandenberghe 2004) to P
1y = ET
Σ
v log
VE A
(1-
1
yk
(9)
Vk
==1
R=1
To minimize 1(y", A), we need to compute its partial derivatives to y and X:
0l
yis
ET
log
X, k= 1,2, .... c
yk
0l
1
vk.
0X
k=1
By setting these derivatives to 0, we get:
Uh = Exo(Erllog Z
k ==1,2,... 1,2,...,
(10)
where - Ei=r exp wkl) a normalization constant independent of k.
Because
Uk log Z,
E T
a
log
V
ag 1.
(11)
2k
k=1
we have:
ts
ts
Tk
ET
c
log
Ey
tk
log
+
log
1x
1/k
tk log
+
ET
t
log
yk
tu
Σ (a log
log Z
Dk
1x + Ey
Σ
Uk
t log
Th log
(12)
Th
k=
from which obtain 1.
12

---

Under review as a conference paper at ICLR 2021
A.3 THE ZERO-ONE (ZO) Loss
For the ZO loss, i.e., Ltt, y) = con (H()) o H(y)), y is the voting result, i.e., H(EE [H(y]), so that the variance be minimized. However, the value of [ depends the relationship between y and t.
When ÿ t, we have:
By Loo (H(t) H(y)} + Ey 1con (H(Ø) + H(y)
con (H(t) + H |)} + By 1con (H(Ø) + H(y)),,
(13)
clearly, 3=1 1.
When ÿ * t, we have:
Ey cou (H(I) & H(y)}
Pr =1 -y (H( =t) Lcon (H(t) H
= Pr ( =(((()) =g) Py (H(y) 7)
PT (H(y) = +(H()) # 9) PT (H(y) + g)
(14)
Since ÿ + H(t), follows that
PT (H(y) = t|H(z) D) =
(15)
Then, 14
becomes:
E, 1con (H(t) & H(y))
= Icon (H(t) + H(Ø) PT (H(y) = H(y) + 9) PT (H(y) + 7)
= 1con (H(t) + Hg))
Pr (H(g) = H + 3 E, [I (H( + H(y)
(16)
hence, B= -p (H(y) t(((n) * Ø)
B CONNECTIONS BETWEEN THE OPTIMIZATION VARIANCE AND THE GRADIENT VARIANCE
This section shows the connection between the gradient variance and the optimization variance in Definition 1
For simplicity, we ignore g in OV, and denote g(Tn) - -ETa((TT) by (TB).. Then, the gradient variance Vg be written as:
Vn, ETd [Io(TT) (TTg((TT) = ETa ([(T))"{(TT))
(17)
Denote the Jacobian matrix of the logits f(x; 0) w.r.t. A by Jo (=(x), i.c.
Jo (Vofi 0). Vofz(2; .).... Vofc(2; 0)]
(18)
where f5( 0) is the j-th entry of [(x; 0), and the number of classes. Using first order approximation, we have:
f(x; 0 + s(TR)) ~ (x:;0) + " ((Tn),
(19)
and OV (æ) can be written as:
By, (TTB) x: Jo ((BB)
ET Jo ((TB)
OV (x)
(20)
(( ETg (0 (1g((a)) (TB [
O(x;0)
The only difference between Ex, [OV()) and Vg the middle weight matrix E,, This suggests that penalizing the gradient variance also reduce the optimization variance.
Jo(
J( f(
13

---

Under review as a conference paper at ICLR 2021
Figure presents the curves of Vg in the training procedure. It can be observed that Vg also shows some a ability to indicate the generalization performance. However, compared with the results in Figure we can see that OV demonstrates stronger power for indicating the generalization error than g- More importantly, Vg loses its comparability when the network size increases, while OV Jo(a))Jo(a)) to can be more reliable to architectural changes with the middle weight matrix Ex 7(.00) [(x,) normalize yg which is illustrated in Figure
We also notice that (BB))((B)ll )l2 is usually far less than ETg (19(TB) hence V, and the gradient norm ET (T )12 almost present the same curves in the training procedure.
VGG11
VGG13
VGG16
1.0
15.
20
30
17.5
25
15.
0.5
aec. DRK
ecc, 20%
-20
Vp 0%
2g.20% 20%
15.5
0.3
10
0-6
0.2
0.5
100
150
0.0
200 opoch
200
0.1
159
epach
opoch
ResNet18
ResNet18
Res/Ne33
2.0
15.0
12.5
0.9
20
15.0
125
0.8
1000
0.4
755
0.6
0.3
550
-355
0.5
100
150
0.0
epoch
epoch
epoch
(a) SVHN
(b) CIFARIO
(c) CIFAR100
Figure 8: Test accuracy and Vg. The models were trained with the Adam optimizer (learning rate 0.0001). The number in each legend indicates its percentage of label noise.
C BEHAVIORS OF DIFFERENT Loss FUNCTIONS
Many different loss functions can be used evaluate the test performance of model. They may have very different behaviors w.r.t. the training epochs. As shown in Figure / the epoch-wise double descent can be very conspicuous
test error, i.e., the ZO loss, but barely observable on CE and MSE losses, which increase after the early stopping point. This is because at the late stage of training. model outputs approach 0 or resulting in the increase of the CE and MSE losses on the misclassified test samples, though the decision boundary may be barely changed. When rescaling the weights of the last layer by positive real number, the ZO loss remains the same because of the untouched decision boundary, whereas the CE and MSE losses are changed. Thus, we perform bias-variance decomposition on the ZO loss to study epoch-wise double descent.
D VGGH ON SVHN BY ADAM OPTIMIZER WITH LEARNING RATE 0.001
Training VGGI1 on SVHN by Adam optimizer with learning rate 0.001 is unstable, as shown in Figure 14(a) Figure 10 the test error and optimization variance. For 0% and 10% label noise, the test error stays large (the test accuracy is low) for a long period in the early phase of training. The optimization variance is also abnormal.
E LOSS, BIAS AND VARIANCE W.R.T. DIFFERENT LEVELS OF LABEL NOISE
Label noise makes epoch-wite wise double descent more conspicuous to observe Nakkiran et al. 2020). If the variance is the major cause of double descent, it should match the variation of the test error
14

---

Under review as a conference paper at ICLR 2021
0.8
CIFAR1O CIPAR100
loss
0.6
loss
0.2
0.2
50
100
150 epach
200
250
50
100
150
200
250
50
100
150
200
250
epach
epach
(a) CE loss
(b) MSE loss
(c) ZO loss
Figure 9: Different loss functions w.r.t the training epoch. ResNet18 was trained on SVHN, CI- FAR10, and CIFARIOO with 20% label noise to introduce epoch-wise double descent. Adam opti- mizer with learning rate 0.0001 was used.
1.0
3.25
1.0
0.05
1.0
0.03
0.8
3.34
0.8
0.04
0.9
0.04
9.03
0.5
3Cc
0.0
0.0
60
20
200
80
102
20
40
100
epoch
epoch
epoch
(a) 0% label noise
(b) 10% label noise
(c) 20% label noise
Figure 10: Test accuracy and optimization variance (OV) of VGG11 on SVHN, w.r.t. different levels of label noise. Adam optimizer with learning rate 0.001 was used.
when adding different levels of label noise. Figure 11 shows example to compare the loss, vari- ance, and bias w.r.t. different levels of label noise. Though label noise impacts both the bias and the variance, the latter appears to be more sensitive and shows better synchronization with the loss. For instance, when we randomly shuffle a small percentage of labels, say 10%. a valley clearly occurs between 20 and 50 epoches for the variance, whereas it is less obvious for the bias. In addition, it seems that the level of label noise does not affect the epoch at which the loss reaches its first min- imum. This is surprising, because the label noise is considered highly related the complexity of the dataset. Our future work will explore the role label noise plays in the generalization of DNNs.
Loss
Var
Bias
0.4
0.6
0.4
0.4
0.4
0.5
0.5
label noise
0.3
0.3
0.3
0.3
0.4
0.2
0.2
0.2
0.3
0.3
0.2
0.1
0.2
0.1
0.1
0.1
0.1
100
200
100
200
100
200
epoch
epoch
epoch
Figure 11: Loss, variance and bias w.r.t. different levels of label noise. trained CIFARI0. Adam optimizer with learning rate 0.0001 was used.
The model was ResNet18
15

---

Under review as a conference paper at ICLR 2021
F
BIAS AND VARIANCE TERMS W.R.T. DIFFERENT LOSS FUNCTIONS
VGG11
VGG13
VGG16
0.010
loss
0.06
loss/bias/var
loss/bias/var
blas
loss/blas/a
0.008
var
0.04
0.006
0.03
0.004
0.02
0.02
0.000
150
250
50
250
250
100
200
250
epoch
epoch
epoch
ResNet18
ResNet18
ResNet34
loss/bias/var
less/bias/var
0.008
0.05
Dss/blas/var
0.04
0.006
0:03
0.01
0.01
0.002
0.00
250
50
150
200
250
epoch
epoch
epoch
(a) SVHN
(b) CIFARIO
(c) CIFARIO0
Figure 12: Test MSE loss and the corresponding bias/variance terms. The models were trained with 20% label noise. Adam optimizer with learning rate 0.0001 was used.
VGG11
VGG13
VGG16
1.50
loss
loss/bias/aar
bias
1.25
loss/blas/Var
1.00
var
1.00
0.50
0.25
100
100
150
200
epoch
epoch
epoch
ResNet18
ResNet18
ResNet34
1.2
loss/blas/var bab//aaaarrr
1.0
loss/bias/var
1.5
loss/b as/var
2.0
0.4
0.2
50
100
150
200
250
$0
100
150
200
250
50
100
150
200
250
epoch
epoch
epoch
(a) SVHN
(b) CIFAR10
(c) CIFAR100
Figure 13: Test CE loss and the corresponding bias/variance terms. The models were trained with 20% label noise. Adam optimizer with learning rate 0.0001 was used.
16

---

Under review as a conference paper at ICLR 2021
G BIAS AND VARIANCE TERMS W.R.T. DIFFERENT OPTIMIZERS AND LEARNING RATES
VGG11 (fail)
VGG13
VGG16
1.0
loss
0.
loss
loss
loss/bias/va
bias
less/bias/var
bias
bias
0.6
loss/bias/ve
0.8
var
var
var
0.7
0.4
0.6
0.0
0.4
50
100
150
200
250
50
100
150
250
100
150
250
epoch
epoch
epoch
ResNet18
ResNet18
ResNet34
0.5
0.6
0.9
loss/blas/val
blas
loss/bias/var
0.5
blas
blas
0.4
var
var
loss/blas
var
0.3
0.8
0.2
0.2
0.1
50
100
200
250
50
100
200
250
50
100
150
200
250
epoch
epoch
epoch
(a) SVHN
(b) CIFARIO
(c) CIFAR100
Figure 14: The expected test ZO loss and its bias and variance. The models were trained with 20% label noise. Adam optimizer with learning rate 0.001 was used.
VGG11
VGG13
VGG16
0.6
loss
loss
0.9
loss
loss/blas/var
0.5
blas
loss/bias/var
blas
bias
0.4
0.4
loss/blas
0.7
0.3
0.5
02
0.1
50
100
200
250
100
200
250
100
250
epoch
epoch
epoch
ResNet18
ResNet18
ResNet34
0.6
loss
loss
loss
loss/bias/Var
0.30
loss/bias/var
0.5
0.25
var
var
var
0:15
0.3
loss/ol
0.8
0.05
100
epoch
epoch
epoch
(a) SVHN
(b) CIFARIO
(c) CIFAR100
Figure 15: Expected test ZO loss and its bias and variance. The models were trained with 20% label noise. SGD optimizer (momentum 0.9) with learning rate 0.01 was used.
17

---

Under review as a conference paper at ICLR 2021
VGG11
VGG13
VGG16
loss blas
loss
0.9
loss
loss/blas/var
loss/biasNa
0.5
blas
blas
0.4
var
0.7
0.3
0.2
0.5
50
100
150
200
250
50
100
150
200
250
50
100
150
200
250
epoch
epoch
epoch
ResNet18
ResNet18
ResNet34
loss
loss
0.9
loss
loss/blas/var
0.5
blas
loss/bias/va
0.5
blas
loss/bias/Va
0.8
blas
var
0.3-
0.2
02-
50
100
200
250
100
200
250
100
250
epoch
epoch
epoch
(a) SVHN
(b) CIFARIO
(c) CIFARI00
Figure 16: Expected test ZO loss and its bias and variance. The models were trained with 20% label noise. SGD optimizer (momentum 0.9) with learning rate 0.001 used.
H DETAILED INFORMATION OF THE SMALL CNN MODEL
We present the detailed information of the architecture trained with small numbers of training sam- ples. consists of two convolutional layers and two fully-con mally-connected layers, shown in Table 2
Table 2: Architecture of the small CNN model ("BN" is short for Batch Normalization).
Layers
Parameters
BN
Activation
Max pooling
Input
input s3ze=(32, 32)
Conv
filters=(3, 3)x 32;
Y
ReLU
(2. 2)
Conv
filters=(3, x)x64;
ReLU
(2.
Dense
modes=1024
ReLU
Dense
nodes=10
Softmax
18

---

Under review as a conference paper at ICLR 2021
1 OPTIMIZATION VARIANCE AND TEST ACCURACY W.R.T. DIFFERENT
OPTIMIZERS AND LEARNING RATES
V6616
0.30
0.000
0.0025
0.6
09-
3.008
0.9
000
0. 0.0020
ACC, 0%
80
0.-
3.005
0.8
0..00
000
OV,
0000015
0.7
3.204
0.7
-0.004
BCC, 20%
0.00000
0.
0.6
3.202
0.6
0.002
0.0015
50
100
150
250
2.000
50
103
150
200
000
50
100
150
200
0. 0000
epoch
epoch
ResNet18
ResNet18
ResNet34
0.0223
0.0025
0.0025
0.7
0.020
0.0000
0.0020
800
0.8
000515
0.3
0.0015
0.5
0.0015
0.7
0.0300
0.7
0.0010
0.0010
0.6
0.0005
0.6
0.0005
03-
0.0005
5b
100
150
200
0.0000
150
159 epech
200
0 0000
02
50
100
200
0.0000
epoch
epoch
(a) SVHN
(b) CIFARIO
(c) CIFARI00
Figure 17: Test accuracy and optimization variance (OV). The models were trained with Adam optimizer (learning rate 0.001). The number each legend indicates its percentage of label noise.
VGG11
VG616
1.0
0.0030
3.005
0. 0.0030
0.0025
0.004
0.0025
0.031
3..002
3.003
0.3
aCt,
DV. 0%
OV, 20%
00.001
0.0010
0.2
0.,005
0.0005
55
100
150
200
252
0.0000
50
100
150
206
252
000
50
160
150
200
250
0.0000
epoch
epoch
epoch
ResNet18
ResNet18
ResNet34
1.0
3.005
0.005
0.055
0.5
3.004
0.004
0.6
0.004
0.8
3.003
3.003
2.5
0.008
0.7
3.002
0.7
3.002
0.4
0.002
3.201
3.001
0.001
0.000
50
100
150
200
250
50
102
150
200
250
150
150
200
250
epoch
(a) SVHN
(b) CIFARIO
(c) CIFARI00
Figure 18: Test accuracy and optimization variance (OV). The models were trained with SGD op- timizer (learning rate 0.01, momentum 0.9). The number in each legend indicates percentage of label noise.
19

---

Under review as a conference paper at ICLR 2021
VGG11
VGG13
VGG16
0.9
0.000
0.6
30
100
130
200
250
50
100
150
200
250
30
100
150 epoch
200
250
epach
epoch
ResNet18
ResNet18
ResNet34
3.007
0.008
0.08
0.9
3.4
0.004
3:203
0.3
3.002
Margedun Pusrrrrr
50
100
150
200
230
50
100
150
200
250
120
150 epach
200
250
epoch
egoch
(a) SVHN
CIFARIO
(c) CIFAR100
Figure 19: Test accuracy and optimization variance (OV). The models were trained with the SGD optimizer (learning rate 0.001, momentum 0.9). The number in each legend indicates its percentage of label noise.
20


Reviews:
[{"review_id": "yqkWLd9hvM", "reviewer": "AnonReviewer4", "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": "* quality\nThe idea is interesting, but the paper lacks theoretical insights. And it was difficult to find in the paper how OV is related to generalization.\n* clarity\nThe paper needs to make it more clear how OV is related to generalization - is it always monotonically decreasing/increasing?\n* originality\nThe idea seems new, but more theoretical insight is needed.\n* significance\nIf the authors include more theoretical justification, the paper's results would be more significant. The current version is too empirical and not very convincing. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "tDZcuIAe-7Y", "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": "This paper proposes the metric of estimating the variance of gradients during optimization of deep networks and empirically found that this metric correlates with test errors, which may indicate a good point for performing early stopping during training.\n\nMy first thinking is that the metric is indeed interesting and informative if, it could be applied to indicates the generalization on the test set, of course. Then my concern rises from the methodology used in this paper, as using 'a correlation' between optimization variance and generalization error to indicate a 'causal relation' between these two numbers. Granted, it might be difficult to actually prove it. From a big picture, it would still be nice to see a comparison analysis with other simpler metrics, such as the gradient magnitude itself?\n\nThe definition of \"optimization variance\" seems to be weird, as in equation 6, the nominator scales with gradient magnitudes, and the denominator tends to have very smaller changes after some iterations, comparably. So why is this OV so different from the gradient norms as to constitute a novel metric? At least from experiments, the changes in denominator do not matter that much.\n\nThe dataset is kind of simple in the empirical analysis. It would be better if Imagenet size level ones or regression tasks are also performed.\n\nSmall questions:\n\nFigure 3, what is 'different number of training batches'? is that batch size?\n\nFigure 4 shows some strong upheaval in terms of accuracy, is that from a large gradient that somehow explodes during training?\n\nFigure 5 has really unreadable captions and legend notations.", "extra_scores": {}, "extra_text": {}}, {"review_id": "s5d3t9g4Tlo", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper under review studies the epoch wise double descent phenomena empirically. The epoch wise double descent phenomena is the observation that the risk of a large neural network trained with SGD first decreases, then increases, and finally decreases again as a function of the epochs or SGD steps. In addition, it proposes a quantity called ``optimization variance (OV)'', and it demonstrate that OV correlates with the test error. Based on this observation, it proposes to early stop when the OV reaches a minimum.\n\nStrong points are that the paper\ni) is an early work studying epoch-wise double descent, and that \nii) the newly introduced optimization variance is an interesting concept and might very well be useful for finding good early stopping points.\n\nWeak points are that \ni) the findings about epoch-wise double descent are not conclusive, and that \nii) optimization variance is not sufficiently evaluated to judge its usefulness. Both is discussed in more detail in Comments 1-6 below.\n\nBased on comments 1-6 below I think that the paper's conclusions are not yet supported by the papers experiment. I do think that the paper can be developed into a very nice contribution, if more substantive findings about epoch-wise double descent can be obtained, and/or if the value of the newly introduced optimization variance is evaluated more thoroughly (e.g., through simple theory, or through more rigorous experiments). \n\nComments:\n1/ The paper's main finding on epoch-wise double descent is that ``the variance dominates the epoch-wise double descent of the test error'' meaning that it ``is mainly the variance that contributes to epoch-wise double descent''. This statement is overly general, because it is drawn from observations for one particular setup (20\\% label noise, CIFAR10 and SVHN). If the label noise is less, it becomes apparent that both the variance and bias work together (as a sum) to generate a double-descent like curve. Adding curves for other distributions (e.g., less label noise, other datasets) can illustrate that.\n\n2/ The paper's main contribution to the study of epoch-wise double descent is the empirical bias-variance decomposition. However, this approach does not enable to draw conclusions on why double descent occurs, as the paper notes itself ``the reason why the variance begins to diminish at the late phase of training is still unclear''. \n\n3/ The paper finds a strong empirical correlation between the test error and the newly introduced optimization variance (OV) (Fig. 2), and proposes to early stop based on the OV. However, Fig. 2 also shows when this fails: c) ResNet 34 on CIFAR-10 shows that OV is minimal at 250 epochs, while the accuracy is highest after about 15-20 epochs. Of course, such an early stopping rule is allowed to fail sometimes, but the evidence that this is a good early stopping rule is not convincing.\n\n4/ The value of OV would be much more convincing if the paper could provide a theoretical result even for a simple toy case like a linear model.\nIt would also be more convincing if the benefits of OV hold for a broad set of models; the paper points out that it doesn't generalize to a large class of models: ``we need to point out that we did not observe a strong correlation between the OV and the test accuracy when using significantly different architectures''.\n\n5/ The paper omits a recent reference on epoch-wise double descent: https://arxiv.org/abs/2007.10099, which is very related because it explains epoch-wise double descent as overlapping bias variance tradeoffs for a variety of setups, both empirically and practically. \n\n6/ As https://arxiv.org/abs/2007.10099 finds, epoch-wise double descent can bit mitigated, and this can typically improves performance. How does the paper's approach to find the early stopping point work in this setup, where double descent is mitigated?\n\nMinor comments:\n``20\\% labels of the training data were randomly shuffled to strengthen epoch-wise double descent'': This is misleading as it suggested that with less or zero label noise, epoch-wise double descent does occur, but it does not for the models and setup considered in the paper.\n\n-----\nUPDATE: Thanks for the response, I have responded below and kept the score constant.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "cM4mcYex8zs", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "Having a stopping rule without the validation set is intriguing, especially for datasets with a low number of samples. The authors propose a rule that doesn't require the validation dataset, i.e. it is solely based on training data. It introduces the notion of optimization variance which is different from the variance of gradients. \nI give them credit for the idea and also the analytical comparison with the variance of gradients.\n\nOn the one hand, the experiments in Section 3.3 are geared towards showing the role of the validation dataset, but on the other hand they lack rigor. It would be interesting to learn the impact at different levels of the percentage of the samples in validation. I also think the work can be impactful on small datasets. While they experiment with large-scale datasets, experiments with even smaller datasets and different validation set proportions would be of great interest. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZrNtWzS9QEq", "reviewer": "AnonReviewer5", "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:\n\nThe paper studies the trajectory of the test error as a function of training time focusing on Epoch-Wise Double-Descent.  Similar to \"Rethinking Bias-Variance Trade-off for Generalization of Neural Networks\" by Yang et. al., the paper shows that if one decomposes the test error to bias and variance terms, Double Descent occurs as a function of train time as a result of unimodality of the variance term (while the bias term decreases monotonically).  The paper also introduces a quantity they name optimization variance (OV) and that correlates with the test error (while being only a function of the train set) and can be useful for early stopping.\n\n=====================================================\n\nMain Concerns and improvement points:\nRegarding the variance as the main culprit behind Double Descent:\nWhile it is interesting to see that the analysis of Yang et. al. carries over to epoch double descent, by itself, this experiment is not too surprising. Citing the discussion section \"Contradicting to the traditional view that the variance keeps increasing because of overfitting, our experimental results show a more complex behavior: the variance starts high and then decreases\nrapid\". This is exactly the claim made in Yang et. al, for model double descent making the novelty of the empirical result more limited. As the authors mention (and promise to study in the future), understanding why the variance diminished with time after the interpolation threshold is an important question that could substantially strengthen the paper. \n\nRegarding Optimization Variance:\nWhile it is cool that the optimization variance not too hard to compute and correlates well with the test set (for a fixed architecture) I'm not sure what is the fundamental contribution here. Just defining a quantity and showing some properties it has without motivation for why and when should we expect this quantity to arise is not a persuasive result. A couple of specific concerns for me are: \n1) Correlation does not mean much by itself. For example, the train accuracy is very correlated with the test accuracy. There are other empirical quantities that correlate with the test (and provably so at times, see for example https://arxiv.org/pdf/1912.00528.pdf). \n2) Usually, training for long enough is sufficient to have high correlation with the test.  For example in fig 5 we could ask where would lie a model trained for a very long time (say 100 epochs) my bet it would right there on the line of best test error.  \n3) If the argument here is early stopping I can just use the test set.\n4) The quantity does not correlate through different model architectures.\n\nTo alleviate my concerns I would love to see some theoretical justification for *why* is this an important quantity and when does it arise naturally. Alternatively, if we can predict test set across different model architectures, that would give more motivation to as why we might want to look at this quantity more deeply.\n\nTo summarize, the first part of the paper is lacking in novelty and in the second part, the OV is not deeply enough motivated. \nI do believe that the paper is on the right track and with some work should be publishable in a future conference.   \n\nMinor Comments:\nIt might be a personal preference, but I find the notation confusing and in disconnect with the standard notation in the field. For example, using t as labels and y as predictions is highly non-standard and would confuse many readers.  (why not y for label, \\hat y or p for prediction, t for training time?)\n\"The expected loss should be small to ensure good generalization performance\" - this is a very informal sentence that I found confusing rather than helpful.  ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Originality: The paper can be developed into a very nice contribution, if the value of the newly introduced optimization variance is evaluated more thoroughly (e.g., through simple theory, or through more rigorous experiments).

Main pros:
- One of the early works studying epoch-wise double descent
- Optimization variance is an interesting concept and might very well be useful for finding good early stopping points.

Main cons:
- Findings about epoch-wise double descent remain inconclusive
- optimization variance is not sufficiently evaluated to judge its usefulness: theoretical justification for why is this an important quantity and when does it arise naturally is something missing at this point.

Overall: there was a consensus that the paper focuses and provides an interesting story, with new ideas; however, paper's conclusions are not strongly supported by experiments; more experiments are needed to make arguments conclusive. 
Decision: Reject