summaries: 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. 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.  The 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.
abstractText: 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 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 a 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.
references.authors: Madhu S Advani Andrew M Saxe
references.title: High-dimensional dynamics of generalization error in neural networks
references.authors: Zeyuan Allen-Zhu Yuanzhi Li Zhao Song
references.title: A convergence theory for deep learning via overparameterization
references.venue: In Proc. 36th Int’l Conf. on Machine Learning,
references.authors: Devansh Arpit Stanisław Jastrzębski Nicolas Ballas David Krueger Emmanuel Bengio Maxinder S Kanwal Tegan Maharaj Asja Fischer Aaron Courville Yoshua Bengio Simon Lacoste-Julien
references.title: A closer look at memorization in deep networks
references.venue: In Proc. 34th Int’l Conf. on Machine Learning,
references.authors: Peter L Bartlett Philip M Long Gábor Lugosi Alexander Tsigler
references.title: Benign overfitting in linear regression
references.venue: Proceedings of the National Academy of Sciences,
references.authors: Mikhail Belkin Daniel Hsu Siyuan Ma Soumik Mandal
references.title: Reconciling modern machine learning practice and the classical bias-variance trade-off
references.venue: Proceedings of the National Academy of Sciences,
references.authors: Mikhail Belkin Daniel Hsu Ji Xu
references.title: Two models of double descent for weak features
references.venue: CoRR, abs/1903.07571,
references.authors: Stephen Boyd Lieven Vandenberghe
references.title: Convex Optimization
references.authors: Niladri Chatterji Behnam Neyshabur Hanie Sedghi
references.title: The intriguing role of module criticality in the generalization of deep networks
references.venue: In Proc. Int’l Conf. on Learning Representations,
references.authors: Laurent Dinh Razvan Pascanu Samy Bengio Yoshua Bengio
references.title: Sharp minima can generalize for deep nets
references.venue: In Proc. 34th Int’l Conf. on Machine Learning,
references.authors: Pedro Domingos
references.title: A unified bias-variance decomposition for zero-one and squared loss
references.venue: In Proc. of the 17th National Conf. on Artificial Intelligence,
references.authors: Jerome Friedman Trevor Hastie Robert Tibshirani
references.title: The Elements of Statistical Learning, volume 1. Springer series in statistics
references.authors: Mario Geiger Arthur Jacot Stefano Spigler Franck Gabriel Levent Sagun Stéphane d’Ascoli Giulio Biroli Clément Hongler Matthieu Wyart
references.title: Scaling description of generalization with number of parameters in deep learning
references.authors: Stuart Geman Elie Bienenstock René Doursat
references.title: Neural networks and the bias/variance dilemma
references.venue: Neural Computation,
references.authors: Trevor Hastie Andrea Montanari Saharon Rosset Ryan J Tibshirani
references.title: Surprises in highdimensional ridgeless least squares interpolation
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In Proc. IEEE Conf. on Computer Vision and Pattern Recognition,
references.authors: Reinhard Heckel Fatih Furkan Yilmaz
references.title: Early stopping in deep networks: Double descent and how to eliminate it
references.authors: Tom Heskes
references.title: Bias/variance decompositions for likelihood-based estimators
references.venue: Neural Computation,
references.authors: Dimitris Kalimeris Gal Kaplun Preetum Nakkiran Benjamin Edelman Tristan Yang Boaz Barak Haofeng Zhang
references.title: SGD on neural networks learns functions of increasing complexity
references.venue: In Proc. Advances in Neural Information Processing Systems,
references.authors: Nitish Shirish Keskar Dheevatsa Mudigere Jorge Nocedal Mikhail Smelyanskiy Ping Tak Peter Tang
references.title: On large-batch training for deep learning: Generalization gap and sharp minima
references.venue: In Proc. Int’l Conf. on Learning Representations,
references.authors: Diederik P. Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: In Proc. Int’l Conf. on Learning Representations,
references.authors: Ron Kohavi David H Wolpert
references.title: Bias plus variance decomposition for zero-one loss functions
references.venue: In Proc. 13th Int’l Conf. on Machine Learning,
references.authors: Eun Bae Kong Thomas G Dietterich
references.title: Error-correcting output coding corrects bias and variance
references.venue: In Proc. 12th Int’l Conf. on Machine Learning,
references.authors: Alex Krizhevsky
references.title: Learning multiple layers of features from tiny images
references.venue: URL https: //www.cs.toronto.edu/~kriz/learning-features-2009-TR.pdf
references.authors: Alex Krizhevsky Ilya Sutskever Geoffrey E Hinton
references.title: ImageNet classification with deep convolutional neural networks
references.venue: In Proc. Advances in Neural Information Processing Systems,
references.authors: Yann LeCun Léon Bottou Yoshua Bengio Patrick Haffner
references.title: Gradient-based learning applied to document recognition
references.venue: Proceedings of the IEEE,
references.authors: Wesley J Maddox Gregory Benton Andrew Gordon Wilson
references.title: Rethinking parameter counting in deep models: Effective dimensionality revisited
references.authors: Partha P Mitra
references.title: Understanding overfitting peaks in generalization error: Analytical risk curves for l2 and l1 penalized interpolation
references.venue: IEEE Journal on Selected Areas in Information Theory,
references.authors: Preetum Nakkiran Gal Kaplun Yamini Bansal Tristan Yang Boaz Barak Ilya Sutskever
references.title: Deep double descent: Where bigger models and more data hurt
references.venue: In Proc. Int’l Conf. on Learning Representations,
references.authors: Yuval Netzer Tao Wang Adam Coates Alessandro Bissacco Bo Wu Andrew Y. Ng
references.title: Reading digits in natural images with unsupervised feature learning
references.venue: In Proc. NIPS Workshop on Deep Learning and Unsupervised Feature Learning
references.authors: Behnam Neyshabur Ryota Tomioka Nathan Srebro
references.title: Norm-based capacity control in neural networks
references.venue: In Proc. of the 28th Conf. on Learning Theory,
references.authors: Behnam Neyshabur Srinadh Bhojanapalli David McAllester Nati Srebro
references.title: Exploring generalization in deep learning
references.venue: In Proc. Advances in Neural Information Processing Systems,
references.authors: Nasim Rahaman Aristide Baratin Devansh Arpit Felix Draxler Min Lin Fred Hamprecht Yoshua Bengio Aaron Courville
references.title: On the spectral bias of neural networks
references.venue: In Proc. 36th Int’l Conf. on Machine Learning,
references.authors: Shai Shalev-Shwartz Shai Ben-David
references.title: Understanding Machine Learning: From Theory to Algorithms
references.authors: Karen Simonyan Andrew Zisserman
references.title: Very deep convolutional networks for large-scale image recognition
references.venue: In Proc. Int’l Conf. on Learning Representations,
references.authors: Robert Tibshirani
references.title: Bias, variance and prediction error for classification rules
references.venue: Technical report, Department of Preventive Medicine and Biostatistics and Department of Statistics,
references.authors: Vladimir N Vapnik
references.title: An overview of statistical learning theory
references.venue: IEEE Trans. on Neural Networks,
references.authors: Huan Wang Nitish Shirish Keskar Caiming Xiong Richard Socher
references.title: Identifying generalization properties in neural networks
references.authors: Han Xiao Kashif Rasul Roland Vollgraf
references.title: Fashion-MNIST: a novel image dataset for benchmarking machine learning
references.venue: algorithms. CoRR,
references.authors: Zitong Yang Yaodong Yu Chong You Jacob Steinhardt Yi Ma
references.title: Rethinking bias-variance trade-off for generalization of neural networks
references.authors: Chiyuan Zhang Samy Bengio Moritz Hardt Benjamin Recht Oriol Vinyals
references.title: Understanding deep learning requires rethinking generalization
references.venue: In Proc. Int’l Conf. on Learning Representations,
references.authors: Xiao Zhang Dongrui Wu
references.title: Rethink the connections among generalization, memorization and the spectral bias of DNNs
sections.heading: 1 INTRODUCTION
sections.text: 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 (ShalevShwartz & Ben-David, 2014), inspiring new designs of network architectures (Krizhevsky et al., 2012; Simonyan & Zisserman, 2015; He et al., 2016; Zagoruyko & Komodakis, 2016) and reconsideration 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; Allen-Zhu et al., 2019).
  Model-wise double descent, i.e., as a DNN’s model complexity increases, its test error first shows a classical U-shaped curve and then enters a 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 al., 2020). 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 et al. (2018) and Yang et al. (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 is the major cause of modelwise 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 increasing the number of training epochs instead of the model complexity1 (Nakkiran et al., 2020). Compared with model-wise double descent, epoch-wise double descent is relatively less explored. Heckel & Yilmaz (2020) showed that epoch-wise double descent occurs in the situation where different parts of DNNs are learned at different epochs, which can be eliminated by proper scaling of step sizes. Zhang & Wu (2020) discovered that the energy ratio of the high-frequency components of a DNN’s prediction landscape, which can reflect the model capacity, switches from increase to
  1In practice, some label noise is often added to the training set to make the epoch-wise double descent more conspicuous.
  decrease at a certain training epoch, leading to the second descent of the test error. However, this metric fails to provide further information on generalization, such as the early stopping point, or how the size of a DNN influences its performance.
  This paper utilizes bias-variance decomposition of the zero-one (ZO) loss (CE loss is still used in training) to further investigate epoch-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 available2. Inspired by the fact that the source of variance comes from the random-sampled training sets, we propose a 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. 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 in 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 al., 2017) and norm-based measures (Neyshabur et al., 2015). However, their values rely heavily on the model parameters, making comparisons across different models very difficult. Dinh et al. (2017) shows that by re-parameterizing a DNN, one can alter the sharpness of its searched local minima without affecting the function it represents; Neyshabur et al. (2018) shows 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 a 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 al. (2020) proposed a metric called Model Criticality that can explain the superior generalization performance of some architectures over others, yet it is unexplored that whether this metric can be used to indicate generalization in the entire training procedure, especially for some relatively complex generalization behaviors, such as epoch-wise double descent.
  To summarize, our contributions are:
  • We perform bias-variance decomposition on the test error to explore epoch-wise double descent. We show that the variance dominates the variation of the test classification error.
  • We propose a novel metric, OV, which is calculated from the training set only and correlates well with the test classification error.
  • Based on the OV, we propose an 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 introduces the details of tracing bias and variance over training epochs. Section 3 proposes the OV and demonstrates its ability to indicate the test behaviors. Section 4 draws conclusions and points out some future research directions.
sections.heading: 2 BIAS AND VARIANCE IN EPOCH-WISE DOUBLE DESCENT
sections.text: 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.
sections.heading: 2.1 A UNIFIED BIAS-VARIANCE DECOMPOSITION
sections.text: Bias-variance decomposition is widely used to analyze the generalization properties of machine learning algorithms (Geman et al., 1992; Friedman et al., 2001). It was originally proposed for
  2Assume the training set has n samples. We 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 n 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 be different.
  the MSE loss and later extended to other loss functions, e.g., CE and ZO losses (Kong & Dietterich, 1995; Tibshirani, 1996; Kohavi et al., 1996; Heskes, 1998). Our study utilizes a unified bias-variance decomposition that was proposed by Domingos (2000) and applicable to arbitrary loss functions.
  Let (x, t) be a sample drawn from the data distribution D, where x ∈ Rd denotes the ddimensional input, and t ∈ Rc the one-hot encoding of the label in c classes. The training set T = {(xi, ti)}ni=1 ∼ Dn is utilized to train the model f : Rd → Rc. Let y = f(x; T ) ∈ Rc be the probability output of the model f trained on T , and L(t,y) the loss function. The expected loss ET [L(t,y)] should be small to ensure that the model both accurately captures the regularities in its training data, and also generalizes well to unseen data.
  According to Domingos (2000), a unified bias-variance decomposition3 of ET [L(y, t)] is:
  ET [L(t,y)] = L(t, ȳ)︸ ︷︷ ︸ Bias +β ET [L(ȳ,y)]︸ ︷︷ ︸ Variance , (1)
  where β takes different values for different loss functions, and ȳ is the expected output:
  ȳ = arg min y∗∈Rc ∣∣∑c k=1 y ∗ k=1,y ∗ k≥0 ET [L(y∗,y)]. (2)
  ȳ minimizes the variance term in (1), which can be regarded as the “center" or “ensemble" of y w.r.t. different T . Table 1 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 ZO loss is used (see Appendix C). To capture the overall bias and variance, we analyzed Ex,tET [L(t,y)], i.e., the expectation of ET [L(t,y)] over the distribution D.
sections.heading: 2.2 TRACE THE BIAS AND VARIANCE TERMS OVER TRAINING EPOCHS
sections.text: To trace the bias term Ex,t[L(t, ȳ)] and the variance term Ex,tET [L(ȳ,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; Tj , q) the model f trained on Tj ∼ Dn (j = 1, 2, ...,K) for q epochs. Then, the estimated bias and variance terms at the q-th epoch, denoted as B(q) and V (q), respectively, can be written as:
  B(q) = E(x,t)∈T ∗ [ L ( t, f̄(x; q) )] , (3)
  V (q) = E(x,t)∈T ∗  1 K K∑ j=1 L(f̄(x; q), f(x; Tj , q))  , (4) 3In real-world situations, the expected loss consists of three terms: bias, variance, and noise. Similar to
  Yang et al. (2020), we view t as the groundtruth and ignore the noise term.
  where
  f̄(x; q) = H  K∑ j=1 H(f(x; Tj , q))  , (5) is the voting result of {f(x; Tj , q)}Kj=1.
  We should emphasize that, in real-world situations, D cannot be obtained, hence Tj in our experiments was randomly sampled from the training set (we sampled 50% training data for each Tj). As a 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 et al., 2016) and VGG (Simonyan & Zisserman, 2015) models4 trained on SVHN (Netzer et al., 2011), CIFAR10 (Krizhevsky, 2009), and CIFAR100 (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 {Tj}Kj=1 (K = 5) from the training set, 20% labels of the training data were randomly shuffled to introduce epoch-wise double descent.
  Figure 1 shows the expected ZO loss and its bias and variance. The bias descends rapidly at first and then generally converges to a 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 Appendices E and G). All experimental results demonstrated that it is mainly the variance that contributes to epoch-wise double descent.
sections.heading: 2.3 DISCUSSION
sections.text: 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 rapidly, followed by a 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 decomposition for MSE and CE losses in Appendix F). CE and MSE losses, analyzed in the traditional
  4Adapted from https://github.com/kuangliu/pytorch-cifar
  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 a 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.
sections.heading: 3 OPTIMIZATION VARIANCE (OV)
sections.text: This section proposes a 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.
sections.heading: 3.1 NOTATION AND DEFINITION
sections.text: 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 (1), the variance measures the model diversity caused by different training samples drawn from the same distribution, i.e., the outputs of DNN change according to the sampled training set. As the gradients are usually the only information transferred from training sets 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 like to develop a metric to reflect the function robustness of DNNs to sampling noises. If the function captured by a DNN drastically varies w.r.t. different training batches, its generalization error is very likely to be poor due to a large variance introduced by the optimization procedure. A similar metric is the sharpness of local minima proposed by Keskar et 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 in the entire optimization process.
  Mathematically, for a sample (x, t) ∼ D, let f(x;θ) be the logit output of a DNN with parameter θ. Let TB ∼ Dm be a training batch with m samples, g : TB → R|θ| the optimizer outputting the update of θ based on TB . Then, we can get the function distribution Fx(TB) over a training batch TB , i.e., f(x;θ + g(TB)) ∼ Fx(TB). The variance of Fx(TB) reflects the model diversity caused by different training batches. The formal definition of OV is given below. Definition 1 (Optimization Variance (OV)) Given an input x and model parameters θq at the q-th training epoch, the OV on x at the q-th epoch is defined as
  OVq(x) , ETB
  [ ‖f(x;θq + g(TB))− ETBf(x;θq + g(TB))‖ 2 2 ] ETB [ ‖f(x;θq + g(TB))‖22
  ] . (6) Note that OVq(x) measures the relative variance, because the denominator in (6) eliminates the influence of the logit’s norm. In this way, OVq(x) at different training phases can be compared. The motivation here comes from the definition of coefficient of variation5 (CV) in probability theory and statistics, which is also known as the relative standard deviation. CV is 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 ∑ i σ 2 i / ∑ i µ 2 i , where σi and µi 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.
  5https://en.wikipedia.org/wiki/Coefficient_of_variation
  Intuitively, the OV represents the inconsistency of gradients’ influence on the model. If OVq(x) 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 are 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.
sections.heading: 3.2 EXPERIMENTAL RESULTS
sections.text: We calculated the expectation of the OV over x, i.e., Ex[OVq(x)], 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 Ex[OVq(x)] (dashed curves) change with the number of training epochs. Though sometimes the OV may not exhibit clear epoch-wise double descent, e.g., VGG16 in Figure 2(c), the symmetry between the solid and dashed curves generally exist, suggesting that the OV, which is 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).
  Note that epoch-wise double descent is not a 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 epochwise double descent, yet the proposed OV still works pretty well.
  OVq(x) in Figure 2 was estimated on all training batches; however, this may not be necessary: a 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 OVq(x) from different number of training batches. The results in Figure 3 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 et al., 1998) trained on MNIST and FashionMNIST without label noise. Spikes of the OV and the test accuracy happen simultaneously at the same epoch.
  Our experimental results demonstrate that the generalization ability of a DNN can be indicated by the OV during stochastic training, without using a validation set. This phenomenon can be used to determine the early stopping point, and beyond.
sections.heading: 3.3 EARLY STOPPING WITHOUT A VALIDATION SET
sections.text: The common process to train a DNN involves three steps: 1) partition the dataset into a training set and a validation set; 2) use the training set to optimize the DNN parameters, and the validation set to determine when to stop training, i.e., early stopping, and record the early 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 no guarantee that the early stopping point on 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 on the entire dataset, without a validation set?
  The OV can be used for this purpose. For more robust performance, instead of using the OV directly, we may need to smooth it to alleviate random fluctuations.
  As an example, we smoothed the OV by a 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 was also performed directly on the test accuracy to get the groundtruth. However, it should be noted that the latter is unknown in real-world applications. It is provided for verification purpose only.
  We trained different DNN models on several datasets (SVHN: VGG11 and ResNet18; CIFAR10: VGG13 and ResNet18; CIFAR100: VGG16 and ResNet34) 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 on the OV6. The results are shown in 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 5(a). However, the test errors, which are what a model designer really cares about, were always close.
  3.4 SMALL SIZE OF THE TRAINING SET
  For large datasets, a validation set can be easily partitioned from the training set without hurting the generalization performance. Therefore, OV is more useful in the case of small datasets. To this end, we performed experiments with small numbers (2000, 4000, 6000) of the training samples in CIFAR10 to verify the effectiveness of OV in this situation. Considering the limited numbers of training samples, we trained a small Convolution Neural Network (CNN) using Adam optimizer with learning rate 0.0001, whose detailed information can be found in Appendix H.
  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 performance 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.
  6Training VGG11 on SVHN with Adam optimizer and learning rate 0.001 was unstable (see Appendix D), so we did not include its results in Figure 5.
sections.heading: 3.5 NETWORK SIZE
sections.text: In addition to indicating the early stopping point, the OV can also explain some other generalization behaviors, such as the influence of the network size. To verify that, we trained ResNet18 with different network sizes on CIFAR10 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, ..., 8) times the number of filters in the original model. We then examined the OV of ResNet18 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 to calculate the OV, so that the cumulative influence during training can be removed to make the comparison more fair.
  The results are shown in Figure 7. As k increases, the OV gradually decreases, i.e., the diversity of model updates introduced by different training batches decreases when widening ResNet18, suggesting that increasing the network size can improve the model’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). Lastly, we need to point out that we did not observe a 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 a more universal cross-model metric to illustrate the generalization performance.
sections.heading: 4 CONCLUSIONS
sections.text: This paper has shown that the variance dominates the epoch-wise double descent, and highly correlates 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 a dedicated validation set.
  Our future work will: 1) apply the OV to other tasks, such as regression problems, unsupervised learning, and so on; 2) figure out the cause of the second descent of the OV; and, 3) design regularization approaches to penalize the OV for better generalization performance.
sections.heading: A BIAS-VARIANCE DECOMPOSITION FOR DIFFERENT LOSS FUNCTIONS
sections.text: 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 L(t,y) = ‖t−y‖22, and need to calculate ȳ based on (2). We first ignore the constraints and solve the following problem:
  ỹ = arg min y∗
  ET [‖y∗ − y‖22], (7)
  whose solution is ỹ = ET y. It can be easily verified that ỹ satisfies the constraints in (2), and hence ȳ = ỹ = ET y.
  Then, we can decompose the MSE loss as: ET [‖t− y‖22] = ET [‖t− ȳ + ȳ − y‖22]
  = ET [‖t− ȳ‖22 + ‖ȳ − y‖22 + 2(t− ȳ)T (ȳ − y)] = ‖t− ȳ‖22 + ET [‖ȳ − y‖22] + 0, (8)
  where the first term denotes the bias, and the second denotes the variance. We can also get β = 1.
  A.2 CROSS-ENTROPY (CE) LOSS For L(t,y) = ∑c k=1 tk log tk yk
  , ȳ can be obtained by applying the Lagrange multiplier method (Boyd & Vandenberghe, 2004) to (2):
  l(y∗, λ) = ET
  [ c∑
  k=1
  y∗k log y∗k yk
  ] + λ · ( 1−
  c∑ k=1 y∗k
  ) . (9)
  To minimize l(y∗, λ), we need to compute its partial derivatives to y∗ and λ: ∂l
  ∂y∗k = ET
  [ log
  y∗k yk + 1
  ] − λ, k = 1, 2, ..., c
  ∂l ∂λ = 1− c∑ k=1 y∗k.
  By setting these derivatives to 0, we get:
  ȳk = 1
  Z exp{ET [log yk]}, k = 1, 2, ..., c (10) where Z = ∑c k=1 exp{ET [log yk]} is a normalization constant independent of k.
  Because
  ET
  [ c∑
  k=1
  αk log ȳk yk
  ] = − logZ, ∀αk c∑ k=1 αk = 1, (11)
  we have:
  ET
  [ c∑
  k=1
  tk log tk yk
  ] = ET [ c∑
  k=1
  tk
  ( log
  tk ȳk + log ȳk yk
  )]
  = c∑ k=1 tk log tk ȳk + ET
  [ c∑
  k=1
  tk log ȳk yk
  ]
  = c∑ k=1 tk log tk ȳk − logZ
  = c∑ k=1 tk log tk ȳk + ET
  [ c∑
  k=1
  ȳk log ȳk yk
  ] , (12)
  from which we obtain β = 1.
  A.3 THE ZERO-ONE (ZO) LOSS
  For the ZO loss, i.e., L(t,y) = 1con{H(t) 6= H(y)}, ȳ is the voting result, i.e., H(ET [H(y)]), so that the variance can be minimized. However, the value of β depends on the relationship between ȳ and t.
  When ȳ = t, we have:
  ET [1con{H(t) 6= H(y)}] = 0 + ET [1con{H(ȳ) 6= H(y)}] = 1con{H(t) 6= H(ȳ)}+ ET [1con{H(ȳ) 6= H(y)}] , (13)
  clearly, β = 1.
  When ȳ 6= t, we have:
  ET [1con{H(t) 6= H(y)}] = PT (H(y) 6= t) = 1− PT (H(y) = t) = 1con{H(t) 6= H(ȳ)} − PT ( H(y) = t
  ∣∣H(y) = ȳ)PT (H(y) = ȳ) − PT ( H(y) = t
  ∣∣H(y) 6= ȳ)PT (H(y) 6= ȳ) . (14) Since ȳ 6= H(t), it follows that
  PT ( H(y) = t ∣∣H(y) = ȳ) = 0. (15) Then, (14) becomes:
  ET [1con{H(t) 6= H(y)}] = 1con{H(t) 6= H(ȳ)} − PT ( H(y) = t ∣∣H(y) 6= ȳ)PT (H(y) 6= ȳ) = 1con{H(t) 6= H(ȳ)} − PT ( H(y) = t
  ∣∣H(y) 6= ȳ)ET [1con{H(ȳ) 6= H(y)}] , (16) hence, β = −PT ( H(y) = t
  ∣∣H(y) 6= ȳ).
sections.heading: B CONNECTIONS BETWEEN THE OPTIMIZATION VARIANCE AND THE
sections.text: GRADIENT VARIANCE
  This section shows the connection between the gradient variance and the optimization variance in Definition 1.
  For simplicity, we ignore q in OVq(x) and denote g(TB)−ETBg(TB) by g̃(TB). Then, the gradient variance Vg can be written as:
  Vg = ETB [ ‖g(TB)− ETBg(TB)‖ 2 2 ] = ETB [ g̃(TB)T g̃(TB) ] . (17)
  Denote the Jacobian matrix of the logits f(x;θ) w.r.t. θ by Jθ(x), i.e.,
  Jθ(x) = [∇θf1(x;θ),∇θf2(x;θ), ...,∇θfc(x;θ)] , (18)
  where fj(x;θ) is the j-th entry of f(x;θ), and c is the number of classes.
  Using first order approximation, we have:
  f(x;θ + g(TB)) ≈ f(x;θ) + Jθ(x)T g(TB), (19)
  and OV (x) can be written as:
  OV (x) ≈ ETB
  [ g̃(TB)TJθ(x)Jθ(x)T g̃(TB) ] f(x;θ)T f(x;θ) + ETB [O (‖g(TB)‖2)] ≈ ETB [ g̃(TB)TJθ(x)Jθ(x)T g̃(TB) ] f(x;θ)T f(x;θ) . (20)
  The only difference between Ex [OV (x)] and Vg is the middle weight matrix Ex [ Jθ(x)Jθ(x) T
  f(x;θ)T f(x;θ)
  ] .
  This suggests that penalizing the gradient variance can also reduce the optimization variance.
  Figure 8 presents the curves of Vg in the training procedure. It can be observed that Vg also shows some ability to indicate the generalization performance. However, compared with the results in Figure 2, we can see that OV demonstrates a stronger power for indicating the generalization error than Vg . More importantly, Vg loses its comparability when the network size increases, while OV
  can be more reliable to architectural changes with the middle weight matrix Ex [ Jθ(x)Jθ(x) T
  f(x;θ)T f(x;θ)
  ] to
  normalize Vg , which is illustrated in Figure 7.
  We also notice that ‖ETBg(TB)‖ 2 2 is usually far less than ETB ‖g(TB)‖ 2 2, hence Vg and the gradient norm ETB ‖g(TB)‖ 2 2 almost present the same curves in the training procedure.
  VGG11
  VGG13
  VGG16
sections.heading: C BEHAVIORS OF DIFFERENT LOSS FUNCTIONS
sections.text: Many different loss functions can be used to evaluate the test performance of a model. They may have very different behaviors w.r.t. the training epochs. As shown in Figure 9, the epoch-wise double descent can be very conspicuous on 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 1, 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 a 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 VGG11 ON SVHN BY ADAM OPTIMIZER WITH LEARNING RATE 0.001
  Training VGG11 on SVHN by Adam optimizer with learning rate 0.001 is unstable, as shown in Figure 14(a). Figure 10 shows 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.
sections.heading: E LOSS, BIAS AND VARIANCE W.R.T. DIFFERENT LEVELS OF LABEL NOISE
sections.text: Label noise makes epoch-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
  when adding different levels of label noise. Figure 11 shows an example to compare the loss, variance, 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 minimum. This is surprising, because the label noise is considered highly related to the complexity of the dataset. Our future work will explore the role label noise plays in the generalization of DNNs.
  Loss
  Var
  Bias
sections.heading: F BIAS AND VARIANCE TERMS W.R.T. DIFFERENT LOSS FUNCTIONS
sections.heading: G BIAS AND VARIANCE TERMS W.R.T. DIFFERENT OPTIMIZERS AND LEARNING RATES
sections.heading: H DETAILED INFORMATION OF THE SMALL CNN MODEL
sections.text: We present the detailed information of the architecture trained with small numbers of training samples. It consists of two convolutional layers and two fully-connected layers, as shown in Table 2.
sections.heading: I OPTIMIZATION VARIANCE AND TEST ACCURACY W.R.T. DIFFERENT OPTIMIZERS AND LEARNING RATES
title: OPTIMIZATION VARIANCE: EXPLORING GENERAL-