Understanding deep learning requires rethinking generalization

The network that reaches 89% test accuracy on CIFAR10 also reaches 100% training accuracy when every label is replaced by a random one.

Zhang, Bengio, Hardt, Recht and Vinyals replaced the labels of standard image benchmarks with random ones and trained unchanged networks on them. The networks fit the noise perfectly, so the size of the model family and the regularizers applied in training cannot be what makes the same networks generalize on real labels.

One experiment, the three classical theories it rules out, a short proof that any labeling of a training set is reachable, and a linear-model case study of what the optimizer contributes.

A convolutional network trained on CIFAR10 with 1.6 million parameters and 50,000 training images gets 100% of the training set right and about 89% of a held-out test set. The 11-point difference is the generalization error, and in 2016 every standard account of why it was small pointed at one of two things: the model family is somehow restricted enough that fitting the training set forces a good function, or the regularizers (weight decay, dropout, data augmentation, early stopping) confine training to a well-behaved subset of the family. This paper runs one experiment that both accounts fail, proves that the failure is unavoidable for any model with more parameters than training points, and then works through the simplest model where the question is still open.

The page follows the paper's order: the randomization test and its numbers, the three theoretical tools it rules out (Rademacher complexity, VC dimension, uniform stability), the regularization ablations, the finite-sample expressivity theorem, and the linear-model analysis of what stochastic gradient descent adds.

The gap theory has to explain

Fix a dataset of $n$ labeled examples drawn from some distribution, a model family $\mathcal{H}$ (every function a given architecture can compute, over all weight settings), and a training algorithm that returns one $h \in \mathcal{H}$. Training error is the fraction of the $n$ examples that $h$ gets wrong; test error is the fraction it gets wrong on fresh draws from the same distribution. Generalization error is the difference. A bound on it has to come from somewhere, and statistical learning theory offers two places to look.

Complexity measures look at the family. Vapnik–Chervonenkis (VC) dimension counts the largest set of points the family can label in every possible way; Rademacher complexity measures how well the family can fit random signs; both feed a bound of the form test error $\le$ training error plus a term that grows with the measure and shrinks with $n$. Stability measures look at the algorithm instead: if swapping one training example changes the returned function very little, the training error cannot be far from the test error. Neither kind of bound depends on the training labels: a complexity measure is a fact about $\mathcal{H}$, a stability measure is a fact about the algorithm, and the same number comes out whether the labels are real or random.

The paper's CIFAR10 networks are a small Inception (1,649,402 parameters), a small Alexnet (1,387,786), and two multilayer perceptrons, MLP 3x512 (1,735,178) and MLP 1x512 (1,209,866). All take 28x28x3 center crops, so an input has $d = 2352$ numbers, and all are trained with SGD at momentum 0.9 and a learning rate of 0.1 (Inception) or 0.01 (the rest), decayed by 0.95 per epoch. On ImageNet the model is Inception V3 on 299x299 inputs, trained with asynchronous SGD on 50 workers. Every parameter count is between 24 and 35 times the number of CIFAR10 training images.

The randomization test

The experiment is a randomization test from non-parametric statistics: take the real dataset, replace the labels with draws that carry no information about the inputs, and rerun the identical procedure. Six versions of the data are used: true labels; partially corrupted labels, where each label is independently replaced by a class drawn at random with probability $p$; random labels, the $p = 1$ case; shuffled pixels, one fixed permutation of pixel positions applied to every image; random pixels, a different permutation per image; and Gaussian, where every image is replaced by noise with the dataset's mean and variance. Nothing else changes: same architecture, same optimizer, same learning-rate schedule, no hyperparameter search.

# the randomization test, as the released code runs it
# (fitting-random-labels/cifar10_data.py, corrupt_labels)
np.random.seed(12345)                    # one fixed corruption per run
mask = np.random.rand(len(labels)) <= p  # each label flips with prob p
labels[mask] = np.random.choice(10, mask.sum())  # uniform random class
# train exactly as usual: same net, same SGD, same schedule
# 100% train accuracy on CIFAR10; test accuracy ~10% (chance)

On CIFAR10 every architecture reaches zero training error on random labels: Inception 100%, Inception without batch normalization 100%, Alexnet 99.82%, MLP 3x512 100%, MLP 1x512 99.34%. Test accuracy sits at 9.78%, 10.12%, 9.86%, 10.48% and 10.61%, which is chance for ten classes. On ImageNet, Inception V3 reaches 95.20% top-1 training accuracy on a million images with random labels from 1,000 classes, and 0.11% top-1 test accuracy, with no hyperparameter change from the true-label run; the authors expect a tuned run would reach 100%. Random pixels and Gaussian noise are fit too, and start converging sooner than random labels, which the paper attributes to noise images being farther apart from each other than natural images of the same class.

The learning curves on random labels have a characteristic shape. The loss stays high for the first passes over the data, because every label is uncorrelated with its image and the gradients from different examples conflict. Because the random assignment is fixed across epochs, repeated passes let the network separate each image individually, and once that starts the loss falls at the usual rate. The paper measures the cost as time to reach the fit: it rises with the corruption fraction by a small constant factor, and the learning-rate schedule never needs to change.

Figure 1 runs a scaled-down version of the test in the browser. A two-hidden-layer ReLU network with 64 units per layer (4,417 weights) trains by full-batch Adam on 100 points in the unit square, labeled by a smooth boundary. The slider sets $p$; ringed points are the ones whose label was replaced. Test accuracy is measured on 400 clean points from the same boundary. At $p = 0$ the map settles into two regions in about 150 steps and test accuracy is near 95%. At $p = 1$ the map becomes a patchwork of islands, one per mislabeled point, training accuracy still reaches 100% after roughly a thousand steps, and test accuracy stays near 50%, chance for two classes.

Between the two extremes the paper's Figure 1c shows test error rising smoothly with $p$ toward 90% (chance on ten classes) while training error stays at zero throughout. Read as a single statement: the network extracts whatever real signal is left in the labels and fits the rest by brute force, and the architecture places no obstacle in the way of either.

What a perfect fit rules out

The empirical Rademacher complexity of a family $\mathcal{H}$ on inputs $x_1, \dots, x_n$ is the paper's equation (1):

Draw a random sign for every input, find the function in the family that correlates best with those signs, record the correlation, and average over draws. For a family of $\pm 1$-valued classifiers the value lies between 0 and 1. It enters a generalization bound of the form test error $\le$ training error $+\, 2\hat{\mathfrak{R}}_n(\mathcal{H})$ plus a confidence term of order $\sqrt{\log(1/\delta)/n}$. The definition is the randomization test in miniature: random signs are random binary labels. A family that can fit any labeling of the $n$ training inputs has some $h$ with $h(x_i) = \sigma_i$ for every draw, so the supremum is exactly 1 and $\hat{\mathfrak{R}}_n(\mathcal{H}) = 1$. The bound then reads test error $\le$ training error $+\, 2$, which is true of every classifier and says nothing. The experiments are multiclass, but restricting them to any two classes gives a binary problem with the same outcome.

Figure 2 computes equation (1) exactly for a family where the supremum can be found by dynamic programming: $n$ points on a line and the class $\mathcal{H}_k$ of $\pm 1$ step functions with at most $k$ sign changes. At $k = 0$ the family is two constant functions and the complexity is the expected absolute mean of $n$ random signs, about $\sqrt{2/\pi n}$, 0.14 at $n = 32$. Raising $n$ at fixed $k$ pushes the value down, which is what a useful bound needs. Raising $k$ toward $n - 1$ pushes it to exactly 1, because a sequence of $n$ signs has at most $n - 1$ changes and can then be matched sign for sign.

VC dimension and its real-valued analog, the fat-shattering dimension, fail the same way: the networks shatter the training set, so any bound built on the dimension of the whole family is trivial at these sample sizes. Bartlett's 1998 bound on the fat-shattering dimension in terms of the $\ell_1$ norm of the weights at each node was the known way to escape a size-based bound, but it is stated for sigmoid networks, and the paper notes that for ReLU networks the $\ell_1$ norm is no longer informative; Neyshabur, Tomioka and Srebro generalized the idea to other norms in 2015, and the authors report that those bounds do not explain the behavior they observe either.

Uniform stability is the algorithm-side tool. An algorithm is $\beta$-uniformly stable if replacing any single training example changes the loss of the returned function by at most $\beta$ at every test point, for every dataset. Bousquet and Elisseeff showed the expected gap between test and training loss is then at most $2\beta$, and Hardt, Recht and Singer showed in 2016 that SGD is uniformly stable with a $\beta$ that grows with the number of steps taken, for both convex and non-convex losses. The definition contains a supremum over all datasets, so $\beta$ is the same for the true-label and random-label runs: same algorithm, same steps, same learning rate. The random-label run has a loss gap of about 90 points on CIFAR10, so any valid $\beta$ for these training runs is at least 0.45, and a bound of that size says nothing about the true-label run whose gap is 11 points. The paper draws the conclusion for Hardt, Recht and Singer's analysis directly: it had to restrict itself to a few passes over the data because SGD over many passes is not uniformly stable, and a weaker, label-aware notion of stability is needed to go further.

Regularizers help, but are not the cause

If the family is not the answer, the regularizers are the remaining candidate. The classical role of a regularizer is to shrink the effective family: penalize the norm of the solution and the Rademacher complexity of the set of reachable solutions drops. The paper tests three explicit regularizers by switching them off. Data augmentation (random crops on CIFAR10; crops plus brightness, saturation, hue and contrast perturbations on ImageNet). Weight decay, an $\ell_2$ penalty on the weights, equivalent to constraining them to a Euclidean ball. Dropout, which zeroes each unit of a layer's output with a fixed probability, used only by Inception V3 on ImageNet.

Figure 3 holds every number from Tables 1, 2 and 4. On CIFAR10, Inception goes from 89.05% test accuracy with random crops and weight decay to 85.75% with neither; Alexnet from 81.22% to 76.07%; MLP 3x512 from 53.35% to 52.39%. The regularizers are worth 1 to 5 points, and every model still generalizes far above chance without them. On ImageNet the drop is larger: Inception V3 falls from 77.84% top-1 with augmentation, dropout and weight decay to 59.80% with none, 18 points, against a chance rate of 0.1%. Augmentation alone recovers most of it, 72.95%, so the ability to exploit known symmetries of the data is worth more than either norm penalty. The paper also compares the unregularized Inception V3 (80.38% top-5) against the ILSVRC 2012 winner, Alexnet with all its regularization (83.6% top-5): a change of architecture bought more than the regularizers did.

Turning regularizers on does not stop the memorization either. With weight decay at its default coefficient, Inception and MLP 3x512 still fit random CIFAR10 labels at 100% and MLP 1x512 at 99.21%; Alexnet with weight decay failed to converge on random labels, the one exception. With random cropping the fit reaches 99.93% online training accuracy (a different quantity, since the crops change each epoch while the random labels stay fixed), which needed a slower decay of the learning rate and more epochs. On ImageNet, Inception V3 with dropout and weight decay reaches 91.18% top-1 training accuracy on random labels. The paper's reading is that in deep learning a regularizer behaves like a tuning parameter that improves the final number rather than the mechanism that makes generalization possible, the opposite of its role in convex empirical risk minimization, where without it the trivial interpolating solutions win.

Two implicit regularizers get the same treatment. Early stopping: the ImageNet table lists in parentheses the best test accuracy seen during training, 72.57% against a final 67.18% with weight decay only, and 63.16% against 59.80% with nothing, so stopping early would have helped there (with the caveat the paper itself makes, that choosing the stopping point on the test set needs a separate validation set to be rigorous). On CIFAR10 the curves show no such gain. Batch normalization: an Inception with every batch-norm layer removed trains less smoothly and lands at 82.00% instead of 85.75% with no regularizers, a 3 to 4 point effect, and fits random labels at 100% just like the original.

Why any labeling is reachable: 2n + d weights

The experiments say these networks can memorize; the theorem says why every network past a modest size can. Classical expressivity results are about the whole input domain (which functions on $\mathbb{R}^d$ a family can approximate, and why depth $k$ beats depth $k-1$). The paper asks a finite-sample question instead: given $n$ distinct points $S \subset \mathbb{R}^d$ and any target function $f: S \to \mathbb{R}$, is there a weight setting whose network output $c(x)$ equals $f(x)$ on every point of $S$?

Theorem 1. There exists a two-layer ReLU network with $2n + d$ weights that can represent any function on a sample of size $n$ in $d$ dimensions.

The network is

a single vector $a$ shared by all hidden units, $n$ thresholds $b_j$, and $n$ output weights $w_j$: $d + n + n$ numbers. The proof has three steps. First, project every sample to a scalar $x_i = \langle a, z_i \rangle$. Since the $z_i$ are distinct, almost any $a$ gives distinct projections, so order them $x_1 < x_2 < \dots < x_n$. Second, choose the thresholds to interleave the points, $b_1 < x_1 < b_2 < x_2 < \dots < b_n < x_n$; the midpoint between consecutive points works. Now the hidden unit $j$ is switched off (outputs 0) at every point to the left of $b_j$ and outputs the positive number $x_i - b_j$ at every point to its right, so the matrix of hidden activations

is lower triangular ($A_{ij} = 0$ for $j > i$) with diagonal entries $x_i - b_i > 0$. Third, the outputs on the sample are $c(z_i) = (Aw)_i$, so the $n$ equations $c(z_i) = y_i$ are the linear system $Aw = y$. A triangular matrix with a nonzero diagonal is invertible (this is the paper's Lemma 1, which also notes that its eigenvalues are the diagonal entries, so the smallest is $\min_i (x_i - b_i)$), and forward substitution solves for $w$ in $n^2/2$ operations. The targets $y$ were arbitrary, so every labeling of the sample is reached.

# Theorem 1, n = 3 points on a line, d = 1
x = [0.20, 0.50, 0.90]          # projected inputs  <a, z_i>, sorted
b = [0.05, 0.35, 0.70]          # thresholds interleaving them
y = [1.0, -1.0, 0.5]            # any targets at all
A = [[max(x[i] - b[j], 0) for j in range(3)] for i in range(3)]
# A = [[0.15, 0,    0   ],
#      [0.45, 0.15, 0   ],
#      [0.85, 0.55, 0.20]]      lower triangular, diagonal > 0
w = forward_substitution(A, y)  # [6.667, -26.667, 47.5]
c = lambda t: sum(w[j] * max(t - b[j], 0) for j in range(3))
# c(0.2) = 1.0   c(0.5) = -1.0   c(0.9) = 0.5   (2n + d = 7 weights)

The worked case shows what the construction costs. With diagonal gaps of 0.15, 0.15 and 0.2, the solved weights are 6.7, −26.7 and 47.5, and they alternate in sign so that each new ramp cancels the accumulated slope of the earlier ones before setting its own target. The smallest eigenvalue from Lemma 1 bounds how large the weights can get, which the paper mentions as the route to a weight bound for the construction. Figure 4 lets you redraw the targets and watch the ramps re-solve.

For CIFAR10 the theorem needs $2 \cdot 50{,}000 + 2352 = 102{,}352$ weights; the smallest network in the paper has 1,209,866, twelve times more. For ImageNet, $2 \cdot 1{,}281{,}167 + 268{,}203$ is about 2.83 million, and Inception V3 is many times that. Every network in the paper sits well past the point where any labeling of its training set is expressible, so a theory that predicts generalization from the family alone has no room to work with. The paper credits Livni, Shalev-Shwartz and Shamir with an earlier construction using $O(dn)$ parameters, and gives Corollary 1 for depth: for every $k \ge 2$ there is a ReLU network of depth $k$, width $O(n/k)$ and $O(n + d)$ weights with the same property, built by splitting the projected axis into $m$ intervals, fitting each interval's $n/m$ points at its own layer, and adding a multiplexer of approximate indicator functions that selects the right layer's output.

Linear models: SGD picks the minimum-norm fit

Expressivity says the family contains memorizers; the experiments say SGD does not always return one. So the remaining question is what the optimizer contributes, and the paper studies it in a setting where the answer can be computed: linear models with more features than examples. Take $n$ distinct points $(x_i, y_i)$ with $x_i \in \mathbb{R}^d$, a nonnegative loss with $\mathrm{loss}(y, y) = 0$, and the empirical risk minimization problem

Stack the inputs as the rows of an $n \times d$ matrix $X$. If $d \ge n$ and $X$ has rank $n$, the linear system $Xw = y$ has infinitely many solutions for every right-hand side, and each one drives (2) to zero: the linear family fits any labeling, the same situation the networks are in. The question becomes which of the zero-loss solutions generalize, and whether anything distinguishes them.

Curvature does not distinguish them. The Hessian of (2) is

because at any zero-loss solution the prediction on example $i$ equals $y_i$, so the second derivative of the loss is evaluated at the same point $z = y_i$ whichever solution you are at. The Hessian is the same matrix at every global minimum, and it has rank at most $n < d$, so it is degenerate at all of them. Flatness, the usual heuristic for which minimum will generalize, cannot separate them here.

The optimizer does distinguish them. One step of SGD on (2) is $w_{t+1} = w_t - \eta_t\, e_t\, x_{i_t}$, where $e_t$ is the derivative of the loss with respect to the prediction on the sampled example $i_t$. Every step adds a multiple of one input vector. Starting from $w_0 = 0$, the iterate is always a combination of inputs, $w = \sum_i \alpha_i x_i = X^{\top} \alpha$ for some coefficients $\alpha$. Impose that the run also fits the labels, $Xw = y$, and the two identities combine into

an $n \times n$ system in $\alpha$ with a unique solution, since the Gram matrix $K = XX^{\top}$ is invertible when $X$ has rank $n$. The system depends on the inputs only through their dot products $K_{ij} = x_i^{\top} x_j$, which is the kernel trick arrived at from the optimizer rather than from a representer theorem. And the solution it selects is a specific one: $w = X^{\top} (XX^{\top})^{-1} y = X^{+} y$, the pseudoinverse solution. Any other interpolant is $X^{+}y + v$ with $Xv = 0$, and $v$ is orthogonal to the row space that $X^{+}y$ lives in, so its squared norm is $\lVert X^{+}y \rVert^2 + \lVert v \rVert^2$. Out of all the zero-loss solutions, SGD from zero returns the one with the smallest $\ell_2$ norm. This is what the paper means by implicit regularization: no penalty was written down, and the algorithm imposed one anyway.

Figure 5 is the two-dimensional case, one training point and two weights. The dashed line is every $w$ with $w \cdot x = y$. The gradient of the squared loss is $(w \cdot x - y)\, x$, a multiple of $x$, so gradient descent moves only along the data direction and lands wherever that direction meets the line. From the origin the landing is the perpendicular foot, the minimum-norm point. From anywhere else it is a different interpolant with a larger norm, identical training loss, an identical Hessian, and a different prediction on a test input.

The kernel form makes the experiment cheap enough to run on real data. Solve (3) directly, with no regularizer, and read off the test error:

# Section 5: fit any labels with a linear model, no regularizer
K = X @ X.T                 # n x n Gram matrix; MNIST: 60,000^2 * 8 B = 28.8 GB
alpha = solve(K, y)         # one LAPACK call, < 3 min on a 24-core box
w = X.T @ alpha             # = X^+ y, the minimum-norm interpolant
# test error: MNIST raw pixels 1.2%, Gabor features 0.6%
#             CIFAR10 Gaussian kernel 46%, random conv features 17%

On MNIST with raw pixels the interpolating solution gets 1.2% test error; with a Gabor wavelet transform first, 0.6%. Adding a regularizer improves neither. On CIFAR10 a Gaussian kernel on pixels gets 46% test error; preprocessing with a random convolutional net of 32,000 random filters (the Coates and Ng architecture with random instead of k-means filters) gets 17%, and an $\ell_2$ penalty brings that to 15%, without data augmentation, all from interpolating solutions of a convex problem.

The paper then tests whether the minimum-norm property predicts anything, and reports that it does not. It is easy to build zero-loss solutions that generalize badly: a Gaussian kernel with centers at random points, or a solution forced to also fit random labels on the test set. Both have a much larger norm than the minimum-norm one. But the MNIST solution on raw pixels has norm about 220 and 1.2% error, while the wavelet-preprocessed solution has norm about 390 and 0.6% error: the norm went up and the error halved. The authors' own verdict is that minimum norm may guide algorithm design and is only a very small piece of the generalization story.

What the paper settles and what it leaves open

The paper's conclusion is a definition and two claims. The effective capacity of a model is what the randomization test measures: whether the training procedure, run as usual, can drive training error to zero on labels that carry no information. For every architecture tested it can, which means these models can memorize their training sets, and any explanation of their generalization that depends only on the model family, only on the training algorithm, or on the explicit regularizers, is ruled out. The second claim is about optimization: fitting random labels costs a small constant factor in training time, so whatever makes SGD converge easily on these problems is not the same thing as whatever makes the result generalize.

The paper's claims stop short of three stronger ones. It does not claim networks memorize real data instead of learning it; the partial-corruption experiment shows them doing both at once, and Arpit and colleagues showed in 2017 that networks trained on real data learn simple, shared patterns first. It does not claim regularizers are useless; the ImageNet ablation is 18 points. It does not claim the minimum-norm bias of SGD explains generalization; the paper's Section 5 gives a counterexample. What it claims is that a correct theory needs a complexity measure under which these enormous models are simple, and that in 2017 no such measure existed.

The follow-up literature has mostly confirmed the negative result. Nagarajan and Kolter showed in 2019 that uniform-convergence bounds, including ones that account fully for the implicit bias of gradient descent, can be vacuous on networks that generalize, and can even grow with the training set. Belkin and colleagues showed in 2019 that interpolating models follow a double-descent curve, with test risk falling again past the point of exact fit, which puts the paper's kernel experiments in a broader pattern. Soudry and colleagues showed in 2018 that the implicit bias depends on the loss: gradient descent on the logistic loss over separable data converges in direction to the maximum-margin classifier while the norm grows without bound, so the minimum-norm story of the paper's Section 5 is specific to the squared loss and a zero start. In 2021 the authors republished the paper in Communications of the ACM under the title "Understanding deep learning (still) requires rethinking generalization".