Understanding deep learning requires rethinking generalization

The same network that scores 89% on CIFAR10's test set reaches 100% training accuracy when every label is random.

Zhang, Bengio, Hardt, Recht and Vinyals replaced the labels of standard image datasets with random ones and trained the networks unchanged. The networks fit the random labels perfectly, so neither the size of the model family nor the regularizers used in training can be what makes the same networks generalize on real labels.

One experiment on random labels, the three classical bounds it defeats, a short proof that a small network can fit any labeling, and a linear model where the optimizer's choice among perfect fits can be computed exactly.

Train a small Inception network with 1,649,402 parameters on CIFAR10's 50,000 training images and it classifies 100% of them correctly and 89.05% of the 10,000 test images. Training error 0%, test error 10.95%: the 10.95-point difference is the generalization gap. In 2016 the standard explanations for why that gap was small pointed at one of two things. Either the model family is restricted enough that fitting the training set forces a good function, or the regularizers (weight decay, dropout, data augmentation, early stopping) keep training inside a well-behaved part of the family.

The paper runs one experiment that both explanations fail. Replace every training label with a random class and train the same network the same way: it still reaches 100% training accuracy, and test accuracy drops to chance. The page follows the paper's order: the gap and the bounds meant to control it, the randomization test and its numbers, what the result rules out, the regularization ablations, a theorem that shows how few weights memorization needs, and a linear model in which the optimizer's role can be worked out by hand.

What the generalization gap is

Fix a dataset of $n$ labeled examples drawn from some distribution, a model family $\mathcal{H}$ (every function one architecture can compute, over all settings of its weights), 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. The generalization gap is test error minus training error, and a theory of generalization is a way to bound it before seeing the test set.

Statistical learning theory offers two kinds of bound. Complexity measures describe the family. Vapnik–Chervonenkis (VC) dimension is the size of the largest set of points the family can label in every possible way; Rademacher complexity measures how well the family can correlate with random signs. Both give a bound of the form test error $\le$ training error plus a term that grows with the measure and shrinks as $n$ grows. Stability measures describe the algorithm instead: if replacing one training example barely changes the function the algorithm returns, the training error of that function cannot sit far from its test error. Neither kind of bound looks at the training labels. A complexity measure is a property of $\mathcal{H}$ and the inputs, a stability measure is a property of the algorithm, and both give the same number 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). Every one has 24 to 35 times as many parameters as there are training images. Inputs are 28x28x3 center crops of the 32x32 images, so each input is a vector of $d = 2352$ numbers. Training is SGD with momentum 0.9 at a learning rate of 0.1 (Inception) or 0.01 (the others), multiplied by 0.95 after every epoch. On ImageNet the model is Inception V3 on 299x299 inputs, trained with asynchronous SGD on 50 workers over 1,281,167 training images in 1,000 classes.

How the randomization test works

The experiment borrows the randomization test from non-parametric statistics: replace the labels with draws that carry no information about the inputs, rerun the identical training, and compare. The paper uses six versions of the data. True labels. Partially corrupted labels, where each label is independently redrawn as a uniform random class with probability $p$ (the redraw can land on the original class). Random labels, the case $p = 1$. Shuffled pixels, one fixed permutation of pixel positions applied to every image in the training and test sets. Random pixels, a different permutation for each image. Gaussian, where each image is replaced by noise with the dataset's mean and variance. Architecture, optimizer and learning-rate schedule stay as they were for true labels, with no new hyperparameter search. The random labels are drawn once and stay fixed across epochs, which is what the released code does:

# 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 is redrawn with prob p
labels[mask] = np.random.choice(10, mask.sum())  # uniform class, may repeat
# then train exactly as usual: same net, same SGD, same schedule
# CIFAR10, p = 1: 100% train accuracy, ~10% test accuracy (chance)

On CIFAR10 every architecture fits random labels: training accuracy is 100% for Inception, 100% for Inception without batch normalization, 99.82% for Alexnet, 100% for MLP 3x512 and 99.34% for MLP 1x512. Test accuracy is 9.78%, 10.12%, 9.86%, 10.48% and 10.61%, which is chance for ten classes. Each of those networks therefore stores 50,000 arbitrary answers, one per image, with nothing in the images to predict them from. On ImageNet, Inception V3 reaches 95.20% top-1 training accuracy (top-1: the highest-scoring class is the labeled one) on 1,281,167 images with random labels from 1,000 classes, and 0.11% top-1 test accuracy, again with no hyperparameter change; the authors expect a tuned run would reach 100%. Random pixels and Gaussian inputs are fit as well, and start converging sooner than random labels on real images. The paper's tentative explanation is that noise images sit farther apart from one another than natural images of the same class do, so separating them is easier.

Training on random labels follows the same pattern each time. For the first passes over the data the loss stays high: every label is unrelated to its image, so the gradients from different examples conflict. Because the random assignment is fixed, after a few passes the network starts separating images individually, and then the loss falls quickly to zero. The paper lists three observations: the learning-rate schedule did not need to change, convergence is fast once fitting starts, and the fit is perfect; overall, training takes longer by a small constant factor.

Figure 1 runs a scaled-down version of the test in the browser. A ReLU network (each hidden unit outputs max(0, its input)) with two hidden layers of 64 units (4,417 weights, about 44 per training point) trains with full-batch Adam on 100 points in a square, labeled by a wavy boundary. The slider sets $p$; ringed points had their label redrawn, and because there are two classes, about half of the redrawn labels land on the wrong class. Test accuracy is measured on 400 clean points from the same boundary. Start with $p = 0$: the map splits into two regions that follow the boundary in about 150 steps, with test accuracy between 95% and 97%. Then try $p = 1$: the map breaks into islands around individual points, training accuracy still reaches 100%, after roughly a thousand steps, and test accuracy stays near 50%, chance for two classes.

Partly corrupted labels

Between true and random labels lies a continuum, and the paper sweeps it on CIFAR10. With ten classes a redrawn label lands on the original class one time in ten, so on average a fraction $0.9p$ of the training labels is wrong: 45% at $p = 0.5$, 90% at $p = 1$. At every $p$ the networks fit the corrupted training set perfectly. The paper's Figure 1b shows the time to convergence growing with $p$, and Figure 1c shows the test error after convergence rising steadily toward 90%, chance on CIFAR10. Training error is zero throughout, so each test error in Figure 1c is also the generalization gap.

If the networks memorized whenever memorizing was possible, any corruption would push them to memorize everything and test error would jump to chance. Instead the network fits the clean labels through the pattern they share and fits the wrong ones individually, and test error grows with the number of wrong labels. The paper describes this as capturing "the remaining signal in the data" while fitting "the noisy part using brute-force".

Figure 2 runs that sweep on the toy from Figure 1. For each of eleven values of $p$, the network trains until it gets every training label right. The left panel shows how many steps that took, on a log scale; the right panel shows the clean test error at that moment, next to the share of training labels that are wrong (5 of 100 at $p = 0.1$, 30 at $p = 0.6$, 49 at $p = 1$). Look for two things. Test error rises with the wrong-label share, from about 3% at $p = 0$ to about 50% at $p = 1$, and stays within 12 points of that share at every $p$. For the three recorded seeds the step count rises from about 130 at $p = 0$ to between 660 and 1,070 at $p = 1$. It is noisy from seed to seed: in this toy the slowest fits come at $p$ = 0.8 to 0.9, and some fresh seeds run out of the 6,000-step budget at high $p$, short of a perfect fit, whereas in the paper's CIFAR10 sweep every network fit the corrupted training set perfectly at every $p$.

Why Rademacher, VC and stability bounds fail

The paper argues that the randomization result rules out VC dimension, Rademacher complexity and uniform stability as explanations, because each assigns the same value to the 89%-test run and the 10%-test run. Start with Rademacher complexity. The empirical Rademacher complexity of a family $\mathcal{H}$ on the training inputs $x_1, \dots, x_n$ is the paper's equation (1):

Computing it takes four steps: draw a random sign $\sigma_i$ for every training input, find the function in the family whose outputs agree best with those signs, record the average agreement $\tfrac{1}{n}\sum_i \sigma_i h(x_i)$, and average that over many draws. For classifiers with outputs in $\{\pm 1\}$, each term $\sigma_i h(x_i)$ is $+1$ for a match and $-1$ for a miss, so the value lies between 0 and 1. It enters a bound of the form

which holds with probability at least $1 - \delta$ over the draw of the training set. The random signs are random binary labels, so equation (1) is itself a randomization test, run over the whole family instead of through one training run. Suppose a family can fit every labeling of the $n$ training inputs. Then for every draw of signs some $h$ has $h(x_i) = \sigma_i$ at every one of the $n$ points, the supremum is exactly 1, and $\hat{\mathfrak{R}}_n(\mathcal{H}) = 1$. The bound becomes test error $\le$ training error $+\,2$, which every classifier satisfies. The networks in the paper fit random labels, so the paper concludes $\hat{\mathfrak{R}}_n \approx 1$ for them and calls it a trivial upper bound. The experiments are multiclass, but keeping any two of the ten classes gives the binary version with the same outcome.

Figure 3 computes equation (1) exactly for a family where the best fit 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 holds only the two constant functions, and the complexity is the expected absolute value of the average of $n$ random signs, about $\sqrt{2/(\pi n)}$, which is 0.14 at $n = 32$. Raising $n$ at fixed $k$ pushes the value down, which is what a useful bound needs. Raising $k$ to $n - 1$ pushes it to exactly 1, because a sequence of $n$ signs changes sign at most $n - 1$ times and can then be matched point for point.

VC dimension and its real-valued analogue, the fat-shattering dimension, fail the same way: the networks shatter their training sets (label them every possible way), so a bound built on the dimension of the whole family says nothing at these sample sizes. The known way around size-based bounds was Bartlett's 1998 result, which bounds the fat-shattering dimension through the $\ell_1$ norm of the weights into each unit instead of through the number of weights. 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 extended the idea to other norms in 2015; the authors report that those bounds do not explain the behavior they observe either. The paper adds that all of these fail "unless we further restrict the network", and the experiments show the trained networks are not restricted in that way.

Uniform stability bounds the algorithm instead. An algorithm is $\beta$-uniformly stable if, for every training set, replacing any one training example changes the loss of the returned function by at most $\beta$ at every test point. Bousquet and Elisseeff showed that the expected gap between test and training loss is then at most $2\beta$. Hardt, Recht and Singer showed in 2016 that SGD is uniformly stable with a $\beta$ that grows with the number of steps, for convex and for non-convex losses. The definition takes the worst case over all training sets, so one $\beta$ has to cover the true-label run and the random-label run alike: same algorithm, same number of steps, same learning rate. Measure loss as 0-1 error. The random-label Inception run has a gap of 100 − 9.78 = 90.22 points, so $2\beta \ge 0.90$ and any valid $\beta$ for that training procedure is at least 0.45. A bound of 0.90 says nothing about the true-label run, whose gap is 10.95 points. The paper draws the same conclusion for Hardt, Recht and Singer's analysis: in the non-convex case it covered only a few passes over the data, because SGD trained for many passes is empirically not uniformly stable, and a weaker notion of stability that can see the labels is needed to go further.

What regularization contributes

If the model family is too large to explain the gap, the remaining candidate is regularization. Classically, a regularizer shrinks the set of functions training can reach: penalize the norm of the weights and the Rademacher complexity of the reachable set drops. The paper tests three explicit regularizers by turning them off. Data augmentation: random crops on CIFAR10, plus brightness, saturation, hue and contrast perturbations on ImageNet. Weight decay: an $\ell_2$ penalty on the weights, which the paper treats as equivalent to constraining them to a Euclidean ball (see the AdamW explainer for how the penalty and the decay differ under adaptive optimizers). Dropout: each unit of a layer's output is zeroed with a fixed probability during training; only Inception V3 on ImageNet uses it here.

Figure 4 holds every number from Tables 1, 2 and 4 of the paper. Start with Inception and switch both regularizers off: test accuracy goes from 89.05% to 85.75%. Alexnet goes from 81.22% to 76.07%, MLP 3x512 from 53.35% to 52.39%. On CIFAR10 the regularizers are worth 1 to 5 points, and every model stays far above the 10% chance rate without them. On ImageNet the effect is larger: Inception V3 drops from 77.84% top-1 with augmentation, dropout and weight decay to 59.80% with none, 18 percentage points, against a chance rate of 0.1%. Augmentation alone recovers most of it (72.95%), more than either norm penalty. The paper also compares the unregularized Inception V3 (80.38% top-5, meaning the labeled class is among the five highest-scoring) with the ILSVRC 2012 winner, Alexnet with all its regularization (83.6% top-5), to argue that a change of architecture bought more than the regularizers did.

Turning regularizers on does not prevent 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, the one exception. With random cropping Inception reaches 99.93% and with augmentation 99.28%. Those two numbers are averages of online mini-batch accuracy, measured on augmented images that change every epoch while each image's random label stays fixed; reaching them took a slower learning-rate decay 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 summary is that explicit regularization "may improve generalization performance, but is neither necessary nor by itself sufficient". It acts like a tuning parameter, whereas in convex empirical risk minimization a regularizer is needed to rule out the trivial solutions that fit the training set and nothing else.

Two implicit regularizers get the same treatment. Early stopping: Table 2 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 on ImageNet stopping early could have helped, with the caveat the paper itself gives: picking the stopping point by test accuracy is only legitimate with a separate validation set. On CIFAR10 the paper sees no benefit. Batch normalization: an Inception with every batch-norm layer removed trains less stably and ends at 82.00% instead of 85.75% with no other regularizers, a 3 to 4 point effect, and still fits random labels at 100%.

Theorem 1: 2n + d weights fit any labels

The experiments show that these particular networks can memorize. The paper's theorem asks how little a network needs to do so. Classical expressivity results concern the whole input space: which functions on $\mathbb{R}^d$ a family can approximate, and how much depth helps. The paper asks a finite-sample question instead. Given $n$ distinct points $S \subset \mathbb{R}^d$ and any target values on them, is there a weight setting whose output matches every target exactly?

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

The network is

with one vector $a$ shared by all $n$ hidden units, $n$ thresholds $b_j$ and $n$ output weights $w_j$: $d + n + n$ numbers in total.

The proof has three steps. First, project every sample to a scalar, $x_i = \langle a, z_i \rangle$. The $z_i$ are distinct, so almost every $a$ gives distinct projections; relabel the points so that $x_1 < x_2 < \dots < x_n$. Second, place the thresholds between the points, $b_1 < x_1 < b_2 < x_2 < \dots < b_n < x_n$. Hidden unit $j$ then outputs 0 at every point left of $b_j$ and the positive number $x_i - b_j$ at every point right of it, so the matrix of hidden activations on the sample,

is lower triangular ($A_{ij} = 0$ whenever $j > i$, because $b_j$ lies right of $x_i$) with diagonal entries $x_i - b_i > 0$. Third, the network's outputs on the sample are $c(z_i) = (Aw)_i$, so matching targets $y_i$ means solving 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 the eigenvalues of $A$ are its diagonal entries, so the smallest is $\min_i (x_i - b_i)$. Forward substitution finds $w$ one entry at a time. The targets were arbitrary, so every labeling of the sample is reachable. For three points the construction runs as follows:

# Theorem 1 with n = 3 points, d = 1 (so <a, z> = z)
x = [0.20, 0.50, 0.90]          # projected inputs, sorted
b = [0.05, 0.35, 0.70]          # thresholds: b1 < x1 < b2 < x2 < b3 < x3
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)

Forward substitution in this example goes row by row: $w_1 = 1/0.15 = 6.667$; row two needs $0.45 \cdot 6.667 + 0.15\, w_2 = -1$, so $w_2 = -26.667$; row three gives $w_3 = 47.5$. The weights alternate in sign and grow, because each new ramp has to cancel the slope the earlier ramps built up before it can set its own target. Small diagonal gaps $x_i - b_i$ make the weights larger, which is why the paper points to the smallest eigenvalue of Lemma 1 as the route to a bound on the weights. In Figure 5, drag a target and watch the ramps re-solve.

For CIFAR10 the construction needs $2 \cdot 50{,}000 + 2352 = 102{,}352$ weights, and the smallest network in the paper has 1,209,866, about 11.8 times as many. For ImageNet it needs $2 \cdot 1{,}281{,}167 + 268{,}203$, about 2.83 million. The theorem is existential: it builds one specific network that can fit any labeling, and it does not show that the paper's Inception or Alexnet can. That they can is the experimental result. The theorem shows that memorization needs only a number of weights linear in $n$ and a very simple architecture, so a count of weights alone cannot rule it out.

The paper credits Livni, Shalev-Shwartz and Shamir with an earlier construction that needed $O(dn)$ parameters. Its Corollary 1 trades width 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. The construction splits the projected axis into $m$ intervals (the paper calls their number $b$), fits each interval's points at its own layer, and adds a multiplexer of approximate indicator functions that routes each input to the right layer's output.

Linear models and the minimum-norm fit

So the family contains functions that memorize, the experiments show that SGD finds one when the labels are random, and yet on real labels it finds one that generalizes. Whatever selects among perfect fits has to come from the optimizer. The paper studies that selection in the simplest setting where it 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 (minimize the average training loss)

Stack the inputs as the rows of an $n \times d$ matrix $X$. If $X$ has rank $n$, which requires $d \ge n$, the system $Xw = y$ has infinitely many solutions for every $y$, and each one drives (2) to zero. The linear model can then fit any labeling, the same position the networks are in. With $d = 3$ features and $n = 2$ examples, for instance, the solutions of $Xw = y$ form a line in $\mathbb{R}^3$, and any point on it fits both examples exactly.

A common heuristic says flat minima generalize better than sharp ones, so the first thing to check is the curvature. At any zero-loss solution the Hessian of (2) is

The chain rule gives $\tfrac{1}{n}X^{\top}\mathrm{diag}(\beta)X$ at any $w$, with each $\beta_i$ evaluated at the current prediction $w^{\top}x_i$. At a zero-loss solution every prediction equals its label, so every $\beta_i$ is evaluated at $z = y_i$ regardless of which solution $w$ is. The Hessian is therefore the same matrix at every global minimum, and its rank is at most $n < d$, so it is degenerate at every one of them and curvature cannot tell these minima apart.

SGD started from zero picks one of them in a definite way. One SGD step 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$. Each step adds a multiple of one input vector, so starting from $w_0 = 0$ the iterate always lies in the span of the inputs, $w = \sum_i \alpha_i x_i = X^{\top} \alpha$ for some coefficients $\alpha$. If the run also fits the labels, $Xw = y$, substituting the first identity into the second gives

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, reached here (in the paper's words, "in a roundabout fashion") through the optimizer. The solution it picks is $w = X^{\top} (XX^{\top})^{-1} y = X^{+} y$, the pseudoinverse solution. Any other interpolant is $X^{+}y + v$ with $Xv = 0$. That $v$ is orthogonal to every row of $X$, hence to $X^{+}y$, which lies in the row space, so

and among all zero-loss solutions, SGD started from zero returns the one with the smallest $\ell_2$ norm. The paper calls this implicit regularization: nobody wrote a norm penalty into (2), and the algorithm returned the minimum-norm solution anyway.

Figure 6 draws the smallest case, one training point and two weights. The dashed amber line is every $w$ with $w \cdot x = y$. The faint bands parallel to it are level sets of the squared loss: the valley floor is flat along the line, which is the identical-Hessian statement above. 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 keeps the component $v$ of the start that is orthogonal to $x$. From the origin, $v = 0$ and the landing is the foot of the perpendicular, where the smallest circle around the origin touches the line. Drag the start elsewhere and the landing moves to a different interpolant with a larger norm, the same zero loss, and a different prediction on the test input.

Equation (3) also makes the experiment cheap to run on real data: solve it directly, with no regularizer, and measure 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, and with a Gabor wavelet transform applied first, 0.6%. Adding regularization improves neither. On CIFAR10 a Gaussian kernel on pixels gets 46% test error. Preprocessing with a random convolutional network of 32,000 random filters (the Coates and Ng architecture with random filters in place of k-means ones) gets 17%, and an $\ell_2$ penalty brings that to 15%, with no data augmentation. These are all exact interpolants of a convex problem, and some of them generalize well.

The paper then asks whether a small norm predicts good generalization, and finds that it does not, or not reliably. Interpolants that generalize badly are easy to build: a Gaussian kernel with centers at random points, or a solution forced to fit random labels on the test set as well. Both have much larger norms than the minimum-norm solution. But on MNIST the minimum-norm solution on raw pixels has norm about 220 and 1.2% error, while the one on wavelet features has norm about 390 and 0.6% error: the norm went up and the error halved. The authors conclude that minimum norm may guide algorithm design and is "only a very small piece of the generalization story".

What the paper settles and leaves open

The paper defines effective capacity as 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, so the effective capacity of these networks is "large enough to shatter the training data". 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 conclusion concerns optimization: fitting random labels costs only a small constant factor in training time, so the reason SGD converges easily on these problems must differ from the reason the result generalizes.

Three stronger claims are not in the paper. It does not claim networks memorize real data instead of learning from it; the partial-corruption sweep shows both happening at once, and Arpit and colleagues showed in 2017 that networks trained on noisy data fit the simple, shared patterns first. It does not claim regularizers are useless; on ImageNet they are worth 18 points. It does not claim the minimum-norm bias explains generalization; Section 5 gives the MNIST counterexample. It does claim that a correct theory needs a measure of complexity under which these enormous models are simple, and that in 2017 nobody had found one.

Later work has mostly confirmed the negative result. Nagarajan and Kolter showed in 2019 that uniform-convergence bounds, including ones that account for the implicit bias of gradient descent, can be vacuous for networks that generalize, and can even grow with the size of 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 places the paper's kernel experiments in a broader pattern. Soudry and colleagues showed in 2018 that the implicit bias depends on the loss: on separable data, gradient descent on the logistic loss converges in direction to the maximum-margin classifier while the norm grows without bound, so the minimum-norm result of Section 5 is specific to the squared loss and a zero start. The lottery ticket hypothesis asks a related question about what over-parameterized training finds, in terms of sparse subnetworks. In 2021 the authors republished the paper in Communications of the ACM as "Understanding deep learning (still) requires rethinking generalization".