Symptom

You train a ResNet with 25 million parameters on 50,000 CIFAR-10 images. It reaches zero training error and 94% test accuracy.

Then you compute the bound. The network’s VC dimension is somewhere around the parameter count, so the sample complexity term $\sqrt{d/m}$ is $\sqrt{25 \times 10^6 / 5 \times 10^4} \approx 22$. The bound says test error is at most training error plus 22, that is, at most 2200%.

This is not a loose bound. It is not a bound at all: any number in $[0,1]$ satisfies it. The theory is correct — every hypothesis of the fundamental theorem holds — and it is telling you nothing whatsoever about the object in front of you, which is working.

That gap is the most honest open problem in practical machine learning, and it is worth being precise about what is and is not known, because this is the one theoretical topic working programmers are actually taught and the folk version of it is wrong.

Statement

Two results, one classical and one experimental, and the tension between them is the post.

Universal approximation (Cybenko 1989; Hornik 1991). A feedforward network with one hidden layer and a non-polynomial activation can approximate any continuous function on a compact set to arbitrary accuracy, given enough hidden units.

Zhang et al. (2017), the random-label experiment. Take a standard image network that generalises well. Replace every training label with a uniformly random one. Train with the identical architecture, optimiser, and regularisation.

It still reaches zero training error. Convergence takes only a small constant factor longer. The same holds with the images replaced by Gaussian noise. Explicit regularisation — weight decay, dropout, augmentation — changes test accuracy by a few points and does not prevent memorisation.

The consequence is a proof by construction. The network’s effective capacity is large enough to shatter the training set, so any bound of the form “test error $\le$ training error $+ \phi(\text{capacity}, m)$” that depends only on the model class and the sample size must be vacuous — because the identical class and sample size also fit pure noise, where test error is necessarily 90%.

Argument

Universal approximation first, since it is the standard non-answer. It says the class is rich enough to contain a good function. It says nothing about how many units are needed (possibly exponential in the input dimension), nothing about whether gradient descent finds that function, and nothing about generalisation. Indeed it makes the puzzle worse: the class also contains every bad function that fits the data. A capacity result cannot explain generalisation, because generalisation is the claim that capacity went unused.

Why the random-label result is decisive. Suppose you propose an explanation of the form “networks generalise because their capacity is limited by $C$”, for any $C$ computed from architecture, parameter count, norm at initialisation, or sample size. The experiment fixes all of those and produces both a generalising model and a memorising one. So $C$ cannot distinguish them, and no bound depending only on $C$ can be tight. One experiment, every uniform-convergence explanation ruled out simultaneously.

Where the explanation has to live, then: in the interaction between the algorithm, the data, and the class — not in the class alone. The leading candidates, and their honest status:

  • Implicit regularisation by SGD. Gradient descent does not return an arbitrary zero-error solution; it returns a particular one. For separable linear models this is proved: gradient descent on logistic loss converges in direction to the maximum-margin solution, with no explicit regulariser (Soudry et al. 2018). For deep networks the analogous statement is conjectural.
  • Flat minima. Solutions in wide, flat basins of the loss surface generalise better than sharp ones, and large-batch training finds sharper ones. The correlation is robust; the definition of flatness is not reparameterisation- invariant, which is a real objection (Dinh et al. 2017).
  • Norm-based and margin-based bounds. Replace parameter count with a product of layer norms divided by margin. These give non-vacuous numbers on some real networks, and they degrade badly with depth.
  • PAC-Bayes compression bounds. The most successful line: Dziugaite and Roy (2017) computed a non-vacuous bound — around 16% error — for a network trained on MNIST, by optimising a PAC-Bayes bound over a distribution around the found solution. This is an existence proof that the gap is closable, and the technique has not yet scaled to modern networks with modern accuracy.
  • Data-dependent structure. Real images are not arbitrary points; they lie near a low-dimensional manifold with strong local structure, and the effective complexity relevant to that distribution is far below the worst case.

Double descent, the other empirical surprise. As you grow model capacity past the point of exactly fitting the training data, test error rises to a peak at that interpolation threshold and then falls again, often below the classical sweet spot (Belkin et al. 2019). The textbook U-curve is the left half of a double-descent curve. This does not contradict the bias–variance identity, which is an identity; it contradicts the folk belief that variance rises monotonically with capacity.

So what should you actually take away? That the theory is not wrong and not useless, but that it answers a different question than the one you have. The fundamental theorem answers what can be guaranteed for the worst distribution. You want to know what will happen on this distribution with this optimiser, and nobody has a general answer. In the absence of one, held-out data is not a fallback, it is the primary instrument, and the theory’s role is to tell you what could invalidate that measurement: distribution shift, test-set reuse, and leakage.

Forbids

Non-vacuous generalisation guarantees for large networks from capacity-only bounds. The random-label experiment rules them out constructively. Any such bound is either loose to the point of meaninglessness or uses information beyond the class and sample size.

Explaining generalisation by architecture alone. Same argument. The architecture is held fixed across both outcomes.

Treating “it has fewer parameters” as a generalisation argument. Parameter count is not the operative variable, and double descent shows the relationship is not even monotone.

Assuming your model did not memorise because it could not. It could. Whether it did is an empirical question, answered by held-out data and not by counting parameters.

Does not forbid

It does not mean learning theory is wrong, which is the misreading that sends people to the opposite and equally useless extreme. Every theorem in the previous posts is true, proved, and correctly stated. Their hypotheses hold here. The bounds are worst-case over distributions, and reality is not the worst case. A vacuous bound is a bound whose hypotheses are too weak, not one that is false.

It does not mean generalisation is unexplained in principle. Non-vacuous PAC-Bayes bounds exist for real networks. The gap is being closed, slowly, by bounds that use properties of the found solution rather than of the class.

It does not mean regularisation is pointless. Weight decay, dropout, and augmentation each buy a few points of test accuracy, reliably. Zhang et al. show they do not explain generalisation, since memorisation survives them. Those are different claims and the paper is careful about the distinction.

It does not mean big models always generalise. They generalise on data with structure. Fed noise, they memorise it perfectly and generalise not at all, which is the experiment. The structure of the data is a necessary ingredient in every candidate explanation.

It does not license ignoring sample size. More data still helps, monotonically and substantially. The theory’s qualitative guidance — more data, better matched inductive bias, held-out evaluation — survives intact. It is the quantitative bound that fails.

Boundary

  • This is a live research area and any summary ages. The candidate explanations above are current as of writing and several may be superseded. The experimental facts are stable; the explanations are not.
  • “Vacuous” has a precise meaning: the bound exceeds the trivial bound of 1 on the error. Some bounds are merely very loose, which is different and sometimes still useful for ranking models.
  • The random-label result is about supervised classification on standard vision benchmarks. Its scope is narrower than the sweeping conclusions drawn from it, including some in this post.
  • Uniform convergence may be the wrong tool entirely. Nagarajan and Kolter (2019) argue that any uniform-convergence bound must be vacuous in these regimes, which if right means the fix is a different framework rather than a tighter bound.
  • None of this gives you a number you can act on. There is no procedure here that predicts test error better than a held-out set, and it is worth being clear that the practical answer remains measurement.

The honest position: we have a theory that explains why learning is possible and no theory that explains why our best method works. That is an unusual place for an engineering field to be, and it is worth knowing you are standing in it rather than assuming the textbook covered it.