Title: A MODERN TAKE ON THE BIAS-VARIANCE TRADEOFF IN NEURAL NETWORKS

Abstract: We revisit the bias-variance tradeoff for neural networks in light of modern empirical findings. The traditional bias-variance tradeoff in machine learning suggests that as model complexity grows, variance increases. Classical bounds in statistical learning theory point to the number of parameters in a model as a measure of model complexity, which means the tradeoff would indicate that variance increases with the size of neural networks. However, we empirically find that variance due to training set sampling is roughly constant (with both width and depth) in practice. Variance caused by the non-convexity of the loss landscape is different. We find that it decreases with width and increases with depth, in our setting. We provide theoretical analysis, in a simplified setting inspired by linear models, that is consistent with our empirical findings for width. We view bias-variance as a useful lens to study generalization through and encourage further theoretical explanation from this perspective.

1. INTRODUCTION:

The traditional view in machine learning is that increasingly complex models achieve lower bias at the expense of higher variance. This balance between underfitting (high bias) and overfitting (high variance) is commonly known as the bias-variance tradeoff (Figure 1 ). In their landmark work that initially highlighted this bias-variance dilemma in machine learning, Geman et al. (1992) suggest that larger neural networks suffer from higher variance. Because bias and variance contribute to test set performance (through the bias-variance decomposition), this provided strong intuition for how we think about generalization capabilities of large models. Learning theory supports this intuition, as most classical and current bounds on generalization error grow with the size of the networks (Brutzkus et al., 2018) .

However, there is a growing amount of evidence of larger networks generalizing better than their smaller counterparts in practice (Neyshabur et al., 2014; Novak et al., 2018; Zhang et al., 2017; Canziani et al., 2016) . This apparent mismatch between theory and practice is due to the use of worst-case analysis that depends only on the model class, completely agnostic to data distribution and without taking optimization into account. 1 A modern empirical study of bias-variance can take all of this information into account.

We revisit the bias-variance tradeoff in the modern setting, focusing on how variance changes with increasing size of neural networks that are trained with optimizers whose step sizes are tuned with a validation set. In contrast to the traditional view of the bias-variance tradeoff (Geman et al., 1992) , we find evidence that the overall variance decreases with network width (Figure 1 ). This can be seen as the "bias-variance analog" of the described recent evidence of larger networks generalizing better. More in line with the tradeoff, we find that variance grows slowly with depth, using current best practices.

To better understand these coarse trends, we develop a new, more fine-grain way to study variance. We separate variance due to initialization (caused by non-convexity of the optimization landscape) from variance due to sampling of the training set. Surprisingly, we find that variance due to training set sampling is roughly constant with both width and depth (Figure 2 ). Variance due to initialization ). We find that variance decreases along with bias when increasing network width (right). These results seem to contradict the traditional intuition. decreases with width and increases with depth, in our setting (Figure 2 ). To support our empirical findings, we provide a simple theoretical analysis of these sources of variance by taking inspiration from over-parameterized linear models. We see further theoretical treatment of variance as a fruitful direction for better understanding complexity and generalization abilities of neural networks.

MAIN CONTRIBUTIONS:

1. We revisit the bias-variance analysis in the modern setting for neural networks and point out that it is not necessarily a tradeoff as overall variance decreases with width (similar to bias), yielding better generalization.

2. We perform a more fine-grain study of variance in neural networks by decomposing it into variance due to initialization and variance due to sampling. Variance due to sampling is roughly constant with both width and depth. Variance due to initialization decreases with width, while it increases with depth, in the settings we consider.

3. In a simplified setting, inspired by linear models, we provide theoretical analysis in support of our empirical findings for network width.

The rest of this paper is organized as follows. Section 2 establishes necessary preliminaries. In Section 3 and Section 4, we study the impact of network width and network depth (respectively) on variance. In Section 5, we present our simple theoretical variance analysis.

2. PRELIMINARIES:



2.1. 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 inferring 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,

EQUATION

for some loss function : Y × Y → R.

In this paper, predictors h θ are parametrized by the weights θ ∈ R N of deep neural networks. We consider a frequentist risk analysis of the learning algorithm, that is, 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 focused on in traditional bias-variance decomposition, we also focus on randomness coming from optimization. We denote the random variable for optimization randomness (e.g. initialization) by I.2 

Formally, given a fixed training set S and fixed optimization randomness I, the learning algorithm A produces θ = A(S, I). Randomness in initialization translates to randomness in A(S, •) because of non-convexity of the loss surface. Given a fixed training set, we encode the randomness due to I 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 frequentist risk for the learning algorithm using training sets of size m becomes:

EQUATION

2.2. BIAS-VARIANCE DECOMPOSITION:

We briefly recall the standard bias-variance decomposition of the frequentist risk in the case of squared-losses. 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 Eqn. 2 decomposes into three sources of error (Geman et al., 1992) :

R m = E noise + E bias + E variance (3)

The first term is an intrinsic error term independent of the predictor; the second is a bias term

EQUATION

where ȳ(x) denotes the expectation E[y|x] of y given x. The third term is the expected variance of the output predictions:

E variance = E x Var(h θ (x)), Var(h θ (x)) = E θ (h θ (x) -E θ [h θ (x)] 2

where the expectation over θ can be done as in Eqn. 2. Finally, in the set-up of Section 2.1, the sources of variance are the choice of training set S and the choice of initialization I (encoded into the conditional p(•|S)). By the law of total variance, we then have the further decomposition:

EQUATION

We call the first term variance due to initialization and the second term variance due to sampling throughout the paper. 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 the models. In fact, the classification risk can be bounded as 4 times the regression risk (Appendix D.2). 

3. VARIANCE AND WIDTH:

In this section, we study how variance of single hidden layer networks varies with width, like a modern analog of Geman et al. (1992) . We study fully connected single hidden layer networks up to the largest size that fits in memory, in order to search for an eventual increase in variance. To make our study as general as possible, we consider networks without any 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. As is commonly done in practice, these networks are trained with optimizers (e.g. SGD) whose step sizes are tuned using a validation set.3 

3.1. COMMON EXPERIMENTAL DETAILS:

Experiments are run on different datasets: full MNIST, small MNIST, and a sinusoid regression task. Averages over data samples are performed by taking the training set S and creating 50 bootstrap (Efron, 1979) 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 and E variance as in Section 2.2, where the population expectation E x is estimated with an average over the test set inputs. 4 To estimate the two terms from the law of total variance (Equation 5), we use 10 random seeds for the outer expectation and 10 for the inner expectation, resulting in a total of 100 seeds. Furthermore, we compute 99% confidence intervals for our bias and variance estimates using the bootstrap (Efron, 1979) .

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 step size hyperparameter is fixed to 0.1 for the full data experiment and is chosen via a validation set for the small data experiment. The momentum hyperparameter is always set to 0.9.

3.2. DECREASING VARIANCE IN FULL DATA SETTING:

We find a clear decreasing trend in variance with width of the network in the full data setting (Figure 1 ). 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. (2014) .

3.3. 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 observation, we decrease the size of the training set to just 100 examples. In this small data setting, somewhat surprisingly, we still observe the same trend of decreasing variance with width (Figure 3a ). The test error behaves similarly (Figure 3b ). The step size is tuned using a validation set (Appendix B.1). The training for tuning is stopped after 1000 epochs, whereas the training for the final models is stopped after 10000 epochs. The corresponding experiment where step size is the same 0.01 for all network sizes is in Appendix B.2. With the same step size for all networks, we do not see decreasing variance. Note that we are not claiming that variance decreases with width regardless of step size. Rather, we are claiming variance decreases with width when the step size is tuned using a validation set, as is done in practice. By tuning the step size, we are making the experimental design choice of keeping optimality of step size constant across networks (more discussion on this in Appendix B.2).

This sensitivity to step size in the small data setting is evidence that we are testing the limits of our hypothesis. A larger amount of data makes the networks more robust to the choice of step size (Figure 1 ). However, it is likely the case that if we were able to compute with much larger networks, we would eventually observe increasing variance in the full data setting as well. 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 (Figure 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.3. This means that this decreasing variance phenomenon is not explained by the concept that "SGD implicitly regularizes."

3.4. DECOUPLING VARIANCE DUE TO SAMPLING FROM VARIANCE DUE TO INITIALIZATION:

In order to better understand this variance phenomenon in neural networks, we separate the variance due to sampling from the variance due to initialization, according to the law of total variance (Equation 5). Contrary to what traditional bias-variance tradeoff intuition would suggest, we find variance due to sampling is roughly independent of width (Figure 2 ). Furthermore, we find that variance due to initialization decreases with width, causing the joint variance to decrease with width (Figure 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 and Lee, 2018; Soltanolkotabi et al., 2017; Livni et al., 2014; Zhang et al., 2018) . Always reaching a global minimum implies low variance due to initialization 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.

3.5. 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 (Figure 3c ) and trends of the two components of the variance (Figure 5c ).

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 Figure 11 of Appendix B.4). We find that wider networks learn sinusoidal functions that are much more similar than the functions learned by their narrower counterparts (Figure 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.4. 

4. VARIANCE AND DEPTH:

In this section, we study the effect of depth on bias and variance by fixing width and varying depth. Historically, there have been pathological problems that cause deeper networks to experience higher test error than their shallower counterparts (Glorot and Bengio, 2010; He et al., 2016; Balduzzi et al., 2017) . This indicates that there are some important confounding factors to control for when varying depth. The best control that we found is to use an initialization that achieves dynamical isometry, the condition that all of the singular values of the input-output Jacobian are 1 at initialization (Saxe et al., 2014; Pennington et al., 2017) , as it allows networks to achieve test error that is nearly independent of depth (Figure 5b ). See Appendix C.1 for more discussion on this.

4.1. TOTAL VARIANCE EXPERIMENTS:

We train fully connected networks up to 200 layers deep and observe slowly increasing variance with depth (Figure 5a ). The experimental protocol is similar to what it was in Section 3, with a few differences: All networks have width 100 and achieve 0 training error. We train them to the same loss value of 5e-5 to control for differences in training loss. This value was chosen carefully by observing when training error had been 0 for a long time. The 3 kinds of different networks we train are vanilla fully connected, fully connected with skip connections, and fully connected with dynamical isometry initialization. We only show the experiment with dynamical isometry in the main paper, but the other two are in Appendix C.2 and Appendix C.3.

We settle on fully connected networks without skip connections, initialized using the initialization Pennington et al. (2017) recommend to achieve dynamical isometry. This is the best experimental protocol of the three we tried because it appears to largely mitigate the pathological problems that cause deeper networks to have higher test error. We compare the test accuracy of skip connections to that of dynamical isometry in Figure 5b 5 to see that while the test accuracy of skip connections varies by over 1% from depth 25 to 100, the corresponding error bars for the dynamical isometry test errors overlap (although test error does increase by about 0.1% from depth 25 to 200). This near lack of dependence of test error on depth is why we view this experiment as having controlled for confounding factors sufficiently well. Additionally, this is the only protocol of the three we tested where bias monotonically decreases with depth (Figure 5a , Appendix C).

Just as new advancements, such as skip connections and dynamical isometry, have greatly helped with test set performance, there could still be future advancements that change these results. For example, it seems plausible that we will eventually have model families whose test error decreases (with depth) until it plateaus and, similarly, variance that increases and plateaus.

To get a more fine-grain look at the effect of depth on variance, we estimate the terms of the law of total variance in Figure 2 , just as we did for width. Surprisingly, variance due to sampling is roughly constant again. Variance due to initialization increases with depth.

We view the increase in variance due to initialization that we observe as consistent with the conventional wisdom that Arora et al. (2018) summarizes: "Conventional wisdom in deep learning states that increasing depth improves expressiveness but complicates optimization." While Arora et al. (2018) focus on speed of training, the variance we measure in Figure 2 is about the diversity of different minima. Increasing depth seems to lead to different initial starting points optimizing to increasingly different functions, as evaluated on the test set. Li et al. (2017, Figure 7 ) provide visualizations that suggest that increasing depth leads to increasingly "chaotic" loss landscapes, which would indicate increasing variance on the training set.

5. DISCUSSION AND THEORETICAL INSIGHTS FOR INCREASING WIDTH:

Our empirical results demonstrate that in the practical setting, variance due to initialization decreases with network width while variance due to sampling remains constant. In Section 5.1, we review classical results from linear models and remark that these trends can be seen in over-parameterized linear models. In Section 5.2 we take inspiration from linear models to provide analogous arguments for this phenomenon in increasingly wide neural networks, under strong assumptions. In Section 5.3, we note the mismatch between width and depth (the trend of variance due to initialization with width is opposite the corresponding trend with depth), and we discuss why the assumptions in Section 5.2 might be increasingly inaccurate with deeper and deeper networks.

5.1. INSIGHTS FROM LINEAR MODELS:

The goal here is to gain insights from simple linear models. We discuss the standard setting which assumes a noisy linear mapping y = θ T x+ between input feature vectors x ∈ R N and real outputs, where E( ) = 0 and Var( ) = σ 2 . Note that x is not necessarily raw data, but can be thought of as the embedding of the raw data in R N , using feature functions; this allows for the "over-parameterized" setting in linear models where N > m, regardless of the dimensionality of the raw data. We consider linear fits ŷ = θT x obtained using mean-square error gradient-descent with random initialization.

We revisit the standard variance analysis for linear regression (Hastie et al., 2009, Section 7.3) , where one can give the explicit form of the gradient descent solution. For a training set S of size m, let X S denote the m × N data matrix whose i th row is the training point x T i . We also introduce the input correlation matrices:

EQUATION

The case where N ≤ m is standard: if X S has maximal rank, Σ S is invertible; the solution is independent of the initialization and given by θS

EQUATION

In the "fixed design" scenario, where we consider fixed training points x i , the expected prediction variance with respect to noise is then

EQUATION

In this case, the variance grows with the number of parameters. For example, by replacing Σ with its unbiased estimator m -1 Σ S , we recover the standard value (N/m)σ 2 (Hastie et al., 2009) .

The "over-parametrized" case where N > m is more interesting: even if X S has maximal rank, Σ S is not invertible. The kernel of Σ S is the subspace U ⊥ S orthogonal to the span U S of the training points x i . Gradient descent updates belong to U S , independent of U ⊥ S . Initialized at θ 0 , it gives the solution θS = P S ⊥ (θ 0 ) + P S (θ) + Σ + S X T S (9)

where P S and P S ⊥ are the projections onto U S and U ⊥ S , and superscript + denotes the pseudoinverse. The first term, orthogonal to the data, does not get updated during training and only depends on the initialization. The two others form the minimum norm solution, which lies in U S .

The form of the solution (Equation 9) has several consequences: (a) Initialization contributes to the variance. Thus, for the input x and using a standard initialization6 θ 0 ∼ N (0, 1 N I), we obtain Var θ0 (ŷ S ) = 1 N P S ⊥ (x) 2 (10) which is non zero whenever x has components orthogonal to the training data. Note, however, that the variance due to initialization actually decreases with the number of parameters.

(b) The expected variance due to noise is

EQUATION

) In this case, the variance scales as the dimension of the data, as opposed to the number of parameters. Thus, replacing Σ by its unbiased estimator m -1 Σ S , we find the value (r/m)σ 2 where r = rank(Σ S ) = dim U S .

We argue in the next section that, under specific assumptions that we discuss, these insights may be relevant for the non-linear case.

5.2. A MORE GENERAL RESULT:

We will illustrate our arguments in the following simplified setting.

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.

(a) The optimization of the loss function is invariant with respect to θ M⊥ . (b) Regardless of initialization, the optimization method consistently yields a solution with the same θ M component, (i.e. the same vector when projected onto M).

These are strong assumptions, but there is some support for them in the literature. 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-parametrized networks splits into (i) a bulk centered near zero and (ii) a small number of large eigenvalues, which suggests7 that learning occurs mainly in a small number of directions. The existence of a subspace M ⊥ in which no learning occurs was also conjectured by Advani and Saxe (2017) and shown to hold in deep linear networks under a simplifying assumption that decouples the dynamics of the weights in different layers.

5.2.1. VARIANCE DUE TO INITIALIZATION:

Given the above assumptions, the following result shows that the variance from initialization 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. 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,

EQUATION

)

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, L = o( √ N ).

5.2.2. VARIANCE DUE TO SAMPLING:

Under the above assumptions, the parameters at the end of learning take the form θ = θ * M + θ 0M ⊥ . For fixed initialization, the only source of variance of the prediction is the randomness of θ * M on the learning manifold. The variance depends on the parameter dimensionality only through dim M = d(N ), and hence remains constant if d(N ) does (Li et al., 2018) .

5.3. DISCUSSION ON ASSUMPTIONS IN INCREASINGLY DEEP NETWORKS:

The mismatch between the outcome of our theoretical analysis and the observed trend of variance due to initialization with depth suggests that our assumptions are increasingly inaccurate with depth.

For some intuition about why this may be the case, consider the dependence of gradients with respect to subsets of hidden units, as these gradients are related to assumption (a): the invariance of the optimization process to θ M⊥ . Gradients of hidden units in the same layer (related to width) do not directly depend on each other; rather, only optimization induces dependencies between them via the loss function. In sharp contrast, hidden units in different layers (related to depth) are functions of their preceding layers, and similarly, the gradients with respect to earlier layers are functionally dependent on the gradients with respect to later layers. This hints at more complex optimization interactions between parameters when increasing depth.

6. CONCLUSION AND FUTURE WORK:

By revisiting the bias-variance decomposition and using a finer-grain method to empirically study variance, we find interesting phenomena. First, the bias-variance tradeoff is misleading for network width (one way to increase size) as the measure of model complexity. Second, variance due to sampling does not appear to be dependent on width or depth. Third, variance due to initialization is roughly consistent with the optimization literature, as we observe the test set analog of the current conventional wisdom for both width and depth. Finally, by taking inspiration from linear models, we perform a theoretical analysis of the variance that is consistent with our empirical observations for increasing width.

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. Additionally, it may be fruitful to apply the biasvariance lens to other network architectures, such as convolutional networks and recurrent networks. We argue it is worth running variance vs. depth experiments using future best practices to train deep models, as the results could be different. More theoretical work is also needed to achieve a full understanding of the behaviour of variance in deep models. Variance is analytically different from generalization error in that the definition of variance does not involve the labels at all. We view the bias-variance lens as a useful tool for studying generalization in deep learning and hope to encourage more work in this direction.

Appendices APPENDIX A PROBABILISTIC NOTION OF EFFECTIVE CAPACITY:

The problem with classical complexity measures is that they do not take into account optimization and have no notion of what will actually be learned. Arpit et al. (2017, Section 1) define a notion of an effective hypothesis class to take into account what functions are possible to be learned by the learning algorithm.

However, this still has the problem of not taking into account what hypotheses are likely to be learned. To take into account the probabilistic nature of learning, we define the -hypothesis class for a data distribution D and learning algorithm A, that contains the hypotheses which are at least -likely for some > 0:

EQUATION

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's -hypothesis class can lead to drastically different intuitions for the complexity of a model and its variance (Figure 6 ). 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 Figure 8 when we do not tune the step size is explained by the fact the constant step chosen is a "good" step size for some networks and "bad" for others. Results from Keskar et al. (2017) and Smith et al. (2018) 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. Figure 11 : Caricature examples of high variance learners on sinusoid task. Below, we find that this does not happen with increasingly wide neural networks (Figure 13 and Figure 14 ). 5, 10, 15, 17, 20, 22, 25, 35, 75, 100, 1000, 10000. We do not observe the caricature from Figure 11 as width is increased. 5, 10, 15, 17, 20, 22, 25, 35, 75, 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

P(|h(θ) -E[h]| > ) ≤ 2 exp -C n 2 L 2 R 2 (14)

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:

EQUATION

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 Var(h

) = E[(h - E[h]) 2 ]. Then Var(h) ≤ 2L 2 σ 2 C (16) Proof. Let g = h -E[h].

Then Var(h) = Var(g) and

EQUATION

Now swapping expectation and integral (by Fubini theorem), and by using the identity E1 |g|>t = P(|g| > t), we obtain

Var(g) = 2 ∞ 0 t P R (|g| > t) dt ≤ 2 ∞ 0 2t exp -C t 2 L 2 σ 2 dt = 2 - L 2 σ 2 C exp -C t 2 L 2 σ 2 ∞ 0 = 2L 2 σ 2 C

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

EQUATION

)

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,

P(|h θ (x) -E[h θ (x)]| > ) ≤ 2 exp -C N 2 L 2 (19)

for some universal constant C > 0.

Proof. In our setting, the parameters at the end of learning can be expressed as

θ = θ * M + θ M ⊥ (20)

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

EQUATION

Let g(θ M ⊥ ) h θ * M +θ M ⊥ (x). By Assumption 3, g(•) is L-Lipschitz. Then, by the Gaussian concentration theorem we get,

EQUATION

)

The result of Theorem 1 immediately follows from Theorem 2 and Corollary 1, with σ 2 = 1/N :

EQUATION

)

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.2 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 

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,

EQUATION

)

where Y denotes the one-hot vector representation of the class y.

Proposition 1. 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 L(h) = Prob x,y {h(x) y < 1 2 } (26)

:

Some recent work has gone in the direction of taking this information into account, see e.gKuzborskij and Lampert (2018);Dziugaite and Roy (2017).

We do not study randomness from stochastic mini-batching because we found the phenomenon of decreasing variance with width persists when using batch gradient descent (

Section 3.3, Appendix B.3).

Note that tuning the step size controls validation error for a specific network size. The question we study in our empirical analysis is how variance at these low validation error points varies with size of the network.

Because we don't have access to ȳ, we use the labels y to estimate Ebias. This is equivalent to assuming noiseless labels and is standard procedure for estimating bias(Kohavi and Wolpert, 1996; Domingos, 2000).

Note that the best dynamical isometry network achieves test set accuracy of about 0.4% worse than the best skip connection network due to the fact that dynamical isometry is not possible with ReLU activations, so Tanh is used(Pennington et al., 2017).

It is such that the initial parameter norm θ0 has unit variance.

Provided the corresponding eigenspace decomposition is preserved throughout training.

Figures and Tables:

Figure1: On the left is an illustration of the common intuition for the bias-variance tradeoff (Fortmann-Roe, 2012). We find that variance decreases along with bias when increasing network width (right). These results seem to contradict the traditional intuition.

Figure 2: Trends of variance due to sampling and variance due to initialization with width (left) and with depth (right). Variance due to sampling is roughly constant with both width and depth, in contrast with what the bias-variance tradeoff might suggest. Variance due to initialization differentiates the effects of width and depth and is in line with neural network optimization literature.

Figure 4: Visualization of the 100 different learned functions of single hidden layer neural networks of widths 15, 1000, and 10000 (from left to right) on the task of learning a sinusoid. The learned functions are increasingly similar with width, not increasingly different. More in Appendix B.4.

Figure 6: The dotted red circle depicts a cartoon version of the -hypothesis class of the learner.The left side reflects common intuition, as informed by the bias-variance tradeoff and worst-case analysis from statistical learning theory. The right side reflects our view that variance can decrease with network width.

Figure 8: Variance on small data with a fixed learning rate of 0.01 for all networks.

Figure9: Variance decreases with width in the small data setting, even when using batch gradient descent.

Figure10: Variance decreases with width in the small data setting, even when using a strong optimizer, such as PyTorch's LBFGS, as the optimizer.

Figure 12: Target function of the noisy sinusoid regression task (in gray) and an example of a training set (80 data points) sampled from the noisy distribution.

Figure 13: Visualization of 100 different functions learned by the different width neural networks. Darker color indicates higher density of different functions. Widths in increasing order from left to right and top to bottom: 5, 10, 15, 17, 20, 22, 25, 35, 75, 100, 1000, 10000.  We do not observe the caricature from Figure11as width is increased.

Figure14: Visualization of the mean prediction and variance of the different width neural networks. Widths in increasing order from left to right and top to bottom:5, 10, 15, 17, 20, 22, 25, 35, 75, 100,  1000, 10000.

Figure 18: Additionally, dynamical isometry seems to cause bias to decrease monotonically 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.

y=1 h(x) y = 1. The classification loss is defined byL(h) = Prob x,y {h(x) y < max y h(x) y } = E (x,y) I(h(x) y < max y h(x) y )

B.3 OTHER OPTIMIZERS FOR WIDTH EXPERIMENT ON SMALL DATA MNIST

Table content: <table><tr><td/><td>0.07 0.08</td><td/><td>Bias Variance</td><td>0.7 0.8</td><td/><td>Test Error Train Error</td></tr><tr><td>Bias and Variance</td><td>0.03 0.04 0.05 0.06</td><td/><td>Average Error</td><td>0.6 0.2 0.3 0.4 0.5</td><td/></tr><tr><td/><td>0.02</td><td/><td/><td>0.0 0.1</td><td/></tr><tr><td/><td>10 0</td><td>10 1 Number of hidden units 10 2 10 3</td><td>10 4</td><td>10 0</td><td>10 1 Number of hidden units 10 2 10 3</td><td>10 4</td></tr></table>

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 3 layers, which is what was seen without skip connections, 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.4 DYNAMICAL ISOMETRY DEPTH EXPERIMENTSThe figures in this section are included in the main paper, but they are included here for comparison to the above and for completeness.

Table content: <table><tr><td colspan="4">C.3 SKIP CONNECTIONS DEPTH EXPERIMENTS</td><td/><td/></tr><tr><td>Bias and Variance</td><td>0.0015 0.0020 0.0025 0.0030</td><td colspan="2">Bias Variance</td><td>Average Test Error</td><td>0.0225 0.0250 0.0275 0.0300 0.0325 0.0350</td><td>Test Error</td></tr><tr><td/><td>0</td><td>10 Number of skip connections 20 30 40</td><td>50</td><td/><td>0</td><td>10 Number of skip connections 20 30 40</td><td>50</td></tr><tr><td colspan="7">10 2 Number of hidden units 10 3 Bias Variance 10 4 100,  1000, 10000.   10 1 0.00 0.05 0.10 0.15 0.20 0.25 Bias and Variance 10 1 10 2 10 3 10 4 Number of hidden units 0.00 0.05 0.10 0.15 0.20 0.25 0.30 0.35 Average Test Loss Test Loss Figure 17: 0 50 100 150 200 Number of hidden layers 0 50 100 150 Number of hidden layers 200 0.026 0.00175 0.00200 0.00225 0.00250 0.00275 0.00300 0.00325 Bias and Variance Bias Variance 0.027 0.028 0.029 Average Test Error 0.030 Test Error</td></tr></table>

Peer review (iclr2019):
 This paper studies variance-bias tradeoff as a function of depth and width of a neural network. Experiments suggest that variance may decrease as a function width and increase as a function of depth. Some analytical results are presented why this may the case for width and why the necessary assumptions for the depth are violated. Main comment on experiments: if I am correct the step size for optimization is chosen in a data-dependent way for each size of the network. This is a subtle point since it leads to a data-dependent hypothesis set. In other words, in this experiments for each width we study variance of neural nets that can be found in fixed number of iterations by a step size that is chosen in data-dependent way. It may be the case that as width grows the step size decreases faster and hence hypothesis set shrinks and we observe decreasing variance. This makes the results of experiments with width not so surprising or interesting. Further comments on experiments: it probably worth pointing out that results for depth are what we would expect from theory in general. More on experiments: it would be also interesting to see how variance behaves as a function of width for depth other than 1. On assumptions: it is not really clear why assumptions in 5.2 hold for wide shallow networks at least in some cases. Paper provides some references to prior work but it would be great to give more details. Furthermore, some statements seems to be contradicting: sentence before 5.2.1 seems to say that assumption (a) should hold for deep nets while sentence at the end of page 8 seems to say the opposite. Overall: I think this paper presents an interesting avenue of research but due to aforementioned points is not ready for publication.