Understanding deep learning requires rethinking generalization

Context. Classical theory explains a small train-test gap through the capacity of the hypothesis class, the stability of the algorithm, or regularization, yet networks with far more parameters than training images generalize, and it was unclear which of these was at work. The paper answers with a randomization test: keep the architecture, inputs, optimizer and hyperparameters, replace the labels by random ones, and retrain. The networks still reach zero training error, so the gap jumps from about 14% to 90% on CIFAR10 (Inception) with nothing else changed. Whatever explains generalization cannot be a property of the architecture, the input distribution or the training recipe alone, since all are identical on the random-label problem; it must depend on how the labels relate to the inputs, through the particular weights the algorithm finds.

Setting and main findings. CIFAR10 (50,000 images, 10 classes) with a small Inception, a small AlexNet and MLPs, all with 1.2M to 1.7M parameters, and ImageNet with Inception V3, trained by SGD with momentum and no weight decay, dropout or augmentation unless stated. Labels are partially corrupted (each replaced with probability $p$ by a uniform class) or fully random; inputs may be shuffled pixels (one fixed permutation for all images), random pixels or Gaussian noise. Every CIFAR10 model fits random labels to between 99.34% and 100% training accuracy with unchanged hyperparameters, Inception V3 reaches 95.20% top-1 training accuracy on ImageNet, and test accuracy is at chance. Explicit regularization adds a few points on CIFAR10 and 18 top-1 points on ImageNet, so in the paper's words it is neither necessary nor by itself sufficient for controlling generalization error.

Theorem 1 (finite-sample expressivity). For every sample $S\subset\mathbb R^d$ of size $n$ and every $f:S\to\mathbb R$ , the two-layer ReLU network $c(x)=\sum_{j=1}^n w_j\max\{\langle a,x\rangle-b_j,0\},\qquad a\in\mathbb R^d,\ b,w\in\mathbb R^n,$ with $2n+d$ free weights has weights giving $c(x)=f(x)$ on $S$ . A corollary trades width for depth: for every $k\ge2$ some ReLU network of depth $k$ , width $O(n/k)$ and $O(n+d)$ weights does the same.

Step 1

Random labels, partial corruption and structureless inputs are all fit to zero training error at small extra cost. All four CIFAR10 architectures, and Inception V3 on ImageNet, reach (nearly) zero training loss on random labels without retuning, and the time to overfit grows by a factor under four. Shuffled pixels, random pixels and Gaussian inputs are fit as well, so at this sample size the convolutional prior is not a capacity limit. SGD finds a global minimum just as easily when the minimum is useless, which separates optimization from generalization. With partial corruption the network fits the signal and memorizes the rest: training error stays zero and test error rises steadily to the 90% chance level as $p$ goes from 0 to 1, the shape Mallinar et al. later call tempered overfitting.

Step 2

The randomization test rules out every bound that cannot see the labels. Such a bound depends only on the architecture, $n$ , the inputs and the training recipe, so it takes the same value on the random-label problem, where it must cover a gap of about 90%; it is therefore at least that large on the true labels. The Rademacher bound shows it most directly: its complexity term $\hat{\mathfrak R}_n(\mathcal H)=\mathbb E_\sigma\sup_{h\in\mathcal H}\frac1n\sum_i\sigma_ih(x_i)$ is literally the ability to fit random signs on these inputs, so Step 1, carried over to a binary version of the problem (by assertion, not experiment), gives $\hat{\mathfrak R}_n\approx1$ , a trivial bound, and the same holds for VC and fat-shattering bounds on the unrestricted network class. Uniform stability, a worst case over all datasets, cannot tell the two runs apart either. What survives are bounds that see the labels through the learned weights: norm or margin capacity of the weights SGD finds, PAC-Bayes bounds around the trained network, and weaker data-dependent stability.

Step 3

Explicit and implicit regularizers add a few points of accuracy but are neither necessary nor sufficient. Removing augmentation and weight decay costs the CIFAR10 models a few points (Inception 85.75% against 89.05%); on ImageNet, with dropout also removed, the loss is 18 top-1 points, most of which augmentation alone recovers. Keeping the regularizers does not prevent memorization: with default weight decay Inception and both MLPs still fit random labels, Inception V3 reaches 91.18% top-1 on ImageNet random labels with weight decay and dropout, and with augmentation Inception fits random labels to over 99% once a decay factor is slowed from 0.95 to 0.999. Implicit regularizers are small too: early stopping would add a few points on ImageNet (picked on the test set) and batch normalization 3 to 4 on CIFAR10.

Removing weight decay and augmentation costs Inception only a few points on CIFAR10, and with weight decay it still fits random labels. What should a practitioner conclude about explicit regularization?

Step 4

Two layers and $2n+d$ weights interpolate any labels on any sample. The proof of Theorem 1 projects to one dimension and builds a piecewise-linear interpolant with one kink per point. A generic direction $a$ gives distinct projections $x_i=\langle a,z_i\rangle$ ; sort them and interleave the biases, $b_1\lt x_1\lt b_2\lt x_2\lt\cdots\lt b_n\lt x_n$ . The interpolation conditions are $y=Aw$ with $A_{ij}=\max\{x_i-b_j,0\},$ which vanishes for $i\lt j$ because $b_j\gt x_i$ there, so $A$ is lower triangular with positive diagonal and invertible. The depth corollary, sketched only, gives each layer the interpolant for a block of $n/k$ sorted points and selects the right output with constant-size ReLU indicators.

In the proof of Theorem 1, what does the interleaving

b_1\lt x_1\lt b_2\lt\cdots\lt b_n\lt x_n

achieve?

Step 5

In linear models SGD picks the min-norm interpolant, and it can generalize without regularization. With $d\ge n$ and $X$ of rank $n$ , every interpolant is a global minimum with the same Hessian, so curvature cannot choose among them, and the optimizer makes the choice: SGD from $w_0=0$ adds multiples of the $x_i$ and stays in the row space, whose only interpolant is $w=X^\top(XX^\top)^{-1}y$ , the minimum- $\ell_2$ -norm solution, which is the same solution a kernel method with the linear kernel returns. Solving $K\alpha=y$ exactly gives 1.2% test error on raw MNIST and 0.6% after a Gabor transform, with no gain from regularization. The norm does not rank solutions (about 220 on raw pixels and 390 after the Gabor transform while the error halves), but since rescaling the features by $c$ rescales the min-norm solution by $1/c$ , the two norms have no common unit, and this shows only that the raw norm is not a universal predictor. These kernel interpolants are the setting benign-overfitting theory went on to analyze.

For a linear model with

d\ge n

, why does SGD started at

w_0=0

on squared loss converge to the minimum-norm interpolant?

Consequences and limits. The paper moved the question from whether the class is small to what makes the solution SGD finds on real labels simple, and set a test for any answer: small on true labels, large on random labels, same architecture and inputs. Bartlett et al.'s margin bound is checked against exactly this test, the PAC-Bayes papers in this section compute bounds that are nonvacuous on real labels, and Nagarajan and Kolter argue that even uniform convergence over the algorithm's own outputs may be too weak. Limits: everything except Theorem 1 is empirical, "effective capacity" is never defined, and the case against Rademacher and VC bounds concerns the unrestricted network class and leaves norm-restricted classes untouched.

Terms

Randomization test: retrain with labels (or inputs) randomized, everything else fixed; measures what the setup can fit
Partially corrupted labels: each label replaced by a uniform class with probability $p$ ; interpolates between true and random labels
Shuffled vs random pixels: one permutation for all images, against a fresh permutation per image
$\hat{\mathfrak R}_n(\mathcal H)=\mathbb E_\sigma\sup_h\frac1n\sum_i\sigma_ih(x_i)$: empirical Rademacher complexity: the class's ability to fit random signs on the sample
Uniform stability: worst-case change of the output when one example is replaced; blind to the labels
Generalization error: test minus training error; equal to test error when training error is zero
$c(x)=\sum_jw_j(\langle a,x\rangle-b_j)_+$: Theorem 1 network: $2n+d$ weights, one shared direction $a$ , interpolates any labels
Interleaving: $b_1\lt x_1\lt b_2\lt\cdots\lt x_n$ makes $A_{ij}=(x_i-b_j)_+$ lower triangular and invertible
$w=X^\top(XX^\top)^{-1}y$: min-norm interpolant; where SGD from zero lands in a linear model
Effective capacity: informal: what the architecture plus training recipe can fit on a sample of this size

Quiz

Why does uniform stability fail the randomization test in the same way as Rademacher complexity?
On random labels the CIFAR10 networks reach zero training loss with unchanged hyperparameters, in under four times the usual training time. What does this say about the role of optimization?
Which candidate explanation of generalization can, in principle, pass the randomization test?
With partial label corruption, training error is zero at every $p$ and test error rises steadily with $p$ . What does this show beyond the random-label result?

Sources

Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR, 2017.

Peter Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. NeurIPS, 2017.
Neil Mallinar, James B. Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakkiran. Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting. NeurIPS, 2022.