A Modern Take on the Bias-Variance Tradeoff in Neural Networks

The bias-variance tradeoff tells us that as model complexity increases, bias falls and variances increases, leading to a U-shaped test error curve. However, recent empirical results with over-parameterized neural networks are marked by a striking absence of the classic U-shaped test error curve: test error keeps decreasing in wider networks. This suggests that there might not be a bias-variance tradeoff in neural networks with respect to network width, unlike was originally claimed by, e.g., Geman et al. (1992). Motivated by the shaky evidence used to support this claim in neural networks, we measure bias and variance in the modern setting. We find that both bias and variance can decrease as the number of parameters grows. To better understand this, we introduce a new decomposition of the variance to disentangle the effects of optimization and data sampling. We also provide theoretical analysis in a simplified setting that is consistent with our empirical findings.


INTRODUCTION
There is a dominant dogma in machine learning: "The price to pay for achieving low bias is high variance" (Geman et al., 1992).
The quantities of interest here are the bias and variance of a learned model's prediction on a new input, where the randomness comes from the sampling of the training data. This idea that bias decreases while variance increases with model capacity, leading to a U-shaped test error curve is commonly known as the bias-variance tradeoff ( Fig. 1 (left)).
There exist experimental evidence and theory that support the idea of a tradeoff. In their landmark paper, Geman et al. (1992) measure bias and variance in various models. They show convincing experimental evidence for the bias-variance tradeoff in nonparametric methods such as kNN (k-nearest neighbor) and kernel regression. They also show experiments on neural networks and claim that bias decreases and variance increases with network width. Statistical learning theory (Vapnik, 1998) successfully predicts these U-shaped test error curves implied by a tradeoff for a number of classic machine learning models. A key element is identifying a notion of model capacity, understood as the main parameter controlling this tradeoff.
A number of different research directions have spawned in response to these findings. Neyshabur et al. (2015) hypothesize the existence of an implicit regularization mechanism. Some study the role that optimization plays (Soudry et al., 2018;Gunasekar et al., 2018). Others suggest new measures of capacity (Liang et al., 2017;Neyshabur et al., 2019). All approaches focus on test error, rather than studying bias and variance directly (Neyshabur et al., 2019;Geiger et al., 2019;Liang et al., 2017;Belkin et al., 2019a).
Test error analysis does not give a definitive answer on the lack of a bias-variance tradeoff. Consider boosting: it is known that its test error often decreases with arXiv:1810.08591v4 [cs.LG] 18 Dec 2019  (Fortmann-Roe, 2012). We find that both bias and variance decrease when we increase network width on MNIST (right) and other datasets (Section 4). These results seem to contradict the traditional intuition of a strict tradeoff.
the number of rounds (Schapire & Singer, 1999, Figures 8-10). In spite of this monotonicity in test error, Bühlmann & Yu (2003) show that variance grows at an exponentially decaying rate, calling this an "exponential bias-variance tradeoff." To study the bias-variance tradeoff, one has to isolate and measure bias and variance individually. To the best of our knowledge, there has not been published work reporting such measurements on neural networks since Geman et al. (1992).
We go back to basics and study bias and variance. We start by taking a closer look at Geman et al. (1992, Figure 16 and Figure 8 (top))'s experiments with neural networks. We notice that their experiments do not support their claim that "bias falls and variance increases with the number of hidden units." The authors attribute this inconsistency to convergence issues and maintain their claim that the bias-variance tradeoff is universal. Motivated by this inconsistency, we perform a set of bias-variance experiments with modern neural networks.
We measure prediction bias and variance of fully connected neural networks. These measurements allow us to reason directly about whether there exists a tradeoff with respect to network width. We find evidence that both bias and variance can decrease at the same time as network width increases in common classification and regression settings ( Fig. 1 and Section 4).
We observe the qualitative lack of a bias-variance tradeoff in network width with a number of gradientbased optimizers. In order to take a closer look at the roles of optimization and data sampling, we propose a simple decomposition of total prediction variance (Section 3.3). We use the law of total variance to get a term that corresponds to average (over data samplings) vari-ance due to optimization and a term that corresponds to variance due to training set sampling of an ensemble of differently initialized networks. Variance due to optimization is significant in the under-parameterized regime and monotonically decreases with width in the over-parameterized regime. There, total variance is much lower and dominated by variance due to sampling (Fig. 2).
We provide theoretical analysis, consistent with our empirical findings, in simplified analysis settings: i) prediction variance does not grow arbitrarily with number of parameters in fixed-design linear models; ii) variance due to optimization diminishes with number of parameters in neural networks under strong assumptions.
Organization The rest of this paper is organized as follows. We discuss relevant related work in Section 2. Section 3 establishes necessary preliminaries, including our variance decomposition. In Section 4, we empirically study the impact of network width on variance.
In Section 5, we present theoretical analysis in support of our findings. Neyshabur et al. (2015); Neyshabur (2017) point out that because increasing network width does not lead to a U-shaped test error curve, there must be some form of implicit regularization controlling capacity. Our work is consistent with this finding, but by approaching the problem from the bias-variance perspective, we gain additional insights: 1) We specifically address the hypothesis that decreased bias must come at the ex- pense of increased variance (see Geman et al. (1992) and Appendix E) by measuring both quantities. 2) Our more fine-grain approach reveals that variance due to optimization vanishes with width, while variances due to sampling increases and levels off. This insight about variance due to sampling is consistent with existing variance results for boosting (Bühlmann & Yu, 2003). To ensure that we are studying networks of increasing capacity, one of the experimental controls we use throughout the paper is to verify that bias is decreasing.

RELATED WORK
In independent concurrent work, Spigler et al. (2018) is the only one to theoretically analyze variance. Their work differs from ours in that we run experiments with neural networks on complex, real data, while they carry out a theoretical analysis of linear models in a simplified teacher (data generating distribution) setting.

Set-up
We consider the typical supervised learning task of predicting an output y ∈ Y from an input x ∈ X , where the pairs (x, y) are drawn from some unknown joint distribution, D. The learning problem consists of learning a function h S : X → Y from a finite training dataset S of m i.i.d. samples from D. The quality of a predictor h can quantified by the expected error, for some loss function : Y × Y → R.
In this paper, predictors h θ are parameterized by the weights θ ∈ R N of neural networks. We consider the average performance over possible training sets (denoted by the random variable S) of size m. This is the same quantity Geman et al. (1992) consider. While S is the only random quantity studied in the traditional bias-variance decomposition, we also study randomness coming from optimization. We denote the on arXiv five months after our paper appeared on arXiv.
random variable for optimization randomness (e.g. initialization) by O.
Formally, given a fixed training set S and fixed optimization randomness O, the learning algorithm A produces θ = A(S, O). Randomness in optimization translates to randomness in A(S, ·). Given a fixed training set, we encode the randomness due to O in a conditional distribution p(θ|S). Marginalizing over the training set S of size m gives a marginal distribution p(θ) = E S p(θ|S) on the weights learned by A from m samples. In this context, the average performance of the learning algorithm using training sets of size m can be expressed in the following ways:

Bias-variance decomposition
We briefly recall the standard bias-variance decomposition in the case of squared-loss. We work in the context of classification, where each class k ∈ {1 · · · K} is represented by a one-hot vector in R K . The predictor outputs a score or probability vector in R K . In this context, the risk in Eq.
(2) decomposes into three sources of error (Geman et al., 1992): The first term is an intrinsic error term independent of the predictor; the second is a bias term: whereȳ(x) denotes the expectation E[y|x] of y given x. The third term is the expected variance of the output predictions: where the expectation over θ can be done as in Eq.
(2). Interpreting this bias-variance decomposition as a bias-variance tradeoff is quite pervasive (see, e.g., Hastie et al. (2001, Chapter 2.9), Goodfellow et al. (2016, Bishop (2006, Chapter 3.2)). It is generally invoked to emphasize that the model selected should be of the complexity that achieves the optimal balance between bias and variance.
Note that risks computed with classification losses (e.g cross-entropy or 0-1 loss) do not have such a clean bias-variance decomposition (Domingos, 2000;James, 2003). However, it is natural to expect that bias and variance are useful indicators of the performance of models that are not assessed with squared error. In fact, we show the classification risk can be bounded as 4 times the regression risk in Appendix D.4. To empirically examine this connection, in all of our graphs that have "test error" or "training error" on some classification task, we plot the 0-1 classification error (see, e.g., Fig. 3b).

Further decomposing variance into its sources
In the set-up of Section 3.1 the prediction is a random variable that depends on two sources of randomness: the randomly drawn training set, S, and any optimization randomness, O, encoded into the conditional p(·|S). In certain regimes, one gets significantly different predictions when using a different initialization. Similarly, the output of a learned predictor changes when we use a different training set. How do we start disentangling variance caused by sampling from variance caused by optimization? There are few different ways; here we describe one of them.
Our goal is to measure prediction variance due to sampling, while controlling for the effect of optimization randomness.
Definition 1 ((Ensemble) Variance due to sampling). We consider the variance of an ensemble of infinitely many predictors with different optimization randomness (e.g. random initializations): A common practice to estimate variance due to optimization effects is to run multiple seeds on a fixed training set. Definition 2 ((Mean) Variance due to optimization). We consider the average (over training sets) variance over optimization randomness for a fixed training set: The law of total variance naturally decomposes variance into these very terms: We use this decomposition to get a finer understanding of our observations (Fig. 2).

EXPERIMENTS
In this section, we study how variance of fully connected single hidden layer networks varies with width. We provide evidence against Geman et al.  Our main finding is that, for all tasks that we study, bias and variance both decrease as we scale network width. We also provide a meaningful decomposition of prediction variance into a variance due to sampling term and a variance due to optimization term.

Common experimental details
We run experiments on different datasets: MNIST, SVHN, CIFAR10, small MNIST, and a sinusoid regression task. Averages over data samples are performed by taking the training set S and creating 50 bootstrap replicate training sets S by sampling with replacement from S. We train 50 different neural networks for each hidden layer size using these different training sets. Then, we estimate E bias 2 and E variance as in Section 3.2, where the population expectation E x is estimated with an average over the test set. To estimate the two terms from the law of total variance (Equation 4), we use 10 random seeds for the outer expectation and 10 for the inner expectation, resulting in a total of 100 neural networks for each hidden layer size. Furthermore, we compute 99% confidence intervals for our bias and variance estimates using the bootstrap (Efron, 1979).
The networks are initialized using PyTorch's default initialization, which scales the variance of the weight initialization distribution inversely proportional to the width (LeCun et al., 1998;Glorot & Bengio, 2010). The networks are trained using SGD with momentum and generally run for long after 100% training set accuracy is reached (e.g. 500 epochs for full data MNIST and 10000 epochs for small data MNIST). The overall trends we find are robust to how long the networks are trained after the training error converges. The step size hyperparameter is specified in each of the sections, and the momentum hyperparameter is always set to 0.9. To make our study as general as possible, we consider networks without regularization bells and whistles such as weight decay, dropout, or data augmentation, which Zhang et al. (2017) found to not be necessary for good generalization.

Decreasing variance in full data setting
We find a clear decreasing trend in variance with width of the network in the full data MNIST setting ( Fig. 1). We also see the same trend with CIFAR10 (Appendix B.1) and SVHN (Appendix B.2). In these experiments, the same step size is used for all networks for a given dataset (0.1 for MNIST and 0.005 for CI-FAR10 and SVHN). The trend is the same with or without early stopping, so early stopping is not necessary to see decreasing variance, similar to how it was not necessary to see better test set performance with width in Neyshabur et al. (2015). Wider ResNets are known to achieve lower test error (Zagoruyko & Komodakis, 2016); this likely translates to decreasing variance with width in convolutional networks as well. Much of the over-parameterization literature focuses on over-parameterization in width; interestingly, the variance trend is not the same when varying depth (Appendix C).

Testing the limits: decreasing variance in the small data setting
Decreasing the size of the dataset can only increase variance. To study the robustness of the above obser- vation, we decrease the size of the training set to just 100 examples. In this small data setting, somewhat surprisingly, we still see that both bias and variance decrease with width ( Fig. 3a). The test error behaves similarly ( Fig. 3b). Because performance is more sensitive to step size in the small data setting, the step size for each network size is tuned using a validation set (see Appendix B.4 for step sizes). The training for tuning is stopped after 1000 epochs, whereas the training for the final models is stopped after 10000 epochs. Note that because we see decreasing bias with width, effective capacity is, indeed, increasing while variance is decreasing.
One control that motivates the experimental design choice of optimal step size is that it leads to the conventional decreasing bias trend ( Fig. 3a) that indicates increasing effective capacity. In fact, in the corresponding experiment where step size is the same 0.01 for all network sizes, we do not see monotonically decreasing bias (Appendix B.5).
This sensitivity to step size in the small data setting is evidence that we are testing the limits of our hypothesis. By looking at the small data setting, we are able to test our hypothesis when the ratio of size of network to dataset size is quite large, and we still find this decreasing trend in variance (Fig. 3a).
To see how dependent this phenomenon is on SGD, we also run these experiments using batch gradient descent and PyTorch's version of LBFGS. Interestingly, we find a decreasing variance trend with those optimizers as well. These experiments are included in Appendix B.6.

Decoupling variance due to sampling from variance due to optimization
In order to better understand this variance phenomenon in neural networks, we separate the variance due to sampling from the variance due to optimiza-tion, according to the law of total variance (Equation 4). Contrary to what traditional bias-variance tradeoff intuition would suggest, we find variance due to sampling increases slowly and levels off, once sufficiently over-parameterized (Fig. 2). Furthermore, we find that variance due to optimization decreases with width, causing the total variance to decrease with width ( Fig. 2).
A body of recent work has provided evidence that over-parameterization (in width) helps gradient descent optimize to global minima in neural networks (Du et al., 2019;Du & Lee, 2018;Soltanolkotabi et al., 2017;Livni et al., 2014;Zhang et al., 2018). Always reaching a global minimum implies low variance due to optimization on the training set. Our observation of decreasing variance on the test set shows that the over-parameterization (in width) effect on optimization seems to extend to generalization, on the data sets we consider.

Visualization with regression on sinusoid
We trained different width neural networks on a noisy sinusoidal distribution with 80 independent training examples. This sinusoid regression setting also exhibits the familiar bias-variance trends (Fig. 3c) and trends of the two components of the variance and the test error ( Fig. 19 of Appendix B.7).
Because this setting is low-dimensional, we can visualize the learned functions. The classic caricature of high capacity models is that they fit the training data in a very erratic way (example in Fig. 15 of Appendix B.7). We find that wider networks learn sinusoidal functions that are much more similar than the functions learned by their narrower counterparts (Fig. 4). We have analogous plots for all of the other widths and ones that visualize the variance similar to how it is commonly visualized for Gaussian processes in Appendix B.7. THEORETICAL INSIGHTS Our empirical results demonstrate that in the practical setting, variance due to optimization decreases with network width while variance due to sampling increases slowly and levels off once sufficiently overparameterized. In Section 5.1, we discuss the simple case of linear models and point out that non-increasing variance can already be seen in the over-parameterized setting. In Section 5.2 we take inspiration from linear models to provide arguments for the behavior of variance in increasingly wide neural networks, and we discuss the assumptions we make.

Insights from linear models
In this section, we review the classic result that the variance of a linear model grows with the number of parameters (Hastie et al., 2009, Section 7.3) and point out that variance behaves differently in the overparameterized setting.
We consider least-squares linear regression in a standard setting which assumes a noisy linear mapping y = θ T x + between input feature vectors x ∈ R N and real outputs, where denotes the noise random variable with E[ ] = 0 and Var( ) = σ 2 . In this context, the over-parameterized setting is when the dimension N of the input space is larger than the number m of examples.
Let X denote the m × N design matrix whose i th row is the training point x T i , let Y denote the corresponding labels, and let Σ = X T X denote the empirical covariance matrix. We consider the fixed-design setting where X is fixed, so all of the randomness due to data sampling comes solely from . A learns weightsθ from (X, Y ), either by a closed-form solution or by gradient descent, using a standard initialization The predictor makes a prediction on x ∼ D: h(x) =θ T x. Then, the quantity we care about is E x Var(h(x)).

Under-parameterized setting
The case where N ≤ m is standard: if X has maximal rank, Σ is invertible; the solution is independent of the initialization and given byθ = Σ −1 X T Y . All of the variance is a result of randomness in the noise . For a fixed x, This grows with the number of parameters N . For example, taking the expected value over the empirical distribution,p, of the sample, we recover that the variance grows with N : We provide a reproduction of the proofs in Appendix D.1.

Over-parameterized setting
The over-parameterized case where N > m is more interesting: even if X has maximal rank, Σ is not invertible. This leads to a subspace of solutions, but gradient descent yields a unique solution from updates that belong to the span of the training points x i (row space of X) (LeCun et al., 1991), which is of dimension r = rank(X) = rank(Σ). Correspondingly, no learning occurs in the null space of X, which is of dimension N − r. Therefore, gradient descent yields the solution that is closest to initialization: where P ⊥ projects onto the null space of X and + denotes the Moore-Penrose inverse.
The variance has two contributions: one due to initialization and one due to sampling (here, the noise ), as in Eq. (4). These are made explicit in Proposition 1.
Proposition 1 (Variance in over-parameterized linear models). Consider the over-parameterized setting where N > m. For a fixed x, the variance decomposition of Eq. (4) yields This does not grow with the number of parameters N . In fact, because Σ −1 is replaced with Σ + , the variance scales as the dimension of the data (i.e the rank of X), as opposed to the number of parameters. For example, taking the expected value over the empirical distribution,p, of the sample, we obtain where r = rank(X). We provide the proofs for overparameterized linear models in Appendix D.2.

A more general result
We will illustrate our arguments in the following simplified setting, where M, M ⊥ , and d(N ) are the more general analogs of rowspace(X), nullspace(X), and r (respectively): Setting. Let N be the dimension of the parameter space. The prediction for a fixed example x, given by a trained network parameterized by θ depends on: (i) a subspace of the parameter space, M ∈ R N with relatively small dimension, d(N ), which depends only on the learning task.
(ii) parameter components corresponding to directions orthogonal to M. The orthogonal M ⊥ of M has dimension, N − d(N ), and is essentially irrelevant to the learning task.
We can write the parameter vector as a sum of these two components θ = θ M + θ M ⊥ . We will further make the following assumptions.
Assumption 1 The optimization of the loss function is invariant with respect to θ M⊥ .
Assumption 2 Regardless of initialization, the optimization method consistently yields a solution with the same θ M component (i.e. the same vector when projected onto M).

Variance due to initialization
Given the above assumptions, the following result shows that the variance from initialization 3 vanishes as we increase N . The full proof, which builds on concentration results for Gaussians (based on Levy's lemma (Ledoux, 2001)), is given in Appendix D.3.
Theorem 1 (Decay of variance due to initialization).
Consider the setting of Section 5.2 Let θ denote the parameters at the end of the learning process. Then, for a fixed data set and parameters initialized as θ 0 ∼ N (0, 1 N I), the variance of the prediction satisfies the inequality, where L is the Lipschitz constant of the prediction with respect to θ, and for some universal constant C > O.
This result guarantees that the variance decreases to zero as N increases, provided the Lipschitz constant L grows more slowly than the square root of dimension,

Variance due to sampling
Under the above assumptions, the parameters at the end of learning take the form θ = θ * M + θ 0M ⊥ . For Discussion on assumptions We made strong assumptions, but there is some support for them in the literature. The existence of a subspace M ⊥ in which no learning occurs was also conjectured by Advani & Saxe (2017) and shown to hold in linear neural networks under a simplifying assumption that decouples the dynamics of the weights in different layers. Li et al. (2018) empirically showed the existence of a critical number d(N ) = d of relevant parameters for a given learning task, independent of the size of the model. Sagun et al. (2017) showed that the spectrum of the Hessian for over-parameterized networks splits into (i) a bulk centered near zero and (ii) a small number of large eigenvalues; and Gur-Ari et al. (2018) recently gave evidence that the small subspace spanned by the Hessian's top eigenvectors is preserved over long periods of training. These results suggest that learning occurs mainly in a small number of directions.

CONCLUSION AND FUTURE WORK
We provide evidence against Geman et al. (1992)'s claim that "the price to pay for achieving low bias is high variance," finding that both bias and variance decrease with network width. Geman et al. (1992)'s claim is found throughout machine learning and is meant to generally apply to all of machine learning (Appendix E), and it is correct in many cases (e.g. kNN, kernel regression, splines). Is this lack of a tradeoff specific to neural networks or is it present in other models as well such as decision trees?
We propose a new decomposition of the variance, finding variance due to sampling (analog of regular variance in simple settings) does not appear to be dependent on width, once sufficiently over-parameterized, and that variance due to optimization decreases with width. By taking inspiration from linear models, we perform a theoretical analysis of the variance that is consistent with our empirical observations.
We view future work that uses the bias-variance lens as promising. For example, a probabilistic notion of effective capacity of a model is natural when studying generalization through this lens (Appendix A). We did not study how bias and variance change over the course of training; that would make an interesting direction for future work. We also see further theoretical treatment of variance as a fruitful direction for better understanding complexity and generalization abilities of neural networks.
where S is a training set drawn from D m , h(A, S) is a random variable drawn from the distribution over learned functions induced by D and the randomness in A; p is the corresponding density. Thinking about a model'shypothesis class can lead to drastically different intuitions for the complexity of a model and its variance (Fig. 5). This is at the core of the intuition for why the traditional view of bias-variance as a tradeoff does not hold in all cases.

Bias and Variance
Bias Variance (a) Variance decreases with width, even in the small data setting (SGD). This figure is in the main paper, but we include it here to compare with the corresponding step sizes used. Note that the U curve shown in Fig. 12 when we do not tune the step size is explained by the fact that the constant step chosen is a "good" step size for some networks and "bad" for others. Results from Keskar et al.  2017) show that a step size that corresponds well to the noise structure in SGD is important for achieving good test set accuracy. Because our networks are different sizes, their stochastic optimization process will have a different landscape and noise structure. By tuning the step size, we are making the experimental design choice to keep optimality of step size constant across networks, rather than keeping step size constant across networks. To us, choosing this control makes much more sense than choosing to control for step size. Note that Park et al. (2019) show that, as long as the network size is not too big, controlling for "optimality of step size" and "keeping step size constant" with increasing network width actually correspond to the same thing, as long as the networks are not too big, which fits well with the fact that we used the same step size across network widths for almost all of our experiments.
B.6 Other optimizers for width experiment on small data MNIST

Average Error
Test Error Train Error Figure 13: Variance decreases with width in the small data setting, even when using batch gradient descent.  Figure 15: Caricature examples of high variance learners on sinusoid task. Below, we find that this does not happen with increasingly wide neural networks ( Fig. 17 and Fig. 18).   Average Test Loss Test Loss Figure 19: We observe the same trends of decomposed variance (left) and test error (right) in the sinusoid regression setting.  Figure 20: We can see that, when using dynamical isometry, bias decreases with depth and variance slowly increases with depth (left). This increase in variance is so small that it only translates to a an increase in test error of about 0.1% for depth 25 to depth 200 (right).

C.2 Discussion on need for careful experimental design
Depth is an important component of deep learning. We study its effect on bias and variance by fixing width and varying depth. However, there are pathological problems associated with training very deep networks such as vanishing/exploding gradient (Hochreiter, 1991;Bengio et al., 1994;Glorot & Bengio, 2010), signal not being able to propagate through the network (Schoenholz et al., 2017), and gradients resembling white noise (Balduzzi et al., 2017). He et al. (2016) pointed out that very deep networks experience high test set error and argued it was due to high training set loss. However, while skip connections (He et al., 2016), better initialization (Glorot & Bengio, 2010), and batch normalization (Ioffe & Szegedy, 2015) have largely served to facilitate low training loss in very deep networks, the problem of high test set error still remains.
The current best practices for achieving low test error in very deep networks arose out of trying to solve the above problems in training. An initial step was to ensure the mean squared singular value of the input-output Jacobian, at initialization, is close to 1 (Glorot & Bengio, 2010). More recently, there has been work on a stronger condition known as dynamical isometry, where all singular values remain close to 1 (Saxe et al., 2014;Pennington et al., 2017). Pennington et al. (2017) also empirically found that dynamical isometry helped achieve low test set error. Furthermore, Xiao et al. (2018, Figure 1) found evidence that test set performance did not degrade with depth when they lifted dynamical isometry to CNNs. This why we settled on dynamical isometry as the best known practice to control for as many confounding factors as possible.
We first ran experiments with vanilla full connected networks (Fig. 21). These have clear training issues where networks of depth more than 20 take very long to train to the target training loss of 5e-5. The bias curve is not even monotonically decreasing. Clearly, there are important confounding factors not controlled for in this simple setting. Still, note that variance increases roughly linearly with depth.
We then study fully connected networks with skip connections between every 2 layers (Fig. 22). While this allows us to train deeper networks than without skip connections, many of the same issues persist (e.g. bias still not monotonically decreasing). The bias, variance, and test error curves are all checkmark-shaped.  Figure 22: While the addition of skip connections (between every other layer) might push the bottom of the U curve in test error out to 10 skip connections (21 layers), which is further than where the bottom was observed without skip connections (3 layers), test error still degrades noticeably in greater depths. Additionally, bias still does not even monotonically decrease with depth. While skip connections appear to have helped control for the factors we want to control, they were not completely satisfying. All networks have training error 0 and are trained to the same training loss of 5e-5.

C.5 Dynamical isometry depth experiments
The figures in this section are included in the main paper, but they are included here for comparison to the above and for completeness. Proof. For a fixed x, we have h(x) = x Tθ . Takingθ = Σ −1 X T Y to be the gradient descent solution, and using Y = Xθ + , we obtain: x T θ, and the variance is, Taking the expected value over the empirical distribution,p, of the sample, we find an explicit increasing dependence on N : Proof. By the law of total variance, Here have h(x) = x Tθ , whereθ the gradient descent solutionθ = P ⊥ (θ 0 ) + Σ + X T Y , and θ 0 ∼ N (0, 1 N I). Then, Since E θ0 (h(x)) = x T Σ + X T Y , the calculation of Var (E θ0 )h(x)) is similar as in D.1, where Σ −1 is replaced by Taking the expected value over the empirical distribution,p, of the sample, we find an explicit dependence on r = rank(X), not N : where I + r denotes the diagonal matrix with 1 for the first r diagonal elements and 0 for the remaining N − r elements.

D.3 Proof of Theorem 1
First we state some known concentration results (Ledoux, 2001) that we will use in the proof. Lemma 1 (Levy). Let h : S n R → R be a function on the n-dimensional Euclidean sphere of radius R, with Lipschitz constant L; and θ ∈ S n R chosen uniformly at random for the normalized measure. Then for some universal constant C > 0.
Uniform measures on high dimensional spheres approximate Gaussian distributions (Ledoux, 2001). Using this, Levy's lemma yields an analogous concentration inequality for functions of Gaussian variables: Lemma 2 (Gaussian concentration). Let h : R n → R be a function on the Euclidean space R n , with Lipschitz constant L; and θ ∼ N (0, σI n ) sampled from an isotropic n-dimensional Gaussian. Then: for some universal constant C > 0.
Note that in the Gaussian case, the bound is dimension free.
In turn, concentration inequalities give variance bounds for functions of random variables. Corollary 1. Let h be a function satisfying the conditions of Theorem 2, and . Then Var(h) = Var(g) and Now swapping expectation and integral (by Fubini theorem), and by using the identity E1 |g|>t = P(|g| > t), we obtain We are now ready to prove Theorem 1. We first recall our assumptions: Assumption 1. The optimization of the loss function is invariant with respect to θ M⊥ .
Assumption 2. Along M, optimization yields solutions independently of the initialization θ 0 .
We add the following assumptions.
Assumption 3. The prediction h θ (x) is L-Lipschitz with respect to θ M⊥ .
Assumption 4. The network parameters are initialized as We first prove that the Gaussian concentration theorem translates into concentration of predictions in the setting of Section 5.2.1.
Theorem 2 (Concentration of predictions). Consider the setting of Section 5.2 and Assumptions 1 and 4. Let θ denote the parameters at the end of the learning process. Then, for a fixed data set, S we get concentration of the prediction, under initialization randomness, for some universal constant C > 0.
Proof. In our setting, the parameters at the end of learning can be expressed as where θ * M is independent of the initialization θ 0 . To simplify notation, we will assume that, at least locally around θ * M , M is spanned by the first d(N ) standard basis vectors, and M ⊥ by the remaining N − d(N ). This will allow us, from now on, to use the same variable names for θ M and θ M ⊥ to denote their lower-dimensional representations of dimension d(N ) and N − d(N ) respectively. More generally, we can assume that there is a mapping from θ M and θ M ⊥ to those lower-dimensional representations.
From Assumptions 1 and 4 we get Let g(θ M ⊥ ) h θ * M +θ M ⊥ (x). By Assumption 3, g(·) is L-Lipschitz. Then, by the Gaussian concentration theorem we get, The result of Theorem 1 immediately follows from Theorem 2 and Corollary 1, with σ 2 = 1/N : Provided the Lipschitz constant L of the prediction grows more slowly than the square of dimension, L = o( √ N ), we conclude that the variance vanishes to zero as N grows.

D.4 Bound on classification error in terms of regression error
In this section we give a bound on classification risk R classif in terms of the regression risk R reg .
Notation. Our classifier defines a map h : X → R k , which outputs probability vectors h(x) ∈ R k , with k y=1 h(x) y = 1. The classification loss is defined by where I(a) = 1 if predicate a is true and 0 otherwise. Given trained predictors h S indexed by training dataset S, the classification and regression risks are given by, where Y denotes the one-hot vector representation of the class y.
Proposition 2. The classification risk is bounded by four times the regression risk, R classif ≤ 4R reg .
Proof. First note that, if h(x) ∈ R k is a probability vector, then h(x) y < max y h(x) y =⇒ h(x) y < 1 2 By taking the expectation over x, y, we obtain the inequality L(h) ≤ L(h) where We then have, Appendix E Common intuitions from impactful works E.1 Quotes from influential papers "Neural Networks and the Bias/Variance Dilemma" from (Geman et al., 1992): "How big a network should we employ? A small network, with say one hidden unit, is likely to be biased, since the repertoire of available functions spanned by f (x; w) over allowable weights will in this case be quite limited. If the true regression is poorly approximated within this class, there will necessarily be a substantial bias. On the other hand, if we overparameterize, via a large number of hidden units and associated weights, then the bias will be reduced (indeed, with enough weights and hidden units, the network will interpolate the data), but there is then the danger of a significant variance contribution to the mean-squared error. (This may actually be mitigated by incomplete convergence of the minimization algorithm, as we shall see in Section 3.5.5.)" "An Overview of Statistical Learning Theory" from (Vapnik, 1999): "To avoid over fitting (to get a small confidence interval) one has to construct networks with small VC-dimension." "Stability and Generalization" from Bousquet & Elisseeff (2002): "It has long been known that when trying to estimate an unknown function from data, one needs to find a tradeoff between bias and variance. Indeed, on one hand, it is natural to use the largest model in order to be able to approximate any function, while on the other hand, if the model is too large, then the estimation of the best function in the model will be harder given a restricted amount of data." Footnote: "We deliberately do not provide a precise definition of bias and variance and resort to common intuition about these notions." "Understanding the Bias-Variance Tradeoff" from Fortmann-Roe (2012): "At its root, dealing with bias and variance is really about dealing with over-and under-fitting. Bias is reduced and variance is increased in relation to model complexity. As more and more parameters are added to a model, the complexity of the model rises and variance becomes our primary concern while bias steadily falls. For example, as more polynomial terms are added to a linear regression, the greater the resulting model's complexity will be." Here are two excerpts: • "As a general rule, as we use more flexible methods, the variance will increase and the bias will decrease. The relative rate of change of these two quantities determines whether the test MSE increases or decreases. As we increase the flexibility of a class of methods, the bias tends to initially decrease faster than the variance increases. Consequently, the expected test MSE declines. However, at some point increasing flexibility has little impact on the bias but starts to significantly increase the variance. When this happens the test MSE increases" (James et al., 2014, Chapter 2.2.2).
• "Our goal is to minimize the expected loss, which we have decomposed into the sum of a (squared) bias, a variance, and a constant noise term. As we shall see, there is a trade-off between bias and variance, with very flexible models having low bias and high variance, and relatively rigid models having high bias and low variance" (Bishop, 2006, Chapter 3.2).
• "As the model complexity of our procedure is increased, the variance tends to increase and the squared bias tends to decrease" (Hastie et al., 2001, Chapters 2.9).