Scaling description of generalization with number of parameters in deep learning

Abstract

Supervised deep learning involves the training of neural networks with a large number $N$ of parameters. For large enough $N$, in the so-called over-parametrized regime, one can essentially fit the training data points. Sparsity-based arguments would suggest that the generalization error increases as $N$ grows past a certain threshold $N^{*}$. Instead, empirical studies have shown that in the over-parametrized regime, generalization error keeps decreasing with $N$. We resolve this paradox through a new framework. We rely on the so-called Neural Tangent Kernel, which connects large neural nets to kernel methods, to show that the initialization causes finite-size random fluctuations $\|f_{N}-\bar{f}_{N}\|\sim N^{-1/4}$ of the neural net output function $f_{N}$ around its expectation $\bar{f}_{N}$. These affect the generalization error $\epsilon_{N}$ for classification: under natural assumptions, it decays to a plateau value $\epsilon_{\infty}$ in a power-law fashion $\sim N^{-1/2}$. This description breaks down at a so-called jamming transition $N=N^{*}$. At this threshold, we argue that $\|f_{N}\|$ diverges. This result leads to a plausible explanation for the cusp in test error known to occur at $N^{*}$. Our results are confirmed by extensive empirical observations on the MNIST and CIFAR image datasets. Our analysis finally suggests that, given a computational envelope, the smallest generalization error is obtained using several networks of intermediate sizes, just beyond $N^{*}$, and averaging their outputs.

Introduction

Deep neural networks (DNNs) have proven to be very successful at a very wide range of tasks. In particular, for supervised learning tasks, they have yielded breakthroughs in various contexts, in particular for image classification , speech recognition , and automatic translation . Yet, a theoretical framework to understand the remarkable successes of DNNs remains to be constructed, and central questions need to be clarified.

Second, DNNs are in practice trained in the so-called over-parametrized regime, where the number of parameters $N$ is much larger than the number of data points $P$. Thus, DNNs are used in a regime where their capacity is very large (they can still classify the data even if all their labels are randomized). Surprisingly from the point of view of traditional statistical learning theory DNNs generalize very well in practice, even without an explicit regularization. This thus raises the question of an appropriate framework to understand generalizations of DNNs.

Recent works suggest that the two questions above are closely connected. Numerical and theoretical studies show that in the over-parametrized regime, the loss landscape of DNNs is not rough with isolated minima as initially thought , but instead has connected level sets and presents many flat directions, even near its global minimum. In particular, recent works on the over-parametrized regime of DNNs have shown that the landscape around a typical initialization point becomes essentially convex, allowing for convergence to a global minimum during training.

In , it has been observed that when optimizing DNNs (using the so-called hinge loss), there is a sharp phase transition — whose location can depend on the chosen dynamics — at some $N^{*}(P)$ such that for $N\geq N^{*}$ the dynamic process reaches a global minimum of the loss. In particular whenever $N>N^{*}$, the training error (i.e. the total of the loss on the training set) reaches its global minimum. A counter-intuitive aspect of deep learning is that increasing $N$ above $N^{*}$ does not destroy the predictive power by over-fitting the data, but instead appears to improve the generalization performance (i.e. the probability that a data point outside of the training set is correctly classified) . Indeed the test error (the probability of an incorrect classification for an unseen data point) has been observed to decrease as $N\rightarrow\infty$ in a slow power-law fashion . In contrast, as $N\to N^{*}$, the test error blows up (a phenomenon shown by the blue curve in Fig. 2). In the context of least-squares regression, the improvement of performance with $N$ has been linked to the observed diminishing fluctuations of the DNN function after training , a result consistent with the notion of stronger implicit regularization with increasing $N$ . This raises the question of understanding what controls these fluctuations and how they affect the test error in a classification task.

In this work, we address these questions in the context of classification tasks for fully-connected DNNs with a fixed number of layers $L\geq 2$, with wide hidden layers. We develop a framework based on a new connection between the $N\rightarrow\infty$ limit of DNNs and kernel methods . More precisely, the training of DNNs can be recast as a kernel gradient descent associated with the so-called Neural Tangent Kernel (NTK). In the $N\to\infty$ limit, the NTK becomes deterministic and constant in time. This result explains why the generalization performance converges as $N\rightarrow\infty$, a result previously obtained for single hidden layer neural networks using a different approach .

First, we introduce an NTK-based framework to study the random fluctuations of the output function $f_{N}$ at the end of training due to the random initialization of the parameters. We find that (in the over-parametrized regime) the key finite-$N$ effect is that the NTK at initialization has random fluctuations around its mean of order $N^{-\nicefrac{{1}}{{4}}}$, leading to similar fluctuations for $f_{N}$.

Second, we consider the fluctuations of the decision boundary (the level set $\{f_{N}(x)=0\}$): we argue that a variation $\delta f_{N}$ of $f_{N}$ yields an increase $\delta\epsilon\sim(\delta f_{N})^{2}$ to the test error. We use this asymptotic result to predict the increase in generalization performance yielded by an ensemble averaging on $n$ samples of the function $f_{N}$ (each trained on the data separately) as $n$ becomes large, as well as the increase in generalization performance as $N$ grows.

Finally, this description breaks down at the transition point $N^{*}$, where the random fluctuations of $f_{N}$ appear to diverge as a power law. We study this divergence through a simple argument on non-linear networks, suggesting that $\|f_{N}\|\sim(N-N^{*})^{-1}$.

Overall, our work introduces a conceptual framework to describe how generalization error in deep learning evolves with the number of parameters. A practical consequence of our analysis is that performing an ensemble average of (both fully-connected and convolutional) DNNs with independent initializations can improve performance significantly: for a given computational envelope, it appears to be best to use several nets of intermediate sizes $N>N^{*}$ and to average their outputs.

After the electronic submission of the present work, and following on , other articles have been written on the nature of the “double descent” curve in the generalization error (Fig. 2) and on the asymptotic behavior of wide networks . Very recently in , a rigorous derivation of the double descent curve was obtained for the mean square regression of simple functions using random features models. Although the scaling arguments proposed here are not mathematical proofs, they provide a quantitative explanation of the double descent curve in a more general setting, including the regression and classification of empirical data by fully connected deep networks. Our predictions are tested empirically in that setting. Finally, our analysis is based on a scaling estimate of the fluctuations of the NTK at initialization, recently supported by more detailed analysis based on Feynman diagrams and path numbering .

Setting

where $\Delta_{\mu}\equiv\epsilon_{m}-y_{\mu}f(x_{\mu};\theta)$ and $\epsilon_{m}$ is the so-called margin, fixed to $1$ in our numerical tests.

The network is then trained using a first-order method, such as gradient descent, for a maximum running time of $t^{*}$, and is stopped as soon as the training loss hits its lowest possible value (typically , unless two identical data points have different labels). The jamming transition point is defined as the smallest value of $N$ for which we reach the lowest possible loss at the end of training.

Note that the hinge loss leads to results that are very similar to the ones relying on the more commonly used cross-entropy loss . It has the advantage however to stop in finite time in the over-parametrized regime $N>N^{*}$.

2 Numerical Setting

We first consider the task of classifying the parity of digits on the MNIST database . For this architecture we consider only the first ten PCA components of the images. We then test our findings with a CNN architecture on the full images in the CIFAR10 dataset.

The DNNs are trained using a full-batch procedure (as opposed to stochastic gradient) described in $S.I$, for a maximum running time $t^{*}=2\cdot 10^{6}$ steps.

Numerical Results on MNIST

Fig. 2 demonstrates the performance of the above setup for the MNIST dataset: we find that at the end of training, the test error (i.e. the empirical generalization error) reaches a local maximum in a cusp-like fashion near the jamming transition $N^{*}$ and then slowly decreases as $N$ becomes larger. We denote by $\bar{f}_{N}^{n}$ the average of $n$ samples of the function $f_{N}$ taken with independent initial conditions. Remarkably, in our experiments, ensemble-averaging with $n=20$ leads to a nearly flat test error for $N>N^{*}$; this supports the hypothesis that the improvement of generalization performance with $N$ originates from reduced variance of $f_{N}$ when $N$ gets large, as recently observed for mean-square regression . In addition to this leading finite-size effect, an interesting sub-leading finite-size effect can be observed, as discussed in Section 7.

Our results below apply directly to mean square regression. In the next paragraphs we will argue that a similar quadratic relationship between test error and fluctuations also holds for classification under mild assumptions on the data; so that our results extend to that case as well.

2 Classification task

We now provide a heuristic argument relating fluctuations of the output function $f_{N}$ to generalization performance. For a random function $f$ (e.g. a DNN function with random initialization), we denote by $\langle\cdot\rangle=\langle\cdot\rangle_{f}$ the expectation with respect to $f$.

Consider a random smooth function $f$ with expectation $\bar{f}$, and set $\delta f\equiv f-\bar{f}$. Let $B,\bar{B}$ denote the decision boundaries $B=\{f(x)=0\},\bar{B}=\{\bar{f}(x)=0\}$, and consider a point $x_{0}$ that is being classified differently by $f$ and $\bar{f}$, i.e. $f(x_{0})\bar{f}(x_{0})<0$, as illustrated in Figure 3. Imagine drawing the shortest segment passing through $x_{0}$ that starts from a point in $\bar{B}$ and ends in $B$. If its length $\delta(x_{0})$ is small, then the signed distance $\delta(x_{0})$ between $B$ and $\bar{B}$ is $\delta(x_{0})=\delta f(x_{0})/|\!|\nabla f(x_{0})|\!|+o(\delta f(x_{0}))$. Note that for smooth activation functions, the smoothness of DNN output function is guaranteed and for ReLU-based DNNs, the output function is smooth outside of the training points (see S.I.). We show direct measurements of $\delta(x)$ in Section A of S.I., supporting that this estimate still holds and becomes more and more accurate as $N\rightarrow\infty$.

Next, we introduce the typical distance $\delta$ along the boundary:

where the average is taken over all the test data $x_{0}$ classified differently by $f$ and $\bar{f}$. As numerically shown in S.I., $\delta$ is very well estimated by $|\!|\delta f|\!|_{\mu}/|\!|\nabla f|\!|_{\mu}$ where $\mu$ is the uniform measure on all the test set.

We then denote by $\Delta\epsilon$ the difference between the true test error of $f$ and that of $\bar{f}$. Under reasonable assumptions We assume that the true test error is a smooth function of the decision boundary. This holds true if the probability distributions to find data of different labels are themselves smooth functions of the input (this is the case, for instance, if the input data have Gaussian noise). it can be expanded by considering a small perturbation of the decision boundary $\bar{B}$ of ${\bar{f}}$ (that can consist of unconnected parts):

The fact that $\langle\delta f(x)\rangle=0$, suggests that $\langle\delta(x)\rangle={\cal O}(\delta f(x)^{2})$. This suggests in turn that in average the true test error increases quadratically with the norm of fluctuations $\delta f$:

Note that if $\bar{f}$ displays a minimal true test error, the decision boundary is optimal: $\partial\epsilon/\partial\delta(x)=0$ and $\partial^{2}\epsilon/\partial^{2}\delta(x)\geq 0$ for all $x\in B$, implying that the prefactor in Eq. (5) must be positive The pre-factor could be zero if the optimal boundary is degenerate, a situation that will not occur generically if the data have e.g. Gaussian noise.. If the true test error is small, the decision boundary will tend to be close to the ideal one, so that the prefactor in Eq. (5) will still be positive. We expect this to be the case for the MNIST model we consider for which the test error is a few percents.

Eq. (5) is a result on the ensemble average of the true test error. Yet, our data in Fig. 2 supports that the test error is a self-averaging quantity: the test error of a given output function (blue points) lies close to its average (blue line).

Asymptotic generalization as n→∞→𝑛n\rightarrow\infty

Using the tools of the previous section, we can now study how an ensemble average $f^{n}_{N}$ of $n$ networks behaves in the $n\rightarrow\infty$ limit. The central limit theorem and the law of large numbers imply that $\delta f^{n}_{N}\sim 1/\sqrt{n}$ while $|\!|\nabla f^{n}_{N}|\!|_{\mu}$ converges to a constant. Thus $\delta\sim 1/\sqrt{n}$ and for the true test errors $\epsilon^{n}_{N}$ and $\bar{\epsilon}^{n}_{N}$ of $f^{n}_{N}$ and $\bar{f}^{n}_{N}$, we have $\epsilon_{N}^{n}-\bar{\epsilon}_{N}^{n}\sim 1/n$. These predictions are confirmed in Fig. 4.

Asymptotic Generalization as N→∞→𝑁N\rightarrow\infty

We now study the fluctuations of $f_{N,t}$ throughout training for large networks using the NTK . At initialization $t=0$, $f_{N,t=0}$ is a random function whose limiting distribution as $N\to\infty$ is an explicit Gaussian . These types of fluctuations do not vanish as $N\to\infty$: the variance of $f_{N,t=0}$ at initialization is essentially constant in $N$ In our setup, the output variance at initialization is smaller than one. It is possible to suppress the randomness of $f_{N,t=0}$ at initialization by training $f^{\prime}_{t}=f_{t}-f_{t=0}$. We have observed that it does not qualitatively affects our results..

However, during the DNN training, the fluctuations of $f_{N,t}$ will shrink around the training points . At the end of training, outside of the training points, the fluctuations due to the random initialization of the parameters manifest themselves in two ways: from the randomness of the initialization point in function space $f_{N,t=0}$ and from the randomness of the learning dynamics. The first one is essentially independent of $N$. Hence, to understand the way the fluctuations of the function at convergence $t\to\infty$ decrease with $N$, we must thus study the random fluctuations of the training process. The gradient descent dynamics of $f_{N,t}$ is described by the NTK $\Theta_{N,t}$:

where $\frac{d}{d\theta_{k}}f_{N,t}$ is the derivative of the output of the network with respect to one parameter $\theta_{k}$ and the sum is over all the network’s parameters. For a general cost $C(f)=\frac{1}{P}\sum_{i}c_{i}(f(x_{i}))$, the function follows the kernel gradient $\nabla_{\Theta_{N,t}}C_{|f_{N,t}}$ of the cost during training

The NTK is random at initialization and varies during training. However as the number $h$ of neurons in each hidden layer goes to infinity, the NTK converges to a deterministic limit $\Theta_{N}^{t}\to\Theta_{\infty}$ which stays constant throughout training . In this limit, the training corresponds to that of a kernel method (i.e. the output evolves along the vector space spanned by the functions $\Theta_{\infty}(x,x_{i})$). The random fluctuations of the training process have now themselves two sources: the random fluctuations of the NTK at initialization, and the evolution of the NTK during training. On the one hand, we have that the variation of the NTK during training is of order $1/\sqrt{N}$, as is suggested by :

($\left\|\Theta\right\|_{F}=\sum_{ij}\Theta(x_{i},x_{j})^{2}$ is the Frobenius norm of the Gram matrix computed over the training set). On the other hand, the random fluctuations of the NTK at initialization are of order $N^{-\nicefrac{{1}}{{4}}}$

Eq. (8) can be readily obtained by re-writing Eq. (6) as a sum on neurons and using the central limit theorem, as sketched in S.I. and tested empirically in . From the above, we see that dominant source of random fluctuations during training is due to the randomness of the NTK at initialization and is of order $N^{-\nicefrac{{1}}{{4}}}$.

Because the NTK describes the behaviour of the function $f_{N,t}$ during training, and because the time to converge to a minimum of the loss converges to a constant as $N\rightarrow\infty$, from Eq. (7) we expect the variance of the NTK to induce some variance of the same order to the function at the end of training: this is proven in the case of the mean square loss in the S.I. Hence, the random fluctuations of the kernel leads to fluctuations of $f_{N}^{t=\infty}$ of order $\mathcal{N}^{-\nicefrac{{1}}{{4}}}$, and we predict:

where the residual variance \Big{\langle}|\!|f_{\infty}-\bar{f}_{\infty}|\!|_{\mu}\Big{\rangle} is due to the fact that we consider a finite dataset. In our setting, since our dataset is large, this residual term is negligible, leading one to:

We expect the fluctuations of $\nabla f_{N}$ to be of the size as those of $f_{N}$, leading to $|\!|\nabla f_{N}|\!|_{\mu}=C_{0}+C_{1}N^{-\nicefrac{{1}}{{4}}}+o(N^{-\nicefrac{{1}}{{4}}})$. This result is consistent with our observations, as shown in Fig. 6.A, in which we find empirically that $C_{1}$ is much larger than $C_{0}$. For the true test errors $\epsilon_{N},\bar{\epsilon}_{N}$ of $f_{N},\bar{f}_{N}$, from the decision boundary discussion, we get

where $\delta_{N}$ indicates the typical distance between the decision boundaries $\bar{f}_{N}=0$ and $f_{N}=0$, as supported by Fig. 6.B. The fluctuations of the decision boundary $\delta_{N}$ can be approximated by $|\!|f_{N}-\bar{f}_{N}|\!|/|\!|_{\mu}\nabla f_{N}|\!|_{\mu}$, as supported by Fig. 6.C, leading to $\delta_{N}=A_{0}N^{-\nicefrac{{1}}{{4}}}+A_{1}N^{-\nicefrac{{1}}{{2}}}+o(N^{-\nicefrac{{1}}{{2}}})$. We then obtain the key prediction

Since we measure both $\epsilon_{N}$ and $\bar{\epsilon}_{N}$ independently, we can test the prediction for the leading exponent without any fitting parameters, and indeed confirm that asymptotically $\epsilon_{N}-\bar{\epsilon}_{N}$ is of order $N^{-\nicefrac{{1}}{{2}}}$ as shown in Fig. 6.D.

Finally we estimate the evolution of test error with $N$. We have:

where $\epsilon_{\infty}$ denotes the true test error of $f_{N}$ as $N\to\infty$ (notice that $\epsilon_{\infty}$ is still random, due to the random initialization and the fact that we have a finite dataset). The first term was estimated above, and turns out to be the dominant one for large datasets. The last term is independent of $N$, and cancels the first term for asymptotically large $N$ (unaccessible in our numerics).

We provide a scaling argument to estimate the size of the second term. For large $N$, we expect the difference between $\bar{f}_{N}$ and $\bar{f}_{\infty}$ to stem from (i) the evolution of the kernel with time (which corresponds to learning features) and (ii) the fact that the relationship between the kernel and the function at infinite time is not linear, as described for the mean square loss in Eq. (17) of the S.I. Both effects are ${\cal O}(N^{-1/2})$, i.e. much smaller than the ${\cal O}(N^{-1/4})$ fluctuations of $f_{N}$ around its mean. The typical distance $\delta_{N,\infty}$ between the interfaces $\bar{f}_{N}=0$ and $\bar{f}_{\infty}=0$ is thus small and ${\cal O}(N^{-1/2})$. According to Eq. (4) we get:

Thus $\bar{\epsilon}_{N}-\bar{\epsilon}_{\infty}={\cal O}(N^{-1/2})$ cannot be neglected a priori. Overall, we get:

a form indeed consistent with observation as shown in Fig. 2.

For MNIST, both for FC and CNN (below), we always find $B_{0}>0$, consistent with the notion that the dominant effect of finite $N$ is the increase in fluctuations of the output.

Note that a direct fit of the test error vs $N$ gives an apparent exponent smaller than $\nicefrac{{1}}{{2}}$ , reflecting that (i) power-law fits are less precise when the value for the asymptote (here the value of $\epsilon_{\infty}$) is a fitting parameter and (ii) that correction to scaling needs to be incorporated for a good comparison with the theory (a fact that ultimately stems from the large correction to scaling of $|\!|\nabla f_{N}|\!|_{\mu}$ shown in Fig. 6.A).

Vicinity of the jamming transition

The asymptotic description for generalization in the large $N$ limit is not qualitatively useful for $N\leq N^{*}$, where a cusp in test error is found. In the perceptron, the simplest network without hidden layers, the cusp in the test error at the jamming point is also observed and predicted analytically . Here instead, we argue that this cusp is induced by a divergence of $|\!|f_{N}|\!|_{\mu}$ at $N^{*}$ when no regularization is used, as apparent in Fig. 7.A (no such divergence happens in the perceptron where $|\!|f_{N}|\!|_{\mu}$ is generally imposed). Indeed following our argument of Section 3, this effect must lead to singular fluctuations of the decision boundary at $N^{*}$, suggesting a singular behavior for the true test error. This phenomenon shares some similarity with the norm divergence that occurs in linear networks with mean square loss for which $|\!|f_{N}|\!|_{\mu}\sim|N-P|^{-2}$ . Yet, for losses better suited for classification such as the hinge loss, we argue that this explosion occurs at a different location with a different exponent.

This predicted inverse relation is tested in Fig. 7.B. It is important to note that, as it is the case for any critical points, working at finite times cuts off a true singularity: as illustrated in Fig. 7.B $|\!|f_{N,t}|\!|$ becomes more and more singular as $t$ grows. This effect also causes a shift of the transition $N^{*}$ where the loss vanishes, that converges asymptotically to a well-defined value in the limit $t\rightarrow\infty$ as documented in . $N^{*}$ is therefore defined when $\|f_{N,t}\|$ displays a power law as function of $N/N^{*}-1$.

Note that for other losses like the cross-entropy, the dynamics never stops completely but becomes extremely slow . In such cases, we expect that asymptotically $|\!|f_{N,t}|\!|=\infty$ as soon as $N>N^{*}$, although this singularity should build up logarithmically slowly in time. For finite learning times we expect that a singularity will occur near $N^{*}$, but will be blurred as for the hinge loss if $t<\infty$.

Subleading Finite-Size Effect

For a given computational envelope, it appears be more efficient to take a value of $N$ slightly bigger than $N^{*}$, and to perform ensemble-averaging to reduce the variance. Quite remarkably, as shown in Figure 2, an additional effect appears to take place after ensemble-averaging: taking $N$ only slightly bigger than $N^{*}$ is not only more efficient from a computational point of view, but it also yields to a slightly better generalization performance than $N\gg N^{*}$. This corresponds to the middle term in Equation 13.

This could be viewed as supporting the classical intuition that keeping the models sparse by controlling the number of parameters is useful, when one averages over differently initialized networks and once the network is large enough. This effect appears stronger for CNN architecture, as confirmed in Section 8.

This effect could be explained by an evolution of the NTK during training. It suggests the possibility that (with ensembling) DNNs at finite $N$ perform better than their kernel method counterparts. It hence appears to be both a very promising direction for future theoretical research and to be of practical interest.

Extension to Convolutional Networks

In this section, we test the generality of our findings for Convolutional Networks (CNNs) used for classification. We train the CNN on the CIFAR10 dataset which consists of 50,000 training and 10,000 test images of 32 by 32 resolution. Each image is labeled by one of the ten possible classes. The architecture is a vanilla model with 3 convolutional and 1 fully-connected layers. Each convolutional layer has $\mathsf{f}$ channels and the output of the CNN is a $10$-dimensional vector (see S.I. for more details). The loss function is linear-hinge $C=\frac{1}{P}\sum_{\mu=1}^{P}\max(0,\Delta_{\mu})$. We vary $\mathsf{f}$ from $2^{1}$ to $2^{11}$. For each value of $\mathsf{f}$, we train $n=20$ models with independent random initial conditions. For each $\mathsf{f}$, the learning rate throughout is fixed at $1/\mathsf{f}$. The jamming transition occurs just before $\mathsf{f}\sim 28$. Soon after the transition, at $\mathsf{f}\sim 40,48,64$, the mean performances are between $\sim\%67-72$. The performance of the ensemble averaging is $\sim\%80.5-80.7$, and the average accuracy of the widest models is a little bit less than $\sim\%77.5$. Peak performance is achieved by ensembling with $\mathsf{f}=64$, yielding a value of $\sim 80.7\%$, while the average performance without ensembling is lowest at $\mathsf{f}=1280$ with a value of $\sim 77.5\%$.

Conclusion

We have provided a description for the evolution of the generalization performance of fixed-depth fully-connected deep neural networks, as a function of their number of parameters $N$. In the asymptotic regime of very large $N$, we find empirically that the network output displays reduced fluctuations with $|\!|f_{N}-\bar{f}_{N}|\!|_{\mu}\sim N^{-\nicefrac{{1}}{{4}}}$. We have argued that this scaling behavior is expected from the finite $N$ fluctuations of the Neural Tangent Kernel known to control the dynamics at $N=\infty$. Next we have provided a general argument relating fluctuations of the network output function to decreasing generalization performance, from which we predicted for the test error $\epsilon_{N}-\epsilon_{\infty}=C_{0}N^{-\nicefrac{{1}}{{2}}}+C_{1}N^{-\nicefrac{{3}}{{4}}}+\mathcal{O}(N^{-1})$, consistent with our observation on MNIST. Overall this approach explains the surprising finding that generalization keeps improving with the number of parameters.

We have then argued that this description breaks down at $N=N^{*}$ below which the training set is not fitted. For the hinge loss where this jamming transition is akin to a critical point, and in the case where no regularization (such as early stopping) is used, we observe the apparent divergence $|\!|f_{N}|\!|\sim(N-N^{*})^{-\alpha}$. We have argued, based on reasonable assumptions, that $\alpha=1$, consistent with our observations. This predicted blow up of the norm of $f_{N}$ explains the spike in the error observed at $N^{*}$.

Our analysis furthermore suggests that optimal generalization does not require to take $N$ much larger than $N^{*}$: since improvement of generalization with $N$ stems from reduced variance in the output function, near-optimal generalization is readily obtained by performing an ensemble average of networks with $N$ fixed, e.g. taken to be a few times $N^{*}$. The usefulness of averaging breaks down near $N^{*}$, where the variance of $f_{N}$ is too large. This suggests that given a computational envelope, it is best from a generalization performance point of view to ensemble slightly beyond the jamming transition point. This is a result of practical importance which needs to be tested in a wide range of architectures and datasets.

Acknowledgements

We thank Marco Baity-Jesi, Carolina Brito, Chiara Cammarota, Taco S. Cohen, Silvio Franz, Yann LeCun, Florent Krzakala, Riccardo Ravasio, Andrew Saxe, Pierfrancesco Urbani and Lenka Zdeborova for helpful discussions.

This work was partially supported by the grant from the Simons Foundation (#454935 Giulio Biroli, #454953 Matthieu Wyart). M.W. thanks the Swiss National Science Foundation for support under Grant No. 200021-165509. C.H. acknowledges support from the ERC SG Constamis, the NCCR SwissMAP, the Blavatnik Family Foundation and the Latsis Foundation. We thank the KITP and the National Science Foundation under Grant No. NSF PHY-1748958 for hosting us while this manuscript was written.

References

Appendix A Materials and methods

Here follow some details on the initialization and training dynamics used for the fully-connected networks. The weights of the network are initialized according to the random orthogonal scheme and all biases are initialized to zero. The network is not optimized using vanilla gradient descent, as learning was then too slow to acquire appropriate statistics. Instead we used ADAM with full batch and learning rate set to $\min(10^{-1}h^{-1.5},10^{-4})$ in order to have a smooth dynamics for all values of $h$. The exponent $-1.5$ has been empirically chosen so that the number of steps to converge is independent of $h$ . The excellent match between theory and predictions support that our conclusions are robust for a range of choices of learning dynamics.

For convolutional networks the parameters are initialized with the standard Xavier initialization and training minimizes a linear-hinge lossAs in Eq. (1) without the square, namely $C=\frac{1}{P}\sum_{\mu=1}^{P}\max(0,\Delta_{\mu})$. with stochastic gradient descent, with learning rate equal to $1/\mathsf{f}$ — $\mathsf{f}$ being the number of channels — and batch size $250$. Momentum, weight decay, or data augmentation were not used.

Appendix B Robustness of the boundaries distance δ​(x)𝛿𝑥\delta(x) estimate

Fig.9 shows that the linear estimate for the distance $\delta(x)$ between two decision boundaries, $\delta(x)=\delta f(x)/|\!|\nabla f(x)|\!|$, holds for ReLU nonlinear function and improves as $N\rightarrow\infty$.

Fig.10 illustrates the validity of the estimate of the typical distance between two boundary decisions presented in the main text $\delta\sim|\!|\delta f|\!|_{\mu}/|\!|\nabla f|\!|_{\mu}$, where $\mu$ corresponds to the uniform measure on all the test points.

Appendix C Central limit theorem of the NTK

In this section, we present a heuristic for the finite-size effects that are displayed by the NTK at initialization: informally, this is the Central Limit Theorem counterpart to the NTK asymptotic result, which can be viewed as a law of large numbers. A rigorous derivation, including the behavior during training, is beyond the scope of this paper.

where $a_{\alpha}(x)=\rho(b_{\alpha}(x))$ is the activity of neuron $\alpha$ when data $x$ is shown, while $b_{\alpha}(x)$ is its pre-activity and $v^{-}(\alpha)$ is the set of $h$ neurons in the layer preceding $\alpha$. The first bracket converges to a well-defined limit described by a so-called activation kernel, see . The second bracket has fluctuations of size comparable to its mean. The normalization is chosen such that each layer contributes a finite amount to the kernel, so that the mean is of order $1/h$. For a given hidden layer, the contributions of two neurons can be shown to have a covariance that is positive and decays as $1/h^{3}$, and thus does not affect the scaling expected from the Central Limit Theorem for uncorrelated variables. For a rectangular network (i.e. where all hidden layers with the same size), this suggests that fluctuations associated with the contribution of one layer to the kernel is of order $1/\sqrt{h}\sim N^{-\nicefrac{{1}}{{4}}}$.

Appendix D Fluctuations of output function for the mean square error loss

In this section, we discuss the fluctuations of the output function after training for the mean square error loss: $C(f)=\frac{1}{2P}\sum_{i}|y_{i}-f(x_{i})|^{2}$. We first investigate the variance of $f_{N,t}$ in the limit $N\to\infty$, then we explain the deviations due to finite size effects, at last we discuss the hing loss case.

Let us first study the variance of $f_{N,t}$ in the limit $N\to\infty$. In this limit, the function $f_{\infty,t=0}$ at initialization is a centered Gaussian process described by a covariance kernel $\Sigma$. During training, the dynamics of $f_{\infty,t}$ is described by a deterministic kernel (the large limit NTK) $\Theta_{\infty}$:

The first two terms are random, but they partly cancel each other, their sum is a centered Gaussian distribution with zero variance on the training set and a small variance for points close to the training set: the more training data points used, the lower the variance at initialization. The last term is equal to the kernel regression on $y$ with respect to the NTK, it is not random.

This shows that even in the infinite-width limit, $f_{\infty,t=\infty}$ has some variance which is due to the variance of $f_{\infty,t=0}$ at initialization. Yet, in the setup where the number of data points is large enough, the variance due to initialization almost vanishes during training and the scaling of the variance due to finite-size effects in $N$ will appear in the last term.

Finally, note that Eq.16 of this S.M. implies that $f_{\infty,t}(x)$ is smooth if both $\Theta_{\infty}(x,x^{\prime})$ and $f_{\infty,t=0}(x)$ are smooth functions of $x$ (this implication holds true for other choices of loss function). $\Theta_{\infty}(x,x^{\prime})$ is smooth if the activation function is smooth , and so does $f_{\infty,t=0}(x)$ which is then a Gaussian function of smooth covariance $\Sigma(x,x^{\prime})$. For Relu neurons, $\Theta_{\infty}(x,x^{\prime})$ displays a cusp at $x=x^{\prime}$ while $\Sigma(x,x^{\prime})$ is smooth, so $f_{\infty,t}(x)$ is smooth except on the training set, as supported by Figure 1 of this S.M.

D.2 Finite width

For a finite width $N$, the training is also described by the NTK $\Theta_{N,t}$ which is random at initialization and varies during training because it depends on the parameters. The integral formula becomes

However the noise at initialization is of order $N^{-\nicefrac{{1}}{{4}}}$, whereas the rate of change is only of order $\Omega(N^{-\nicefrac{{1}}{{2}}})$. We can therefore make the approximation

Here again the first two terms almost cancel each other, but the third term is random due to the randomness of the NTK which is of order $\mathcal{O}(N^{-\nicefrac{{1}}{{4}}})$, as needed.

D.3 Hinge Loss