Rethinking Bias-Variance Trade-off for Generalization of Neural Networks

Introduction

Bias-variance trade-off is a fundamental principle for understanding the generalization of predictive learning models (Hastie et al., 2001). The bias is an error term that stems from a mismatch between the model class and the underlying data distribution, and is typically monotonically non-increasing as a function of the complexity of the model. The variance measures sensitivity to fluctuations in the training set and is often attributed to a large number of model parameters. Classical wisdom predicts that model variance increases and bias decreases monotonically with model complexity (Geman et al., 1992). Under this perspective, we should seek a model that has neither too little nor too much capacity and achieves the best trade-off between bias and variance.

In contrast, modern practice for neural networks repeatedly demonstrates the benefit of increasing the number of neurons (Krizhevsky et al., 2012; Simonyan & Zisserman, 2015; Zhang et al., 2017), even up to the point of saturating available memory. The inconsistency between classical theory and modern practices suggests that some arguments in the classical theory can not be applied to modern neural networks.

Geman et al. (1992) first studied the bias and variance of the neural networks and give experimental evidence that the variance is indeed increasing as the width of the neural network increases. Since Geman et al. (1992), Neal et al. (2019) first experimentally measured the variance of modern neural network architectures and shown that the variance can actually be decreasing as the width increases to a highly overparameterized regime. Recently, Belkin et al. (2019a, 2018, b) directly studied the risk of modern machine learning models and proposed a double descent risk curve, which has also been analytically characterized for certain regression and classification models (Mei & Montanari, 2019; Hastie et al., 2019; Spigler et al., 2019; Deng et al., 2019; Advani & Saxe, 2017; Bartlett et al., 2020; Chatterji & Long, 2020). However, there exists two mysteries around the double descent risk curve. First, the double descent phenomenon can not be robustly observed (Nakkiran et al., 2019; Ba et al., 2020). In particular, to observe it in modern neural network architectures, we sometimes have to artificially inject label noise (Nakkiran et al., 2019). Second, there lacks an explanation for why the double descent risk curve should occur. In this work, we offer an simple explanation for these two mysteries by proposing an unexpected unimodal variance curve.

Specifically, we measure the bias and variance of modern deep neural networks trained on commonly used computer vision datasets. Our main finding is that while the bias is monotonically decreasing with network width as in the classical theory, the variance curve is unimodal or bell-shaped: it first increases and then decreases (see Figure 2). Therefore, the unimodal variance is consistent with the finding of Neal et al. (2019), who observed that the variance eventually decreases in the overparameterized regime. In particular, the unimodal variance curve can also be observed in Neal et al. (2019, Figure 1, 2, 3). However, Neal et al. (2019) did not point out the characteristic shape of the variance or connect it to double descent. More importantly, we demonstrate that the unimodal variance phenomenon can be robustly observed for varying network architecture and dataset. Moreover, by using a generalized bias-variance decomposition for Bregman divergences (Pfau, 2013), we verify that it occurs for both squared loss and cross-entropy loss.

This unimodal variance phenomenon initially appears to contradict recent theoretical work suggesting that both bias and variance are non-monotonic and exhibit a peak in some regimes (Mei & Montanari, 2019; Hastie et al., 2019) . The difference is that this previous work considered the fixed-design bias and variance, while we measure the random-design bias and variance (we describe the differences in detail in §2.1). Prior to our work, Nakkiran (2019) also considered the variance of linear regression in the random-design setting, and Rosset & Tibshirani (2017) discussed additional ways to decompose risk into the bias and the variance term.

A key finding of our work is that the complex behavior of the risk curve arises due to the simple but non-classical variance unimodality phenomenon. Indeed, since the expected risk (test loss) is the sum of bias and variance, monotonic bias and unimodal variance can lead to three characteristic behaviors, illustrated in Figure 1, depending on the relative size of the bias and variance. If the bias completely dominates, we obtain monotonically decreasing risk curve (see Figure 1(a)). Meanwhile, if the variance dominates, we obtain a bell-shaped risk curve that first increases then decreases (see Figure 1(c)). The most complex behavior is if bias and variance dominate in different regimes, leading to the double-descent risk curve in Figure 1(b). All three behaviors are well-aligned with the empirical observation in deep learning that larger models typically perform better. The most common behavior in our experiments is the first case (monotonically decreasing risk curve) as bias is typically larger than variance. We can observe the double-descent risk curve when label noise is added to the training set (see §3.3), and can observe the unimodal risk curve when we use the generalized bias-variance decomposition for cross-entropy loss (see §3.2).

The investigations described above characterize bias and variance as a function of network width, but we can explore the dependence on other quantities as well, such as model depth (§4.2). Indeed, we find that deeper models tend to have lower bias but higher variance. Since bias is larger at current model sizes, this confirms the prevailing wisdom that we should generally use deeper models when possible. On the other hand, it suggests that this process may have a limit—eventually very deep models may have low bias but high variance such that increasing the depth further harms performance.

We also investigate the commonly observed drop in accuracy for models evaluated on out-of-distribution data, and attribute it primarily to increased bias. Combined with the previous observation, this suggests that increasing model depth may help combat the drop in out-of-distribution accuracy, which is supported by experimental findings in Hendrycks & Dietterich (2019).

Theoretical Analysis of A Two-Layer Neural Network.

Finally, we conduct a theoretical study of a two-layer linear network with a random Gaussian first layer. While this model is much simpler than those used in practice, we nevertheless observe the same characteristic behaviors for the bias and variance. In particular, by working in the asymptotic setting where the input data dimension, amount of training data, and network width go to infinity with fixed ratios, we show that the bias is monotonically decreasing while the variance curve is unimodal. Our analysis also characterizes the location of the variance peak as the point where the number of hidden neurons is approximately half of the dimension of the input data.

Preliminaries

In §2.2, we present our estimator for bias and variance in equation (1) and (2).

Fixed Design.

In fixed-design setting, the covariates $\{\boldsymbol{x}_{i}\}_{i=1}^{n}$ are held be fixed, and the only randomness in the training set $\mathcal{T}$ comes from $\boldsymbol{y}_{i}\sim P(\boldsymbol{Y}\mid\boldsymbol{X}=\boldsymbol{x}_{i})$. As presented in Mei & Montanari (2019); Hastie et al. (2019); Ba et al. (2020), a more natural way to present the fixed-design assumption is to hold $\{\boldsymbol{x}_{i}\}_{i=1}^{n}$ to be fixed and let $\boldsymbol{y}_{i}=f_{0}(\boldsymbol{x})+\boldsymbol{\epsilon}_{i}$ for $i=1,\dots,n$, where $f_{0}(\boldsymbol{x})$ is a ground-truth function and $\boldsymbol{\epsilon}_{i}$ are random noises. Under this assumption, the randomness in $\mathcal{T}$ all comes from the random noise $\boldsymbol{\epsilon}_{i}$. To make this clear, we write $\mathcal{T}$ as $\mathcal{T}_{\boldsymbol{\epsilon}_{i}}$. Then, we obtain the fixed-design bias-variance decomposition

2 Estimating Bias and Variance

To estimate bias and variance in equation (1) and (2), we introduce an unbiased estimator for variance, and obtain bias by subtracting the variance from the risk. Let $\mathcal{T}=\mathcal{T}_{1}\cup\cdots\cup\mathcal{T}_{N}$ be a random disjoint split of training samples. In our experiment, we mainly take $N=2$ (for CIFAR10 each $\mathcal{T}_{i}$ has 25k samples). To estimate the variance, we use the unbiased estimator

where var depends on the test point $\boldsymbol{x}$ and on the random training set $\mathcal{T}$. While var is unbiased, its variance can be reduced by using multiple random splits to obtain estimators $\widehat{\textsf{var}}_{1},\dots,\widehat{\textsf{var}}_{k}$ and taking their average. This reduces the variance of the variance estimator since:

where the $\{\widehat{\textsf{var}}_{i}\}_{i=1}^{k}$ are identically distributed but not independent, and we used the Cauchy-Schwarz inequality.

Cross-Entropy Loss (CE).

where $\pi[l]$ is the $l$-th element of $\pi$, and $\bar{\pi}$ is the average of log-probability after normalization, i.e.,

This decomposition is a special case of the general decomposition for Bregman divergence discussed in Pfau (2013).

We apply Algorithm 1 to estimate the generalized variance in (3). Here we could not obtain an unbiased estimator, but the estimate is better if we take more random splits (larger $k$). In practice, we choose $k$ to be large enough so that the estimated variance stabilizes when we further increase $k$ (see §3.4). Similar to the case of squared loss, we estimate the bias by subtracting the variance from the risk.

Measuring Bias and Variance for Neural Networks

In this section, we study the bias and variance (equations (1) and (2)) of deep neural networks. While the bias is monotonically decreasing as folk wisdom would predict, the variance is unimodal (first increases to a peak and then decreases). We conduct extensive experiments to verify that this phenomenon appears robustly across architectures, datasets, optimizer, and loss function. Our code can be found at https://github.com/yaodongyu/Rethink-BiasVariance-Tradeoff.

We first describe our mainline experimental setup. In the next subsection, we vary each design choice to check robustness of the phenomenon. More extensive experimental results are given in the appendix.

For the mainline experiment, we trained a ResNet34 (He et al., 2016) on the CIFAR10 dataset (Krizhevsky et al., 2009). We trained using stochastic gradient descent (SGD) with momentum $0.9$. The initial learning rate is 0.1. We applied stage-wise training (decay learning rate by a factor of 10 every 200 epochs), and used weight decay $5\times 10^{-4}$. To change the model complexity of the neural network, we scale the number of filters (i.e., width) of the convolutional layers. More specifically, with $\text{width}=w$, the number of filters are $[w,2w,4w,8w]$. We vary $w$ from 2 to 64 (the width $w$ of a regular ResNet34 designed for CIFAR10 in He et al. (2016) is 16).

In Figure 2, we can see that the variance as a function of the width is unimodal and the bias is monotonically decreasing. Since the scale of the variance is small relative to the bias, the overall behavior of the risk is monotonically decreasing.

2 Varying Architectures, Loss Functions, Datasets

Architectures. We observe the same monotonically descreasing bias and unimodal variance phenomenon for ResNext29 (Xie et al., 2017). To scale the “width” of the ResNext29, we first set the number of channels to 1 and increase the cardinality, defined in (Xie et al., 2017), from 2 to 4, and then fix the cardinality at 4 and increase channel size from 1 to 32. Results are shown in Figure 3(a), where the width on the $x$-axis is defined as the cardinality times the filter size.

Loss Function. In addition to the bias-variance decomposition for MSE loss, we also considered a similar decomposition for cross-entropy loss as described in §2.2. We train with cross-entropy loss and use $n=10,000$ training samples (5 splits), repeating $N=4$ times with independent random splits. As shown in Figure 3(b), the behavior of the generalized bias and variance for cross entropy is consistent with our earlier observations: the bias is monotonically decreasing and the variance is unimodal. The risk first increases and then decreases, corresponding to the unimodal risk pattern in Figure 1(c).

Datasets. In addition to CIFAR10, we study bias and variance on MNIST (LeCun, 1998) and Fashion-MNIST (Xiao et al., 2017). For these two datasets, we use a fully connected neural network with one hidden layer with ReLU activation function. The “width” of the network is the number of hidden nodes. We use 10,000 training samples ($N=5$). As seen in Figure 3(c) and 10 (in Appendix B), for both MNIST and Fashion-MNIST, the variance is again unimodal and the bias is monotonically decreasing.

In addition to the above experiments, we also conduct experiments on the CIFAR100 dataset, the VGG network architecture (Simonyan & Zisserman, 2015), various training sample sizes, and different weight decay regularization and present the results in Appendix B. We observe the same monotonically descreasing bias and unimodal variance phenomenon in all of these experiments.

3 Connection to Double-Descent Risk

When the relative scale of bias and variance changes, the risk displays one of the three patterns, monotonically decreasing, double descent, and unimodal, as presented in Figure 1(a), 1(b) and 1(c). In particular, the recent stream of observations on double descent risk (Belkin et al., 2019a) can be explained by unimodal variance and monotonically decreasing bias. In our experiments, including the experiments in previous sections, we typically observe monotonically decreasing risk; but with more label noise, the variance will increase and we observe the double descent risk curve.

Similar to the setup in Nakkiran (2019), for each split, we sample training data from the whole training dataset, and replace the label of each training example with a uniform random class with independent probability $p$. Label noise increases the variance of the model and hence leads to double-descent risk as seen in Figure 4. If the variance is small, the risk does not have the double-descent shape because the variance peak is not large enough to overwhelm the bias, as observed in Figures 2, 3(a), 3(c) and 10.

4 Discussion of Possible Sources of Error

In this section, we briefly describe the possible sources of error in our estimator defined in §2.2.

Mean Squared Error. As argued in §2.2, the variance estimator is unbiased. To understand the variance of the estimator, we first split the data into two parts. For each part, we compute the bias and variance for varying network width by using our estimator. Averaging across different model width, the relative difference between the two parts is 0.6% for bias and 3% for variance, so our results for MSE are minimally sensitive to finite-sample effects. The complete experiments can be found in the appendix (see Figure 17).

Cross Entropy Loss. For cross entropy loss, we are currently unable to obtain an unbiased estimator. We can assess the quality of our estimator using the following scheme. We partition the dataset into five parts $\mathcal{T}_{1},\dots,\mathcal{T}_{5}$, i.e., set $N=5$ in Algorithm 1. Then, we sequentially plot the estimate of bias and variance using $k=1,2,3,4$ as described in Algorithm 1. We observe that using larger $k$ gives better estimates. In Figure 18 of Appendix B.9, we observe that as $k$ increases, the bias curve systematically decreases and the variance curve increases. Therefore our estimator over-estimates the bias and under-estimates the variance, but the overall behaviors of the curves remain consistent.

What Affects the Bias and Variance?

In this section, through the Bias-Variance decomposition analyzed in §3, we investigate the role of depth for neural networks and the robustness of neural networks on out-of-distribution examples.

For many real-world computer vision applications, inputs can be corrupted by random noise, blur, weather, etc. These common occurring corruptions are shown to significantly decrease model performance (Azulay & Weiss, 2019; Hendrycks & Dietterich, 2019). To better understand the “generalization gap” between in-distribution test examples and out-of-distribution test examples, we empirically evaluate the bias and variance on the CIFAR10-C dataset developed by Hendrycks & Dietterich (2019), which is a common corruption benchmark and includes 15 types of corruption.

By applying the models trained in the mainline experiment, we are able to evaluate the bias and variance on CIFAR10-C test dataset according to the definitions in (1) and (2). As we can see from Figure 5(a), both the bias and variance increase relative to the original CIFAR10 test set. Consistent with the phenomenon observed in the mainline experiment, the bias dominates the overall risk. The results indicate that the “generalization gap” mainly comes from increased bias, with relatively less contribution from variance as well.

2 Effect of Model Depth on Bias and Variance

In addition to the ResNet34 considered in the mainline experiment, we also evaluate the bias and variance for ResNet18 and ResNet50. Same as the mainline experiment setup, we estimate the bias and variance for ResNet using 25,000 training samples ($N=2$) and three independent random splits ($k=3$). The standard building block of ResNet50 architecture in He et al. (2016) is bottleneck block, which is different from the basic block used in ResNet18 and ResNet34. To ensure that depth is the only changing variable across three architectures, we apply the basic block for ResNet50. Same training epochs and learning rate decays are applied to three models.

From Figure 5(b) and 5(c), we observe that the bias decreases as the depth increases, while the variance increases as the depth increases. For each model, the bias is monotonically decreasing and the variance is unimodal. The differences in variance are small (around 0.01) compared with the changes in bias. Overall, the risk typically decreases as the depth increases. Our experimental results suggest that the improved generalization for deeper models, with the same network architecture, are mainly attributed to lower bias.

For completeness, we also include the bias and variance versus depth when basic blocks in ResNet are replaced by bottleneck blocks (see Figure 20 in the appendix). We observe similar qualitative trend of bias and variance.

Note that at high width, the bias of ResNet50 is slightly higher than the bias of ResNet18 and ResNet34. We attribute this inconsistency to difficulties when training ResNet50 without bottleneck blocks at high width. Lastly, we also include the bias and variance versus depth for out-of-distribution test samples, in which case we also observed decreased bias and increased variance as depth increases, as shown in Figure 19 of Appendix B.10.

Theoretical Insights from a Two-layer Linear Model

While the preceding experiments show that the bias and variance robustly exhibit monotonic-unimodal behavior in the random-design setting, existing theoretical analyses hold instead for the fixed-design setting, where the behavior of the bias and variance are more complex, with both the bias and variance exhibiting a peak and the risk exhibiting double descent pattern (Mei & Montanari (2019, Figure 6)). In general, while the risk should be the same (in expectation) for the random and fixed design setting, the fixed-design setting has lower bias and higher variance.

Motivated by the more natural behavior in the random-design setting, we work to extend the existing fixed-design theory to the random-design case. Our starting point is Mei & Montanari (2019), who consider two-layer non-linear networks with random hidden layer weights. However, the randomness in the design complicates the analysis, so we make two points of departure to help simplify: first, we consider two-layer linear rather than non-linear networks, and second, we consider a different scaling limit ($n/d\to\infty$ rather than $n/d$ going to some constant). In this setting, we rigorously show that the variance is indeed unimodal and the bias is monotonically decreasing (Figure 6). Our precise assumptions are given below.

2 Bias-Variance Analysis

We may now calculate the bias and variance of the model described above via the following formulations:

where $f_{0}(\boldsymbol{x})$ and $f_{\lambda}(\boldsymbol{x};\mathcal{T},\boldsymbol{W})$ are defined in (4) and (6), respectively. Note that the bias and variance are functions of the model parameter $\boldsymbol{\theta}$. To simplify the analysis, we introduce a prior $\boldsymbol{\theta}\sim\mathcal{N}(0,\boldsymbol{I}_{d})$ and calculate the expected bias and expected variance as

The precise formulas for the expected bias and the expected variance are parametrized by the dimension of the input feature $d$, the number of training points $n$, the number of hidden units $p$ and also $\lambda$.

Previous literatures (Mei & Montanari, 2019) suggests that both the risk and the variance achieves a peak at the interpolation threshold ($n=p$). In the regime when $n$ is very large, the risk no longer exhibits a peak, but the unimodal pattern of variance still holds. In the rest of the section, we consider the regime where the $n$ is large (monotonically decreasing risk), and derive the precise expression for the bias and variance of the model. From our expression, we obtain the location where the variance achieves the peak. For this purpose, we consider the following asymptotic regime of $n,p$ and $d$:

Let $\{(d,n(d),p(d))\}_{d=1}^{\infty}$ be a given sequence of triples. We assume that there exists a $\gamma>0$ such that

For simplicity, we will write $n:=n(d)$ and $p:=p(d)$.

With the assumption above, we have the expression of the expected bias, variance and risk as a function of $\gamma$ and $\lambda$.

Given $\{(d,n(d),p(d))\}_{d=1}^{\infty}$ that satisfies Assumption 1, let $\lambda=\frac{n}{d}\lambda_{0}$ for some fixed $\lambda_{0}>0$. The asymptotic expression of expected bias and variance are given by

The risk can be obtained through $\textbf{Bias}_{\lambda}^{2}+\textbf{Variance}_{\lambda}$. The expression in Theorem 1 is plotted as the red curves in Figure 6. In addition to the case when $n/d\rightarrow\infty$, we also plot the shape of bias, variance and risk when $n/d\rightarrow\{0.15,0.25,0.35,\dots,1.00,1.50\}$. We find that the risk of the model grows from unimodal to monotonically decreasing as the number of samples increased (see Figure 6(a)). Moreover, the bias of the model is monotonically decreasing (see Figure 6(b)) and the variance is unimodal (see Figure 6(c)).

The derivative of the limiting expected Bias in (9) can be calculated as

When $\lambda_{0}\geq 0$, the expression in (10) is strictly non-positive, therefore the limiting expected bias is monotonically non-increasing as a function of $\gamma$, as classical theories predicts.

To gain further insight into the above formulas, we also consider the case when the ridge regularization amount $\lambda_{0}$ is small. In particular, we consider the first order effect of $\lambda_{0}$ on the bias and variance term, and compute the value of $\gamma$ where the variance attains the peak.

Under the assumptions of Theorem 1, the first order effect of $\lambda_{0}$ on variance is given by

Moreover, up to first order, the peak in the variance is

Theorem 2 suggests that when $\lambda_{0}$ is sufficiently small, the variance of the model is maximized when $p=d/2$, and the effect of $\lambda_{0}$ is to shift the peak slightly to $d/2-\lambda_{0}d$.

From a technical perspective, to compute the variance in the random-design setting, we need to compute the element-wise expectation of certain random matrix. For this purpose, we apply the combinatorics of counting non-cross partitions to characterize the asymptotic expectation of products of Wishart matrices.

Conclusion and Discussion

In this paper we re-examine the classical theory of bias and variance trade-off as the width of a neural network increases. Through extensive experimentation, our main finding is that, while the bias is monotonically decreasing as classical theory would predict, the variance is unimodal. This combination leads to three typical risk curve patterns, all observed in practice. Theoretical analysis of a two-layer linear network corroborates these experimental observations.

The seemingly varied and baffling behaviors of modern neural networks are thus in fact consistent, and explainable through classical bias-variance analysis. The main unexplained mystery is the unimodality of the variance. We conjecture that as the model complexity approaches and then goes beyond the data dimension, it is regularization in model estimation (the ridge penalty in our theoretical example) that helps bring down the variance. Under this account, the decrease in variance for large dimension comes from better conditioning of the empirical covariance, making it better-aligned with the regularizer.

In the future, it would be interesting to see if phenomena characterized by the simple two-layer model can be rigorously generalized to deeper networks with nonlinear activation, probably revealing other interplays between model complexity and regularization (explicit or implicit). Such a study could also help explain another phenomenon we (and others) have observed: bias decreases with more layers as variance increases. We believe that the (classic) bias-variance analysis remains a powerful and insightful framework for understanding the behaviors of deep networks; properly used, it can guide practitioners to design more generalizable and robust networks in the future.

Acknowledgements. We would like to thank Emmanuel Candés for first bringing the double-descent phenomenon to our attention, Song Mei for helpful discussion regarding random v.s. fixed design regression, and Nikhil Srivastava for pointing out to relevant references in random matrix theory. We would also like to thank Preetum Nakkiran, Mihaela Curmei, and Chloe Hsu for valuable feedback during preparation of this manuscript. The authors acknowledge support from Tsinghua-Berkeley Shenzhen Institute Research Fund and BAIR.

References

Appendix A Summary of Experiments

We summarize the experiments in Table 1, each row corresponds to one experiment, some include several independent splits, in this paper. Every experiment is related to one or multiple figures, which is specified in the last column “Figure”.

Appendix B Additional Experiments

In this section, we provide additional experimental results, some of them are metioned in §3 and §4.

Network Architecture: The implementation of the deep neural networks used in this work is mainly adapted from https://github.com/kuangliu/pytorch-cifar.

Training Details: For CIFAR10 dataset and CIFAR100 dataset, when training sample size is 25,000, we use 500 epochs for training and decay by a factor of 10 the learning rate every 200 epoch. When training sample size is 10,000/5,000, we use 1000 epochs for training and decay by a factor of 10 the learning rate every 400 epoch. For MNIST dataset and FMNIST dataset, we use 200 epochs for training and decay by a factor of 10 the learning rate every 100 epoch. For all the experiments in this paper, we sampled data without replacement to train the models as described in §2.2.

We provide additional results on ResNext29 presented in §3.2. The results are shown in Figure 7. We also study the behavior of risk, bias, and variance of VGG network (Simonyan & Zisserman, 2015) on CIFAR10 dataset. Here we use VGG11 and the number of filters are $[k,2k,4k,4k,8k,8k,8k,8k]$, where $k$ is the width in Figure 8. The number of training samples of each split is 10,000. We use the same optimization setup as the mainline experiment (ResNet34 in Figure2).

B.2 Loss

We provide additional results on cross-entropy loss presented in §3.2, the results are shown in Figure 9.

B.3 Dataset

We provide the results on Fashion-MNIST dataset in Figure 10, which is mentioned in §3.2. We study the behavior of risk, bias, and variance of ResNet34 on CIFAR100 dataset. Because the number of class is large, we use cross-entropy during training, and apply the classical Bias-Vairance decomposition for MSE in (1) and (2) to estimate the risk, bias, and variance. As shown in Figure 11, we observe the bell-shaped variance curve and the monotonically decreasing bias curve on CIFAR100 dataset.

B.4 Training Size

Appart from the 2 splits case in Figure 2, we also consider 5 splits (10,000 training samples) and 20 splits case (2,500 training samples). We present the 5 splits case (10,000 training samples) in Figure 12, which corresponds to the label 0$\%$ case in Figure 4. We present the 20 splits (2,500 training samples) in Figure 13. With less number of training samples, both the bias and the variance will increase.

B.5 Weight Decay

We study another different weight decay parameter, (wd=1e-4) for ResNet34 on CIFAR10 dataset (10,000 training samples). The risk, bias, variance, and train/test error curves are shown in Figure 14. Compared with Figure 12, we observe that larger weight decay can decrease the variance.

B.6 Label Noise

We provide the risk curve for ResNet34 under different label noise percentage as described in §3.3, and the results are shown in Figure 15.

B.7 0-1 Loss Bias-Variance Decomposition

We evaluated the bias and variance for 0-1 loss (defined in Dietterich & Kong (1995)) on the CIFAR10 dataset with 10,000 training samples using ResNet34. The results are shown in Figure 16. We can consistently observe that the bias is monotonically decreasing and the variance is unimodal.

B.8 Sources of Error for Mean Squared Error (MSE)

As argued in §2.2 the estimator for variance is unbiased estimator. To understand the variance of the estimator, we first split the data into two parts, $A$ and $B$. For each part, we take multiple random splits ($k$) and estimate the variance by taking the average of those estimators, and vary the number of random splits $k$. The results are shown in Figure 17. We can see that the variation between to parts of data is small. Quantitatively, veraging across different model width, the relative difference between two parts of data is 0.65% for bias and 3.15% for variance.

B.9 Sources of Error for Cross Entropy Loss (CE)

For cross entropy loss, we are currently unable to obtain an unbiased estimator. We can access the quality of our estimator using the following scheme. We partition the dataset into five parts $\mathcal{T}_{1},\dots,\mathcal{T}_{5}$, i.e., set $N=5$ in Algorithm 1. Then, we sequentially plot the estimate of bias and variance using $k=1,2,3,4$ as described in Algorithm 1. Using larger $k$ gives better estimate. As shown in Figure 18, when $k$ is small, our estimator over-estimate the bias and under-estimate the variance, but the overall behavior of the curves are consistent.

B.10 Effect of Depth on Bias and Variance for Out-Of-Distribution Data

We study the role of depth on out-of-distribution test data. In Figure 19, we observe that increasing the depth can decrease the bias and increase the variance. Also, deeper ResNet can generalize better on CIFAR10-C dataset as shown in Figure 19.

B.11 Effect of Depth on ResNet using Bottleneck Blocks

In order to study the role of depth for ResNet on bias and variance, we apply basic residual block for ResNet50. To better investigate the depth of ResNet, we use Bottleneck block for ResNet26, ResNet38, and ResNet50. More specifically, the number of 3-layer bottleneck blocks for ResNet26, ResNet38, and ResNet50 are $$,$$, and $$. As shown in Figure 20, we observe that deeper ResNet with Bottleneck blocks has lower bias and higher variance.

B.12 Effect of Depth on VGG

We study the role of depth for VGG network on bias and variance. As shown in Figure 21, we observe that deeper VGG has lower bias and higher variance.

B.13 Additional Synthetic Experiment

In Figure 22, we plot the result of performing regression on synthetic data using a two-layer linear fully connected linear network with varying width. The data are generated as $y={\boldsymbol{\beta}}^{\top}{\boldsymbol{\boldsymbol{x}}}$, $\boldsymbol{x}\sim\mathcal{N}(0,{\boldsymbol{I}}_{d}/d)$, where $\|\boldsymbol{\beta}\|_{2}=1$ is randomly generated and fixed weight vector. The first layer of the network is drawn from i.i.d. zero-mean Gaussian distribution with variance $1/\sqrt{d}$, and the second layer is trained using gradient descent with weight decay $0.1$. The horizontal axis is the number of parameters of the hidden layer normalized by the dimension of the data (i.e., $p/d$). The dots indicate actual experimental results, while the lines indicate theoretically predicted results. We can observe that they align well and the peak occurs at the predicted value.

Appendix C Proof of Theorems in §5

Throughout this section, we use $\|\cdot\|$ and $\|\cdot\|_{2}$ to denote the Frobenius norm and spectral norm of a matrix, respectively. Recall that for any given $\boldsymbol{\theta}$, the training set $\mathcal{T}=(\boldsymbol{X},\boldsymbol{y})$ satisfies the relation $\boldsymbol{y}=\boldsymbol{X}^{\top}\boldsymbol{\theta}$. By plugging this relation into (6), we get

To avoid cluttered notations, we omit the dependency of $\boldsymbol{M}$ on $\lambda,\mathcal{T}$ and $\boldsymbol{W}$.

By using (11), the expected bias and expected variance in (7) and (8) can be written as functions on the statistics of $\boldsymbol{M}$. This is stated in the following proposition. To proceed, we introduce the change of variable

in order to be consistent with conventions in random matrix theory.

The expected bias and expected variance are given by

where $\boldsymbol{M}$ is defined in (12).

By plugging (11) into (7), and using the prior that $\boldsymbol{x}\sim\mathcal{N}(0,\boldsymbol{I}_{d}/d)$ and $\boldsymbol{\theta}\sim\mathcal{N}(0,\boldsymbol{I}_{d})$, we get

Similarly, by plugging (11) into (8) we get

First, we show that in the asymptotic setting defined in Assumption 1, the expected Bias and expected Variance can be calculated as functions on the statistics of the following matrix:

In the following, we omit the dependency of $\boldsymbol{\widetilde{M}}$ on $\lambda_{0}$ and $\boldsymbol{W}$.

Under Assumption 1 with $\lambda-\frac{n}{d}\lambda_{0}$, we have

It suffices to show that $\|\boldsymbol{M}-\boldsymbol{\widetilde{M}}\|_{2}=0$ almost surely. From (12) and (13), we have

where $\boldsymbol{\Delta}:=(d/n)\boldsymbol{X}\boldsymbol{X}^{\top}-\boldsymbol{I}$ and $\boldsymbol{\Omega}:=(\boldsymbol{W}\boldsymbol{W}^{\top}+\lambda_{0}\boldsymbol{I}+\boldsymbol{W}\boldsymbol{\Delta}\boldsymbol{W}^{\top})^{-1}-(\boldsymbol{W}\boldsymbol{W}^{\top}+\lambda_{0}\boldsymbol{I})^{-1}.$

By using triangle inequality and the sub-multiplicative property of spectral norm, we have

Furthermore, by a classical result on the perturbation of matrix inverse (see e.g., Ghaoui (2002, equation $(1.1)$)), we have

It remains to show that $\|\boldsymbol{\Delta}\|_{2}=0$ and that $\|\boldsymbol{W}\|_{2}$, $\|(\boldsymbol{W}\boldsymbol{W}^{\top}+\lambda_{0}\boldsymbol{I})^{-1}\|_{2}^{2}$, and $\|\boldsymbol{\widetilde{M}}\|_{2}$ are bounded from above almost surely. By Wainwright (2019, Example 6.2), $\forall\delta>0$ and $n>d$,

By letting $\delta=\sqrt{d/n}$ and taking the asymptotic limit as in Assumption 1, we have

From Geman (1980), the largest eigenvalue of $\boldsymbol{W}\boldsymbol{W}^{\top}$ is almost surely $(1+\sqrt{\eta})^{2}<\infty$. Therefore, we have

We therefore conclude that $\|\boldsymbol{M}-\boldsymbol{\widetilde{M}}\|_{2}=0$ almost surely, as desired. ∎

Given the expression for Bias and Variance in Proposition 1, under the asymptotic assumptions from Assumption 1,

Recall that $\boldsymbol{\widetilde{M}}=\boldsymbol{W}^{\top}(\boldsymbol{W}\boldsymbol{W}^{\top}+\lambda_{0}\boldsymbol{I})^{-1}\boldsymbol{W}$, by Sherman-Morrision,

Let $\boldsymbol{A}=(d/p)\boldsymbol{W}^{\top}\boldsymbol{W}$, and $\mu_{\boldsymbol{A}}$ be the spectral measure of $\boldsymbol{A}$. Then

According to Marchenko-Pastur Law (Bai & Silverstein, 2010), in the limit when $d\rightarrow\infty$ when $\eta\leq 1$,

where $\eta_{+}=(1+\sqrt{\eta})^{2}$, and $\eta_{-}=(1-\sqrt{\eta})^{2}$. For convenience, define

Given the expression for Bias in Proposition 1, under the asymptotic assumptions in Assumption 1, the Bias for the model is given by

Recall that $\boldsymbol{\widetilde{M}}=\boldsymbol{I}-(\boldsymbol{I}+\lambda_{0}^{-1}\boldsymbol{W}^{\top}\boldsymbol{W})^{-1}$. Thus

where $\eta={d}/{p},\boldsymbol{A}=(d/p)\boldsymbol{W}^{\top}\boldsymbol{W}$. According to Corollary 3.3 in Bishop et al. (2018) (recall we are considering the asymptotic regime of $d,p\rightarrow\infty$),

Observe that the double sum in the previous equation is just the generating series for the Narayana number,

Finally, the statement of Theorem 1 follows directly from the above propositions.