Why Classical Bounds Do Not Explain Deep Networks

What uniform convergence bounds say about models with more parameters than training examples, and why they cannot account for how well such models predict. Proves that a class able to fit every labeling has Rademacher complexity 1 and uniform gaps of at least about a quarter, and that any bound that depends on the class and the input distribution but not on the labels must be at least one half when the class can fit random labels; reproduces the randomization test of Zhang et al. with a 33,793-parameter network on 1,000 digit images over 30 seeds; derives the exact risk of minimum-norm least squares in the Gaussian weak-features model of Belkin, Hsu and Xu, whose infinite peak at p = n is a double descent, checked by simulation and reproduced with random features on the digits; and states with their limits the Nagarajan–Kolter argument against uniform convergence and the margin, PAC-Bayes, compression and stability bounds proposed instead. Worked problems compute the exact risk curve by hand on a small case, the expected traces it rests on, and a norm-based bound for an interpolating model.

A neural network with one hidden layer of 512 units has 33,793 parameters. Trained on 1,000 images of handwritten digits to tell the digits 0 to 4 from 5 to 9, it fits every training label, and on 797 images it has not seen it is right 97.5% of the time. Replace the 1,000 training labels by coin flips and train the same network the same way: it again fits every training label, and on the unseen images it is right about half the time, as expected when what it learned carries no information about the digits. The network, its size, its training procedure and its training images are the same in both runs; only the labels differ. Can a bound that depends on the class of networks, and not on the labels, explain why the first network predicts well?

It cannot, and this article proves why. A uniform convergence bound controls the gap between true and empirical risk simultaneously for every hypothesis in a class, and the bounds of The VC Dimension and Rademacher Complexity are of that kind. They explain well why a small class, such as the thresholds on HbA1c of this unit, generalizes. For a class that can fit any labeling of the sample they say nothing, and modern networks are such classes. The article states precisely what fails and what has been established about the alternatives, and it keeps observed facts, proved theorems and conjectures apart.

First we prove what classical bounds say about a class that fits every labeling, and why a bound that ignores the labels must be vacuous. Then we reproduce a small version of the randomization test of Zhang et al. (2017). Next comes double descent: the test error of interpolating models falls again as they grow. We derive its exact form for minimum-norm least squares in a Gaussian model and see the same shape with random features on real images. Finally we state the argument of Nagarajan and Kolter (2019) that even uniform convergence restricted to what the training algorithm outputs can fail, and what margin, PAC-Bayes, compression and stability bounds achieve instead. The article assumes Rademacher Complexity, and it is the last article of the Statistical Learning Theory unit.

What the classical bounds predict

The VC bound of Rademacher Complexity (Corollary 1 there) adds $\sqrt{2d\ln(em/d)/m}$ to the training error, where $d$ is the VC dimension of the class and $m$ the number of training examples. For networks the VC dimension grows with the number of weights. Bartlett, Harvey, Liaw and Mehrabian (2019, abstract) prove that the VC dimension of networks with ReLU activations, $W$ weights and $L$ layers is $O(WL\log W)$, and give networks for which it is $\Omega(WL\log(W/L))$. Corollary 1 assumes $m \ge d$, and within that range the complexity term alone exceeds 1 once $d$ is more than about a fifth of $m$: with $r = d/m$ the term is $\sqrt{2r(1 - \ln r)}$, which is 1.09 at $r = \frac14$ and 1.41 at $r = 1$. A bound above 1 on a probability says nothing. For $d > m$ the corollary does not apply at all, and Proposition 1 below treats a class that shatters its sample.

Parameter counts can overstate what a class can do. The randomization test measures it directly, on the sample. Zhang et al. (2017, Theorem 1) show that a network with two layers, ReLU activations and $2n + d$ weights can represent any function on any $n$ points in $d$ dimensions. For a class of classifiers that realizes every labeling of the sample, the Rademacher machinery gives exact consequences.

Proposition 1 (a class that fits every labeling). Let $\mathcal{H}$ be a class of classifiers that, with probability 1 over samples $S \sim \mathcal{D}^m$, realizes every labeling of the inputs of $S$. Then $\mathfrak{R}_m(\tilde{\mathcal{H}}) = 1$; under the 0-1 loss

$$E_S\Big[\sup_{h \in \mathcal{H}}\big|L_{\mathcal{D}}(h) - L_S(h)\big|\Big] \ge \frac14 - \frac{1}{2\sqrt m};$$

and the bounds (3) of Rademacher Complexity are at least 1 for every hypothesis.

Proof. On a sample whose labelings are all realized, the set of value vectors of $\tilde{\mathcal{H}}$ is $\{-1, +1\}^m$, and its complexity is 1 by Lemma 1, part 3, of Rademacher Complexity. This holds with probability 1, so the expectation $\mathfrak{R}_m(\tilde{\mathcal{H}})$ is 1. By Lemma 2 there the 0-1 loss class has complexity $\frac12$, and its functions have $|L_{\mathcal{D}}| \le 1$, so Theorem 2 there gives the lower bound $\frac12 \cdot \frac12 - \frac{1}{2\sqrt m}$. In the bounds (3), the complexity term is $\mathfrak{R}_m(\tilde{\mathcal{H}}) = 1$ or $\hat{\mathfrak{R}}_{S_x}(\tilde{\mathcal{H}}) = 1$, and the empirical risk is non-negative. $\square$

At $m = 1{,}000$ the lower bound is 0.234. So uniform convergence over the whole class fails: some hypotheses in it have true and empirical risks far apart, in expectation. That is not yet a failure to explain the network that training actually returns, because the bound might be applied to a smaller class. The next result rules out every such smaller class that does not depend on the labels.

Proposition 2 (a bound that ignores the labels). Fix a distribution of the inputs on $\mathcal{X}$. Let $B$ be a number that depends only on a class $\mathcal{H}$, the sample size $m$, $\delta$ and that input distribution, such that for every distribution $\mathcal{D}$ on $\mathcal{X} \times \{0, 1\}$ with that input distribution, with probability at least $1 - \delta$ over $S \sim \mathcal{D}^m$, every $h \in \mathcal{H}$ satisfies $L_{\mathcal{D}}(h) \le L_S(h) + B$. Let $\mathcal{D}'$ have that input distribution and labels that are fair coin flips independent of the inputs. If with probability greater than $\delta$ under $\mathcal{D}'$ some $h \in \mathcal{H}$ has $L_S(h) = 0$, then $B \ge \frac12$.

Proof. Under $\mathcal{D}'$ the label is independent of the input and equally likely to be 0 or 1, so for every classifier $P(h(x) \ne y) = \frac12$, and $L_{\mathcal{D}'}(h) = \frac12$ for every $h$. The event on which the bound holds has probability at least $1 - \delta$, and the event on which some $h$ fits the sample has probability greater than $\delta$, so the two events intersect. On a sample in both, that $h$ gives $\frac12 \le 0 + B$. $\square$

The proposition is the formal content of the argument of Zhang et al. (2017, §2.2). Any bound with $B$ computed from the class and the input distribution, whether through its VC dimension, its expected Rademacher complexity $\mathfrak{R}_m(\tilde{\mathcal{H}})$, or any other property that does not look at the labels, gives the network trained on the true labels a guarantee no better than $0 + \frac12$, if the same class fits coin flips. A bound that can explain the true-label network must therefore depend on the labels, for example through properties of the trained network that differ between the two runs. Lemma 2 of Rademacher Complexity makes the point concrete: the empirical Rademacher complexity of a 0-1 loss class does not involve the labels at all. For a bound $B(S_x)$ computed from the sample's inputs, such as that empirical complexity, the same argument gives a weaker conclusion: $P(B(S_x) \ge \frac12)$ is at least the probability that some $h$ fits the coin flips, less $\delta$, which is positive (for a bound valid for every labeling distribution); and since the inputs have the same distribution under the true labels, the bound computed on a true-label sample is at least $\frac12$ with that same probability.

The randomization test

Zhang, Bengio, Hardt, Recht and Vinyals (2017) trained standard image classifiers on CIFAR-10, 50,000 training images in 10 classes, with the true labels and with labels replaced by random ones, and found that "Deep neural networks easily fit random labels" (§1.1). Their Table 1 reports, among others, a network with one hidden layer of 512 units and 1,209,866 parameters that reached training accuracy 100.0% and test accuracy 50.51% on the true labels without regularization, and training accuracy 99.34% with test accuracy 10.61% on random labels. A small version of Inception adapted to CIFAR-10, with 1,649,402 parameters, reached 100.0% training accuracy in both cases, with test accuracy 85.75% on the true labels (without data augmentation or weight decay) and 9.78% on random ones. They add that the networks fit random labels with unchanged learning-rate schedules, that the time to fit increased only by a small constant factor (§§1.1 and 2.1, and Figure 1b), and that with weight decay turned on Inception and the multilayer networks still fit random labels on CIFAR-10, while AlexNet with weight decay did not converge on random labels (§3). Their conclusion (§2.2) is the one Proposition 2 makes formal: the Rademacher complexity of these classes is close to its trivial maximum of 1, which gives no useful bound, and the same applies to the VC dimension. They also note that uniform stability, a property of the training algorithm, does not depend on the labels and cannot separate the two cases either.

A small randomization test

The digits data distributed with scikit-learn hold 1,797 images of $8 \times 8$ pixels with values 0 to 16, which we divide by 16. The dataset description (scikit-learn 1.6.1) calls them a copy of the test set of the UCI optical recognition of handwritten digits data, created by Alpaydin and Kaynak (1998). The task is to separate the digits 0 to 4 from 5 to 9, the binary version of a digit task that Dziugaite and Roy (2017) also used. For each of 30 seeds (16,004,001 to 16,004,030) the script draws 1,000 training images and keeps the other 797 for testing, and it draws 1,000 coin flips. It trains a network with one hidden layer of 512 ReLU units, 33,793 parameters, with the Adam optimizer at learning rate 0.001, batches of 100 and no weight decay (scikit-learn's MLPClassifier), one epoch at a time until every training label is fitted (at most 3,000 epochs; no run reached the cap). It does this twice, from the same initialization: once with the true labels and once with the coin flips.

Labels Runs fitting every training label Epochs to fit Test accuracy
True 30 of 30 65 (56.3 to 69.5) 0.975 (0.974 to 0.978)
Coin flips 30 of 30 275 (259 to 324.8) 0.500 (0.486 to 0.514)

Each cell is the median over the 30 seeds, with the interquartile range. The ratio of epochs, random to true, had median 4.5 (4.0 to 5.2). These are observations of one small experiment. They agree with what Zhang et al. report for far larger networks and images: the same network and procedure fit pure noise, at a few times the cost, and the test accuracy separates the two runs completely.

The coin flips are Rademacher variables in $\pm1$ form, so each run on coin flips is one Monte Carlo draw of the supremum in the definition of the Rademacher complexity, with the supremum taken over the networks this training procedure reaches. All 30 draws reached the maximum value 1. That is an estimate from 30 draws, not a proof that every sign vector would be fitted, but by Proposition 1 a class with complexity near 1 can have no useful uniform convergence bound, and by Proposition 2 no label-independent bound can give the true-label network a guarantee below one half.

Double descent

The classical picture of The Bias–Variance Tradeoff says that test error, as a function of a model's flexibility, falls while bias drops and then rises as variance takes over: a U. Interpolating models, which fit the training data exactly, sit at the far right of the U, where test error should be large. Belkin, Hsu, Ma and Mandal (2019) found instead that test error often falls a second time beyond the interpolation threshold, the smallest size at which a model can fit its training data exactly, and named the resulting curve double descent. In their Figure 2, minimum-norm least squares on random Fourier features of 10,000 MNIST images has a test-error peak at $N = 10^4$ features, the number of training images, and falls again beyond it, below the minimum of the classical U. They show the same shape for fully connected networks with one hidden layer on 4,000 MNIST images (their Figure 4), with the peak at the number of examples times the number of classes, and for random forests and boosting.

Their explanation (§2) is about norms. Beyond the threshold many interpolating solutions exist, and minimum-norm least squares picks the one of smallest norm. A larger model offers more interpolants and so a smaller smallest norm. At the threshold exactly one interpolant exists and its norm is largest. For general networks they write that the behavior of stochastic gradient descent "is not fully understood", while citing empirical and some theoretical evidence of a similar small-norm bias (§4). For networks the mechanism is a proposal, not a theorem.

Nakkiran, Kaplun, Bansal, Yang, Barak and Sutskever (2020) documented double descent in residual networks, convolutional networks and transformers, as a function of model width, of training time ("epoch-wise" double descent) and of the number of training samples, where more data can hurt near the peak. The effect was strongest with label noise in the training set; without it the peak often appeared as a plateau (their §2, "Remarks on Label Noise"). They defined the effective model complexity of a training procedure as the largest number of samples on which it reaches training error near zero, and stated as an informal hypothesis (their Hypothesis 1, which they call informal and without a principled choice of its tolerance) that double descent occurs as a function of this quantity. It is a conjecture supported by their experiments, not a theorem.

The library's note on Superposition, Memorization, and Double Descent describes a related observation in a toy network, where test loss rises and falls as the size of the dataset varies, at a transition between memorizing training examples and storing general features. The rest of this section derives double descent exactly in a model simple enough to solve.

An exact double descent

Belkin, Hsu and Xu (2020) analyzed least squares in a Gaussian model where the number of features used can be varied past the number of observations. The idea of the result: below the threshold the fit is ordinary least squares, whose variance is driven by the inverse of $X^{\mathsf T}X$, and that inverse has infinite mean as the matrix approaches singularity at $p = n$. Above the threshold the minimum-norm fit has variance driven by the inverse of $XX^{\mathsf T}$, which shrinks as $p$ grows, and a bias from the part of the coefficient vector the data cannot see.

The model. Inputs $x \in \mathbb{R}^D$ have independent standard normal coordinates, and $y = x^{\mathsf T}\beta + \varepsilon$ with $\varepsilon \sim N(0, \sigma^2)$ independent of $x$ (normal distributions are written with the variance second here, as in the formula). A fit uses only the first $p$ coordinates, the set $T$, with the rest $T^c$ omitted. Given $n$ observations with design $X_T$ ($n \times p$) and responses $\mathbf{y}$, the fit is $\hat\beta_T = X_T^{+}\mathbf{y}$, the shortest least-squares solution of The Singular Value Decomposition in Statistics (Theorem 5 there), and $\hat\beta_{T^c} = 0$. When $p > n$ it interpolates: $X_T\hat\beta_T = \mathbf{y}$. The risk is the expected squared error on a new observation, $E[(y - x^{\mathsf T}\hat\beta)^2]$.

Two lemmas about Gaussian matrices carry the proof.

Lemma 1 (the inverse of a Wishart matrix). Let $X$ be $n \times p$ with independent standard normal entries and $W = X^{\mathsf T}X$. If $n \ge p + 2$ then $E[W^{-1}] = I_p/(n - p - 1)$. If $n \in \{p, p + 1\}$, every diagonal entry of $W^{-1}$ has infinite expectation.

Proof. A matrix with independent continuous entries has full rank with probability 1: rank deficiency of an $n \times p$ matrix with $n \ge p$ makes the determinant of its top $p \times p$ block zero, and that determinant is a nonzero polynomial in the entries. The zero set of a nonzero polynomial has probability 0 under any distribution with a density, by induction on the number of variables: for almost every value of the other variables, the polynomial in the last variable is not identically zero and so has finitely many roots. So $W$ is invertible with probability 1.

Write $x_1$ for the first column of $X$ and $X_{-1}$ for the others, and partition $W$ as $\begin{pmatrix} a & b^{\mathsf T} \\ b & C\end{pmatrix}$ with $a = x_1^{\mathsf T}x_1$, $b = X_{-1}^{\mathsf T}x_1$ and $C = X_{-1}^{\mathsf T}X_{-1}$. Let $s = a - b^{\mathsf T}C^{-1}b$. The vector $\mathbf{u} = s^{-1}(1, -C^{-1}b)$ satisfies $W\mathbf{u} = s^{-1}(a - b^{\mathsf T}C^{-1}b,\ b - CC^{-1}b) = (1, 0)$, so it is the first column of $W^{-1}$, and $(W^{-1})_{11} = 1/s$. Now $s = x_1^{\mathsf T}(I - P)x_1 = \lVert(I - P)x_1\rVert^2$, where $P = X_{-1}C^{-1}X_{-1}^{\mathsf T}$ is the projection onto the column space of $X_{-1}$ (The Geometry of Least Squares, Theorem 2) and $I - P$ is the projection onto its orthogonal complement, of dimension $n - (p - 1)$. Given $X_{-1}$, the column $x_1$ is still a vector of independent standard normal variables, so by Sampling Distributions from the Normal (Theorem 2) $\lVert(I - P)x_1\rVert^2$ has the chi-squared distribution with $k = n - p + 1$ degrees of freedom. That conditional distribution does not depend on $X_{-1}$, so it is also the unconditional one.

The chi-squared density with $k$ degrees of freedom is $x^{k/2 - 1}e^{-x/2}/(2^{k/2}\Gamma(k/2))$ for $x > 0$ (Chi-Squared and t Distributions). Hence

$$E\Big[\frac1{\chi^2_k}\Big] = \frac{\int_0^\infty x^{k/2 - 2}e^{-x/2}\,dx}{2^{k/2}\Gamma(k/2)} = \frac{2^{k/2 - 1}\Gamma(k/2 - 1)}{2^{k/2}\Gamma(k/2)} = \frac{1}{2(k/2 - 1)} = \frac{1}{k - 2}$$

for $k \ge 3$, using $\Gamma(t + 1) = t\Gamma(t)$. For $k \le 2$ the exponent $k/2 - 2$ is at most $-1$ and the integral diverges at 0. With $k = n - p + 1$, the condition $k \ge 3$ is $n \ge p + 2$, and then $E[(W^{-1})_{11}] = 1/(n - p - 1)$; for $n \in \{p, p + 1\}$ it is infinite. Every column plays the same part, so the same holds for each diagonal entry.

For the off-diagonal entries, let $Q$ be the diagonal matrix that changes the sign of coordinate $j$. Then $XQ$ has the same distribution as $X$, and $(XQ)^{\mathsf T}XQ = QWQ$ has inverse $QW^{-1}Q$, whose $(i, j)$ entry for $i \ne j$ is $-(W^{-1})_{ij}$. So $(W^{-1})_{ij}$ and $-(W^{-1})_{ij}$ have the same distribution, and the mean is 0. It exists, because $W^{-1}$ is positive definite and so $|(W^{-1})_{ij}| \le ((W^{-1})_{ii} + (W^{-1})_{jj})/2$. $\square$

Lemma 2 (projection onto a random row space). Let $X$ be $n \times p$ with independent standard normal entries and $p \ge n$, and let $P$ be the projection onto the row space of $X$, the span of its rows in $\mathbb{R}^p$. Then $E[P] = (n/p)I_p$.

Proof. For any orthogonal $p \times p$ matrix $Q$, the matrix $XQ$ has independent standard normal entries: each row $x_i^{\mathsf T}Q$ is a rotation of a standard normal vector, which is again standard normal by Sampling Distributions from the Normal (Theorem 1), and the rows stay independent. The rows of $XQ$ are $Q^{\mathsf T}x_i$, which span $Q^{\mathsf T}$ times the row space of $X$, so the projection onto that span is $Q^{\mathsf T}PQ$. Hence $M = E[P]$ satisfies $M = Q^{\mathsf T}MQ$ for every orthogonal $Q$. With $Q$ the sign change of one coordinate, as in Lemma 1, the off-diagonal entries of $M$ are 0. With $Q$ the permutation exchanging two coordinates, the diagonal entries are equal. So $M = cI_p$. The trace of a projection is its rank, here $n$ with probability 1, so $pc = n$. $\square$

Theorem 1 (the exact risk; Belkin, Hsu and Xu, 2020, Theorem 1). In the model above, with $s^2 = \lVert\beta_{T^c}\rVert^2 + \sigma^2$,

$$E\big[(y - x^{\mathsf T}\hat\beta)^2\big] = \begin{cases} s^2\Big(1 + \dfrac{p}{n - p - 1}\Big) & \text{if } p \le n - 2, \\[2ex] \infty & \text{if } n - 1 \le p \le n + 1, \\[1ex] \lVert\beta_T\rVert^2\Big(1 - \dfrac np\Big) + s^2\Big(1 + \dfrac{n}{p - n - 1}\Big) & \text{if } p \ge n + 2. \end{cases}$$

Proof. For a new observation independent of the training data, $y - x^{\mathsf T}\hat\beta = x^{\mathsf T}(\beta - \hat\beta) + \varepsilon$. Its coordinates are independent with variance 1 and $\varepsilon$ is independent of everything, so the conditional expectation given the training data is $\sigma^2 + \lVert\beta - \hat\beta\rVert^2 = \sigma^2 + \lVert\beta_{T^c}\rVert^2 + \lVert\beta_T - \hat\beta_T\rVert^2$, since $\hat\beta_{T^c} = 0$. The first two terms are $s^2$. In the training data, write $\mathbf{y} = X_T\beta_T + \boldsymbol\eta$ with $\boldsymbol\eta = X_{T^c}\beta_{T^c} + \boldsymbol\varepsilon$. Each entry of $\boldsymbol\eta$ is a fixed combination of independent normal variables, with variance $s^2$; the entries are independent of each other and of $X_T$, because they involve only the other columns and the noise. Write $X$ for $X_T$.

If $p \le n$, then $X$ has full column rank with probability 1, $\hat\beta_T = (X^{\mathsf T}X)^{-1}X^{\mathsf T}\mathbf{y} = \beta_T + (X^{\mathsf T}X)^{-1}X^{\mathsf T}\boldsymbol\eta$, and

$$E\lVert\hat\beta_T - \beta_T\rVert^2 = E\big[\boldsymbol\eta^{\mathsf T}X(X^{\mathsf T}X)^{-2}X^{\mathsf T}\boldsymbol\eta\big] = s^2E\,\mathrm{tr}\big(X(X^{\mathsf T}X)^{-2}X^{\mathsf T}\big) = s^2E\,\mathrm{tr}\big((X^{\mathsf T}X)^{-1}\big),$$

taking the expectation over $\boldsymbol\eta$ first, with $E[\boldsymbol\eta\boldsymbol\eta^{\mathsf T}] = s^2I_n$, and using $\mathrm{tr}(AB) = \mathrm{tr}(BA)$. By Lemma 1 this is $s^2p/(n - p - 1)$ for $p \le n - 2$ and infinite for $p \in \{n - 1, n\}$.

If $p \ge n$, then $X$ has full row rank with probability 1, and $X^{+} = X^{\mathsf T}(XX^{\mathsf T})^{-1}$, so $\hat\beta_T = P\beta_T + X^{\mathsf T}(XX^{\mathsf T})^{-1}\boldsymbol\eta$ with $P = X^{\mathsf T}(XX^{\mathsf T})^{-1}X$ the projection onto the row space. Then $\beta_T - \hat\beta_T = (I - P)\beta_T - X^{\mathsf T}(XX^{\mathsf T})^{-1}\boldsymbol\eta$. The first vector is orthogonal to the row space and the second lies in it, so by Pythagoras

$$\lVert\beta_T - \hat\beta_T\rVert^2 = \beta_T^{\mathsf T}(I - P)\beta_T + \boldsymbol\eta^{\mathsf T}(XX^{\mathsf T})^{-1}\boldsymbol\eta.$$

By Lemma 2 the first term has expectation $(1 - n/p)\lVert\beta_T\rVert^2$. The second has expectation $s^2E\,\mathrm{tr}((XX^{\mathsf T})^{-1})$. The matrix $XX^{\mathsf T}$ is $X^{\mathsf T}$ transposed times itself, with $X^{\mathsf T}$ a $p \times n$ matrix of independent standard normal entries, so Lemma 1 with the roles of $n$ and $p$ exchanged gives $n/(p - n - 1)$ for $p \ge n + 2$ and infinity for $p \in \{n, n + 1\}$. Adding $s^2$ gives the stated formula. $\square$

Belkin, Hsu and Xu (2020, §2.2) prove the theorem by the same route, and they credit the case $p \le n$ to Breiman and Freedman (1983), which was not consulted here. As $n$ and $p$ grow with $p/n \to \gamma$, the variance factors $p/(n - p - 1)$ and $n/(p - n - 1)$ tend to $\gamma/(1 - \gamma)$ and $1/(\gamma - 1)$, the limits that Hastie, Montanari, Rosset and Tibshirani (2022, Theorem 1 and eq. 8) prove for isotropic features under much weaker assumptions than normality.

Example (the setting of Belkin, Hsu and Xu's Figure 1). Take $D = 100$ features, $n = 40$ observations, $\beta_j = 1/10$ for every $j$ (so $\lVert\beta\rVert^2 = 1$ and $\lVert\beta_T\rVert^2 = p/100$) and $\sigma^2 = 1/25$. Predicting 0 has risk $1 + 1/25 = 1.04$. The formula gives risk 1.264 at $p = 10$ and 3.207 at $p = 30$, rising to 25.74 at $p = 38$; it is infinite from 39 to 41; then it falls from 25.44 at $p = 42$ to 1.566 at $p = 60$ and 0.667 at $p = 100$. Among $p \le 38$ the smallest risk is that of $p = 0$: in this model no fit below the threshold beats predicting 0, while the interpolating fit with all 100 features beats it by more than a third. Belkin, Hsu and Xu (2020, after Corollary 1) note that the risk is smallest at $p = D$ whenever the signal-to-noise ratio $\lVert\beta\rVert^2/\sigma^2$ exceeds $D/(D - n - 1)$, here 1.69; the ratio here is 25.

An exact double descent, checked

The script simulates the model for 30 seeds (16,002,001 to 16,002,030). For each seed and each $p$ in a grid it draws 200 training sets, computes the minimum-norm fit, and averages the exact conditional risk $\sigma^2 + \lVert\beta - \hat\beta\rVert^2$; the 30 averages are summarized by their median and interquartile range.

$p$ Exact risk Simulated (median of 30 means)
10 1.264 1.262 (1.257 to 1.270)
30 3.207 3.232 (3.165 to 3.313)
60 1.566 1.573 (1.554 to 1.593)
100 0.667 0.667 (0.665 to 0.669)
Prediction risk of minimum-norm least squares with n = 40 observations against the number of features used, on a logarithmic scale: the exact formula of Theorem 1 (line) and the simulation (points, median of 30 seed means with quartile bars). Notice that the risk rises without bound toward p = 40 from both sides, and that past the peak it falls below the risk of predicting 0 (dashed), which no fit below the peak achieves.
Prediction risk of minimum-norm least squares with n = 40 observations against the number of features used, on a logarithmic scale: the exact formula of Theorem 1 (line) and the simulation (points, median of 30 seed means with quartile bars). Notice that the risk rises without bound toward p = 40 from both sides, and that past the peak it falls below the risk of predicting 0 (dashed), which no fit below the peak achieves.

At the four values of the table the exact risk lies within the interquartile range of the simulated means. At $p = 42$, next to the threshold, it does not. By Lemma 1 the variance term involves the reciprocal of a chi-squared variable with few degrees of freedom, whose own variance is infinite for 4 or fewer degrees of freedom; at $p = 42$ it has 3. A mean of 200 such draws is then more often below its expectation than above, a few rare large draws carrying much of the expectation, and here the median of the 30 means falls short of the formula: 22.40 (20.28 to 24.87) against the exact 25.44. At $p = 38$, with the same 3 degrees of freedom, the scatter is as large but the median happens to lie above the formula: 25.95 (21.95 to 31.39) against 25.74. The downward pull of heavy tails is a tendency, not a rule, over 30 seeds.

Example (the "more parameters means more overfitting" reading). "Past the threshold the model has more parameters than observations, so it must be overfitting more and more." In this model the opposite holds. Interpolation is exact for every $p \ge 41$, and the variance term $s^2 n/(p - n - 1)$ falls as $p$ grows, because the shortest interpolant spreads its coefficients over more directions. Hastie et al. (2022, Corollary 1) show the same for the norm of the estimate: it diverges at the threshold and decreases beyond it. What grows with $p$ is the bias term $(1 - n/p)\lVert\beta_T\rVert^2$, the part of the signal in directions the 40 observations do not span. Whether the second descent goes below the first is a property of the setting. Hastie et al. (2022, introduction, summary of results) find that in a well-specified isotropic model the global minimum lies below the threshold, that a misspecified model can put it above, and that an optimally tuned ridge penalty does at least as well as minimum-norm interpolation everywhere in their isotropic settings, which is the remark The Bias–Variance Tradeoff reports from James et al. (2021).

The same curve with random features

Does the shape survive on real data, with features that are not Gaussian? The script fits minimum-norm least squares to one-hot targets of the 10 digit classes on $N$ random Fourier features $\phi_j(x) = \sqrt2\cos(\langle w_j, x\rangle + b_j)$, with $w_j$ normal with standard deviation 0.2 in each coordinate and $b_j$ uniform on $[0, 2\pi]$, as in the random Fourier features of Belkin et al. (2019), here in real form. There are 300 training images and 1,497 test images; 30 seeds (16,003,001 to 16,003,030) draw the split and the features. The prediction is the class with the largest output.

Test squared loss (left, logarithmic scale) and test error (right) of minimum-norm least squares on N random Fourier features of the digits, with 300 training images: median of 30 seeds with the band from the first to the third quartile. Notice the peak at N = 300, where the fit first interpolates, and that both curves end, at 4,000 features, below their best value before the peak.
Test squared loss (left, logarithmic scale) and test error (right) of minimum-norm least squares on N random Fourier features of the digits, with 300 training images: median of 30 seeds with the band from the first to the third quartile. Notice the peak at N = 300, where the fit first interpolates, and that both curves end, at 4,000 features, below their best value before the peak.

The best number of features below the threshold, by test squared loss, was 100, with test squared loss 0.332 (0.326 to 0.341) and error 0.078 (0.070 to 0.084). At $N = 300$, the first size at which the training loss was zero to rounding, the test squared loss had median 105 (47 to 1,099) and the error 0.803 (0.769 to 0.863), little better than the error of about 0.9 from guessing among 10 classes. That median loss is the largest on the grid of sizes, against 3.48 at $N = 290$ and 3.63 at $N = 310$. At $N$ = 4,000 the squared loss was 0.175 (0.170 to 0.182) and the error 0.033 (0.031 to 0.037), both lower than the median at any size below the threshold. The norm of the coefficient matrix had median 208 (136 to 659) at $N = 300$ and 1.49 (1.46 to 1.53) at $N$ = 4,000, the pattern Belkin et al. (2019, Figure 2) report for the norm on MNIST. These are observations on one dataset and one feature distribution.

What does this mean for bounds? For a linear model on $N$ features the VC dimension of the linear classifiers grows with $N$, so the VC bound grows steadily through the threshold and beyond, and it describes neither the peak nor the second descent. A norm-based bound could follow the second descent, since the norm falls past the threshold. Whether it can do so with useful numbers is the next question.

Norm-based bounds

The margin bounds of Rademacher Complexity (Corollaries 2 and 3) contain no parameter count, only the norm of the weights, the size of the inputs and the margin. For random Fourier features $\lVert\phi(x)\rVert^2 = 2\sum_j\cos^2(\cdot) \le 2N$ for every input, so $R = \sqrt{2N}$. A minimum-norm interpolator of $\pm1$ labels has every training margin exactly 1, so its ramp loss at $\gamma = 1$ is 0, and Corollary 3 there, with the radius chosen after the fit, bounds its error by $2 \cdot 2^k\sqrt{2N}/\sqrt m + \sqrt{\ln(k(k + 1)/\delta)/(2m)}$, where $2^k$ is the first power of 2 at or above the norm.

On the binary digit task with $m$ = 1,000 training images and $N$ = 4,000 features (30 seeds, 16,004,501 to 16,004,530, each drawing a split, the features and the coin flips), the script fits the true labels and coin flips by minimum-norm least squares and evaluates the bound at $\delta = 0.05$. The random features are drawn independently of the images, so the bound can be applied conditionally on them. The bound is a statement about an i.i.d. sample from a distribution; the experiment shows what its value would be for such samples. The training images are drawn without replacement from the 1,797, so the test accuracy on the other 797 is an estimate on held-out images, not $L_{\mathcal{D}}$ for such a distribution. Nothing below depends on the difference, since both bounds exceed 1.

Labels Norm of the interpolator Bound (Corollary 3) Test accuracy
True 5.3 (5.2 to 5.5) 45 (45 to 45) 0.984 (0.981 to 0.986)
Coin flips 26.1 (25.7 to 26.5) 181 (181 to 181) 0.501 (0.493 to 0.518)

The norm sees the difference that the class cannot: the coin-flip interpolator needs about five times the norm (median ratio 4.9), and its bound is four times larger, because the norms round up to the radii $2^3$ and $2^5$. Both bounds are vacuous, by factors of 45 and 181. This is the pattern reported for real networks. Bartlett, Foster and Telgarsky (2017) proved a margin bound for networks of $L$ layers with weight matrices $A_1, \ldots, A_L$ that scales with the spectral complexity, the product of the spectral norms $\lVert A_i\rVert_\sigma$ times a correction factor in the matrices' $(2,1)$ norms relative to reference matrices, divided by the margin, with the number of parameters entering only through logarithms (their Theorem 1.1). For AlexNet trained by stochastic gradient descent on CIFAR-10 and MNIST, with true and random labels, they found that the bound, the Lipschitz constants and the excess risk moved together, and that margins normalized by the spectral complexity separated true from random labels (their abstract and Figures 1 to 3). Their paper uses the bound to compare distributions of normalized margins, not as a numerical guarantee. Nagarajan and Kolter (2019, §2) evaluated this bound and a similar norm-based one on fully connected networks of depth 5 and width 1,024 trained on MNIST by stochastic gradient descent with batch size 1, and found that, while the test error fell with the training set size $m$ roughly as $m^{-0.43}$, both bounds grew roughly as $m^{0.68}$, because the distance of the weights from their initialization and the product of spectral norms grew with $m$. They tie the growth of the bounds to small batch sizes (§§1 and 2); at batch size 32 the bounds decreased with $m$, but only as about $m^{-0.23}$, against $m^{-0.44}$ for the test error (their Appendix B.1). Arora, Ge, Neyshabur and Zhang (2018, §6.3) report that on a VGG-19 network trained on CIFAR-10 the earlier norm-based bounds they compared were orders of magnitude worse than a naive count of parameters.

Can uniform convergence over what the algorithm outputs work?

Proposition 2 rules out bounds computed from the class alone. A natural repair is to apply uniform convergence to a smaller class: only the hypotheses the training algorithm actually outputs on samples from the distribution at hand. Nagarajan and Kolter (2019) showed that even this can fail.

They define, for a learning algorithm and a distribution, the tightest algorithm-dependent uniform convergence bound $\epsilon_{\text{unif-alg}}(m, \delta)$ (their Definition 3.3): choose any set $\mathcal{S}_\delta$ of samples with probability at least $1 - \delta$, let $\mathcal{H}_\delta$ be the set of hypotheses the algorithm outputs on those samples, and take the smallest possible value of $\sup_{S \in \mathcal{S}_\delta}\sup_{h \in \mathcal{H}_\delta}|L_{\mathcal{D}}(h) - L_S(h)|$. Every two-sided uniform convergence bound applied to the algorithm's outputs is at least this large. In a high-dimensional linear classifier trained by one step of gradient descent, with $K$ informative dimensions and $D$ noise dimensions, $D$ much larger than $m$, their Theorem 3.1 proves that the generalization error is at most a small $\epsilon$ while $\epsilon_{\text{unif-alg}}$ is at least $1 - \epsilon$. The mechanism: the learned weights on the noise dimensions are a sum of the training points' noise, which hardly affects predictions on new points but is aligned with the training points themselves. Flipping the sign of the noise coordinates of the training sample gives a "bad" sample with the same distribution, on which the learned classifier errs everywhere. Uniform convergence must hold on almost all samples at once, and these bad samples cannot all be excluded. For a two-layer ReLU network of width 100,000 trained on the "adversarial spheres" distribution (two concentric spheres in 1,000 dimensions with radii 1 and 1.1), they showed empirically that the analogous bad sample is completely misclassified while the test error falls with $m$ (their §3.2 and Figure 2).

The authors state the limits of the result. It concerns two-sided bounds, which are what existing techniques give, and they also argue (their Remark 3.1 and Appendix J) that the deterministic PAC-Bayes bounds obtained by the two standard ways of derandomizing a PAC-Bayes bound are lower-bounded by the same two-sided quantity. Bounds on a stochastic network, such as that of Dziugaite and Roy below, are not covered by that argument. They do not rule out uniform convergence when gradient descent is run with explicit regularization such as weight decay (§1.1). The proof is for their linear example and an infinite-width network in their appendix; the ReLU network example is empirical. What is established is that two-sided uniform convergence, even restricted to the hypotheses the algorithm outputs on almost all samples, can be provably unable to explain generalization in settings that share features with deep learning; whether that is the situation for practical networks is, in their title's word, a question of what it "may" be unable to do.

What has been tried instead

Each approach below gives some guarantee or measurement that a pure class-based bound cannot. None, as of the papers read for this article, gives a numerically tight guarantee for the deterministic network that training returns.

  • Margin and norm bounds (Bartlett, Foster and Telgarsky, 2017). Does: depends on the trained weights and the data, so it separates true from random labels, and it has no explicit dependence on the number of parameters. Does not: give non-vacuous numbers for practical networks, and in the setting of Nagarajan and Kolter (2019, §2) it grew with the training set size while the error fell.
  • PAC-Bayes bounds (Dziugaite and Roy, 2017). A PAC-Bayes bound controls the expected error of a random classifier drawn from a distribution $Q$ over weights, in terms of its empirical error and the Kullback–Leibler divergence of $Q$ from a prior $P$ chosen before seeing the data. Dziugaite and Roy optimized such a bound, starting from networks trained by stochastic gradient descent on a binary version of MNIST (digits 0 to 4 against 5 to 9, 55,000 training images), with a Gaussian $Q$ centered near the trained weights and a prior centered at the random initialization. Does: their Table 1 reports bounds of 0.161 to 0.223 on the test error of the stochastic networks, holding with probability 0.965, for networks with about 326,000 to 2.4 million parameters; for one network trained on random labels the bound was 1.352, vacuous as it should be. These were the first non-vacuous bounds for networks of this size, in their words "to our knowledge" (§1). Does not: apply to the trained deterministic network, whose test error was 0.013 to 0.018 against the bound's 0.16 or more; the bound is about a randomized network, found by optimizing the bound itself.
  • Compression (Arora, Ge, Neyshabur and Zhang, 2018). Does: if the trained network can be replaced by one with $q$ parameters, each taking at most $r$ values, whose outputs on the training set are within a margin of the original's, then the compressed network has error at most the original's margin error plus $O(\sqrt{q\log r/m})$ (their Theorem 2.1); they compress via noise-stability properties they verify on trained networks, and report bounds much smaller than earlier norm-based ones (§6.3). Does not: bound the original network: their Remark (1) after Theorem 2.1 states that "The framework proves the generalization not of f but of its compression". During training their bound kept improving while the test error did, but "not to the same level" (§6.2).
  • Algorithmic stability (Hardt, Recht and Singer, 2016). An algorithm is $\epsilon$-uniformly stable if replacing one training example changes the expected loss at every point by at most $\epsilon$, and then its expected generalization gap is at most $\epsilon$ (their Theorem 2.2). Does: for convex, smooth, Lipschitz losses, stochastic gradient descent for $T$ steps is stable with $\epsilon \le (2L^2/n)\sum_t\alpha_t$ (Theorem 3.8, with step sizes $\alpha_t$ and $n$ examples), and for non-convex smooth losses with decreasing steps they give a bound growing like $T^{1 - 1/(\beta c + 1)}/n$ (Theorem 3.12), which favors short training. Does not: depend on the labels, which Zhang et al. (2017, §1.2) point out means it cannot separate true from random labels; and networks trained for many epochs, as in the randomization test, fall outside the regime where the bound is small.

Two other lines of work analyze the interpolating predictor directly rather than through uniform convergence. Exact risk calculations for minimum-norm least squares and random features, such as Theorem 1 here and Hastie et al. (2022), describe double descent in tractable models. The influence-function study summarized in Studying Large Language Model Generalization with Influence Functions uses "generalization" in a different sense, how a large model combines what it learned beyond copying training sequences, and measures it by attributing outputs to training data, not by bounding a risk gap.

What is established and what is not

Established by proof (on this page or in the cited papers): a class that fits every labeling of its samples has Rademacher complexity 1, an expected uniform gap of at least $\frac14 - 1/(2\sqrt m)$, and no useful Rademacher or VC bound (Proposition 1); a bound that depends on the class and the input distribution but not on the labels must be at least $\frac12$ when the class fits random labels with probability greater than $\delta$ (Proposition 2); in the Gaussian weak-features model the risk of minimum-norm least squares is infinite at the interpolation threshold and falls beyond it, with an exact formula (Theorem 1, Belkin et al., 2020); in their linear example, the tightest algorithm-dependent two-sided uniform convergence bound is nearly vacuous while the generalization error is small (Nagarajan and Kolter, 2019, Theorem 3.1); the PAC-Bayes, compression and stability theorems hold under their stated conditions.

Established by experiment (reported, not proved): standard networks fit random labels at a few times the cost of fitting true ones (Zhang et al., 2017, and this article's small test); double descent appears for random features, networks, trees and boosting (Belkin et al., 2019) and as a function of width, training time and sample size in modern architectures, most strongly with label noise (Nakkiran et al., 2020); norm-based bounds separate true from random labels but are numerically vacuous, and in one setting grew with the sample size (Bartlett, Foster and Telgarsky, 2017; Nagarajan and Kolter, 2019); non-vacuous PAC-Bayes bounds exist for stochastic networks (Dziugaite and Roy, 2017).

Conjectured or open: that stochastic gradient descent in deep networks has a small-norm or similar implicit bias that explains generalization (Belkin et al., 2019, §4, call it not fully understood); that double descent is governed by effective model complexity (Nakkiran et al., 2020, Hypothesis 1, stated informally); whether any form of uniform convergence can explain generalization of practical networks (Nagarajan and Kolter, 2019, cast doubt on it without settling it for practical networks).

What is proved here, what is cited, and what the experiments show

Proved on this page: the consequences for a class that fits every labeling (Proposition 1, from the results of Rademacher Complexity); the lower bound $\frac12$ on any label-independent bound when the class fits random labels (Proposition 2); the mean of the inverse of a Wishart matrix and its divergence, from the chi-squared distribution (Lemma 1); the mean of the projection onto a random row space (Lemma 2); the exact risk of minimum-norm least squares in the Gaussian weak-features model (Theorem 1, a theorem of Belkin, Hsu and Xu, 2020, proved here by their route).

Cited: the VC dimension of ReLU networks (Bartlett, Harvey, Liaw and Mehrabian, 2019, abstract); finite-sample expressivity (Zhang et al., 2017, Theorem 1); the asymptotic risk and norm of minimum-norm least squares and the comparison with ridge (Hastie et al., 2022); the theorems of Nagarajan and Kolter (2019), Bartlett, Foster and Telgarsky (2017), Dziugaite and Roy (2017), Arora et al. (2018) and Hardt et al. (2016), at the strength stated with each; the experiments of Zhang et al. (2017), Belkin et al. (2019) and Nakkiran et al. (2020). Each was read in its arXiv version; section, table and figure numbers refer to those versions.

What the experiments show: on 1,000 digit images, a 33,793-parameter network fitted true labels and coin flips in all 30 runs, with test accuracy 0.975 against 0.500 and about 4.5 times as many epochs for the coin flips; the exact risk curve of Theorem 1 matched simulation; minimum-norm least squares on random features of the digits peaked at 300 features, the number of training images, and at 4,000 features beat every model below the threshold; the norm of an interpolator was five times larger for coin flips than for true labels, and the norm-based bound was vacuous for both. These are observations on one small dataset.

Worked problems

The problems use small exact cases and this article's experiments; this unit has no course assignments. The script tools/experiments/statistics/uniform-convergence.py checks every number.

Problem 1 (an exact risk curve by hand). In the model of Theorem 1, let $D = 20$, $n = 10$, $\beta_j^2 = 1/20$ for every $j$, and $\sigma^2 = 0$. Compute the risk for $p$ = 0, 5, 8, 12, 15 and 20, and say which $p$ is best.

Solution. Here $\lVert\beta_T\rVert^2 = p/20$ and $s^2 = 1 - p/20$. At $p = 0$ the risk is $s^2 = 1$. At $p = 5$: $s^2 = 3/4$ and the risk is $\frac34(1 + \frac54) = 27/16 = 1.6875$. At $p = 8$: $s^2 = 3/5$ and the risk is $\frac35(1 + \frac81) = 5.4$. The values $p$ = 9, 10 and 11 have infinite risk. At $p = 12$: $\lVert\beta_T\rVert^2 = 3/5$, $s^2 = 2/5$, and the risk is $\frac35(1 - \frac{10}{12}) + \frac25(1 + \frac{10}{1}) = \frac1{10} + \frac{22}5 = 9/2 = 4.5$. At $p = 15$: $\frac34(1 - \frac{10}{15}) + \frac14(1 + \frac{10}{4}) = \frac14 + \frac78 = 9/8 = 1.125$. At $p = 20$ the omitted part is empty and there is no noise, so $s^2 = 0$ and the risk is $1 \cdot (1 - \frac{10}{20}) = 0.5$. The best is $p = 20$, all features, an interpolating fit; every $p$ from 1 to 8 is worse than predicting 0. A simulation with 50,000 training sets (seed 16,005,001) gives 1.69 at $p = 5$ and 1.12 at $p = 15$.

Problem 2 (the traces behind the variance). For a $10 \times 3$ matrix $X$ of independent standard normal entries, find $E\,\mathrm{tr}((X^{\mathsf T}X)^{-1})$. For a $10 \times 20$ matrix, find $E\,\mathrm{tr}((XX^{\mathsf T})^{-1})$.

Solution. By Lemma 1 with $n = 10$ and $p = 3$, $E[(X^{\mathsf T}X)^{-1}] = I_3/(10 - 3 - 1)$, whose trace is $3/6 = 0.50$. For the second, $XX^{\mathsf T}$ is $Z^{\mathsf T}Z$ with $Z = X^{\mathsf T}$ a $20 \times 10$ matrix, so Lemma 1 with 20 rows and 10 columns gives $E[(XX^{\mathsf T})^{-1}] = I_{10}/(20 - 10 - 1)$, with trace $10/9 = 1.111$. Multiplied by $s^2$, these are the variance terms of Theorem 1 at $(n, p) = (10, 3)$ and $(10, 20)$.

Problem 3 (how far apart can the gaps be?). A class of classifiers realizes every labeling of almost every sample of 1,000 points. What does Theorem 2 of Rademacher Complexity say about the expected largest gap $|L_{\mathcal{D}}(h) - L_S(h)|$, and what do the bounds (3) there say?

Solution. By Proposition 1 the expected largest gap is at least $\frac14 - \frac{1}{2\sqrt{1000}} = 0.25 - 0.0158 = 0.234$. The bounds (3) add the complexity, 1, to a non-negative training error, so they are at least 1 for every hypothesis and say nothing. The lower bound concerns the whole class: it says some hypotheses have large gaps, not that the one returned by training does. Proposition 2 is the statement about the returned network.

Problem 4 (a norm-based bound for an interpolator). A minimum-norm interpolator on $N$ = 4,000 random Fourier features fits $m$ = 1,000 true labels with norm 5.3, the median in the table above. Evaluate Corollary 3 of Rademacher Complexity at $\gamma = 1$ and $\delta = 0.05$. If the norm stayed at 5.3, how many training images would make the complexity term 0.1?

Solution. The first power of 2 at or above 5.3 is $2^3 = 8$, so $k = 3$. The ramp loss is 0, since every margin is exactly 1. The complexity term is $2 \cdot 8 \cdot \sqrt{2 \cdot 4000}/\sqrt{1000} = 16\sqrt8 = 45.25$, and the confidence term is $\sqrt{\ln(3 \cdot 4/0.05)/2000} = \sqrt{\ln 240/2000} = 0.052$, for a bound of 45.31 on a probability. The complexity term falls to 0.1 when $\sqrt m = 16\sqrt{8000}/0.1$, at $m$ = 204,800,000, more than a hundred thousand times the 1,797 images that exist. The norm would not stay fixed as $m$ grows: Nagarajan and Kolter (2019, §2) found norms of trained networks growing with $m$.

Summary

Result Statement
Fitting every labeling complexity 1; expected largest gap $\ge \frac14 - \frac1{2\sqrt m}$; Rademacher and VC bounds vacuous (Proposition 1)
Label-independent bounds at least $\frac12$ if the class fits random labels (Proposition 2)
Randomization test 33,793 parameters, 1,000 images: true labels and coin flips both fitted in 30 of 30 runs; test accuracy 0.975 against 0.500
Wishart inverse $E[(X^{\mathsf T}X)^{-1}] = I/(n - p - 1)$ for $n \ge p + 2$, infinite diagonal for $n \in \{p, p + 1\}$ (Lemma 1)
Exact double descent risk $s^2(1 + \frac p{n - p - 1})$ below, $\lVert\beta_T\rVert^2(1 - \frac np) + s^2(1 + \frac n{p - n - 1})$ above, infinite for $\lvert p - n\rvert \le 1$ (Theorem 1)
Random features, digits test loss peaks at $N = n = 300$; 4,000 features beat every model below the threshold
Norm bounds separate true from random labels; vacuous (45 and 181 here)
Nagarajan and Kolter even the tightest algorithm-dependent two-sided uniform convergence bound can be nearly vacuous
Alternatives margins, PAC-Bayes (non-vacuous for stochastic nets), compression (for the compressed net), stability (label-independent)

What we have learned

Uniform convergence bounds explain generalization by the size of the class, measured by its VC dimension or Rademacher complexity. For a class that fits every labeling of its sample, as modern networks do, those measures are at their maximum, and any bound that depends on the class and the input distribution but not on the labels must be at least one half, whatever labels the network was trained on. A small randomization test on the digits reproduces the observation behind this: the same network fits true labels and coin flips, and only the first predicts well. Double descent sharpens the puzzle, since past the interpolation threshold larger models can predict better. In the Gaussian weak-features model it is a theorem: the variance of the minimum-norm fit is infinite at the threshold and falls beyond it. Norm-based, PAC-Bayes and compression bounds use the trained weights and so can respond to the labels, but none yet gives a tight guarantee for the network that training returns, and Nagarajan and Kolter showed settings in which no two-sided uniform convergence argument can.

This is the last article of the Statistical Learning Theory unit. Its open questions lead back to two practical tools that do not depend on any of these bounds: a held-out test set, whose error is a sum of independent terms that Hoeffding's inequality controls for the one model being evaluated (Training, Validation and Test Sets), and the study of what a trained model has learned, which the library's notes on memorization and double descent and influence functions approach from the inside.

References

  • Alpaydin, E., and Kaynak, C. (1998). Optical Recognition of Handwritten Digits [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C50P49. The scikit-learn digits are a copy of its test part. record · 3 pages
  • Arora, S., Ge, R., Neyshabur, B., and Zhang, Y. (2018). Stronger generalization bounds for deep nets via a compression approach. Proceedings of the 35th International Conference on Machine Learning, PMLR 80, 254–263. arXiv:1802.05296. Theorem 2.1 and its remarks; §§6.2 and 6.3. record
  • Bartlett, P. L., Foster, D. J., and Telgarsky, M. (2017). Spectrally-normalized margin bounds for neural networks. Advances in Neural Information Processing Systems 30. arXiv:1706.08498. Theorem 1.1; Figures 1 to 3. record
  • Bartlett, P. L., Harvey, N., Liaw, C., and Mehrabian, A. (2019). Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63), 1–17. arXiv:1703.02930. Abstract. (An earlier extended abstract by Harvey, Liaw and Mehrabian appeared at the Conference on Learning Theory, 2017.) record
  • Belkin, M., Hsu, D., Ma, S., and Mandal, S. (2019). Reconciling modern machine-learning practice and the classical bias–variance trade-off. Proceedings of the National Academy of Sciences, 116(32), 15849–15854. https://doi.org/10.1073/pnas.1903070116 (arXiv:1812.11118). Figures 2 and 4; §§2 and 4. record · 2 pages
  • Belkin, M., Hsu, D., and Xu, J. (2020). Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4), 1167–1180. https://doi.org/10.1137/20M1336072 (arXiv:1903.07571). Theorem 1, Corollary 1 and Figure 1; §2.2. record
  • Breiman, L., and Freedman, D. (1983). How many variables should be entered in a regression equation? Journal of the American Statistical Association, 78(381), 131–136. https://doi.org/10.1080/01621459.1983.10477941. Cited as credited by Belkin, Hsu and Xu (2020); not consulted. record
  • Dziugaite, G. K., and Roy, D. M. (2017). Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI). arXiv:1703.11008. §§1, 4 and 5; Table 1. record
  • Hardt, M., Recht, B., and Singer, Y. (2016). Train faster, generalize better: stability of stochastic gradient descent. Proceedings of the 33rd International Conference on Machine Learning, PMLR 48, 1225–1234. arXiv:1509.01240. Definition 2.1; Theorems 2.2, 3.8 and 3.12. record
  • Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. J. (2022). Surprises in high-dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2), 949–986. https://doi.org/10.1214/21-AOS2133 (arXiv:1903.08560). §1 (summary of results); Theorem 1, eq. 8 and Corollary 1. record
  • James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. §10.8, as reported in The Bias–Variance Tradeoff; not consulted. record · 31 pages
  • Nagarajan, V., and Kolter, J. Z. (2019). Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems 32. arXiv:1902.04742 (version 4). §§1.1, 2 and 3; Definition 3.3; Theorem 3.1; Remark 3.1; Appendices B.1, F and J. record · 2 pages
  • Nakkiran, P., Kaplun, G., Bansal, Y., Yang, T., Barak, B., and Sutskever, I. (2020). Deep double descent: where bigger models and more data hurt. International Conference on Learning Representations. arXiv:1912.02292; also Journal of Statistical Mechanics: Theory and Experiment (2021), 124003, https://doi.org/10.1088/1742-5468/ac3a74. §§1 and 2; Definition 1 and Hypothesis 1. record · 2 pages
  • Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. (2017). Understanding deep learning requires rethinking generalization. International Conference on Learning Representations. arXiv:1611.03530. §§1 to 4 and Appendix A; Table 1; Theorem 1. record · 2 pages