The Geometry of Generalization in Deep Learning — Epoche C2
The claim, and the experiment that made it necessary The claim examined here is that a massively overparameterised neural network generalises because the optimiser lands it in a flat minimum of the training loss — a point around which the loss surface is nearly level in every direction — and not because having more parameters than data points somehow makes the fitting problem benign. The claim is now standard equipment, and it is usually stated without the argument that would give it content — or the objection that shows it, in its usual form, to be not even well posed. The fact that forced the question was reported by Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht and Oriol Vinyals in 2017. They took standard image architectures and trained them on the fifty thousand images of CIFAR-10 after replacing every label with an independent draw from the uniform distribution over the ten classes. The networks reached zero training error. They did so again when the pixels of each image were scrambled by a fixed random permutation, and again when the images themselves were replaced by Gaussian noise. Fitting the random labels took a modest constant factor more epochs than fitting the true ones; nothing else changed. The consequence is a statement about capacity, and it is worth doing rather than gesturing at. Let $\mathcal{H}$ be the set of functions the architecture can realise, $S = (x_1,\dots,x_m)$ the training inputs with $m = 50{,}000$, and let the empirical Rademacher complexity be $$ \hat{\mathfrak{R}}_S(\mathcal{H}) = \mathbb{E}_{\sigma}\left[\sup_{h \in \mathcal{H}} \frac{1}{m}\sum_{i=1}^{m}\sigma_i h(x_i)\right], $$ the expectation taken over independent signs $\sigma_i$ uniform on $\{-1,+1\}$: the extent to which the class can correlate with pure noise on this particular sample. If for essentially any assignment of labels there is a member of the class matching it, the supremum is attained at nearly $1$ for nearly every draw, so $\hat{\mathfrak{R}}_S(\mathcal{H}) \approx 1$. Writing $\hat{L}_S$ for the average loss on the sample and $L_{\mathcal{D}}$ for the expected loss on the data distribution, the standard uniform-convergence bound for losses taking values in $[0,1]$ then reads, with probability at least $1-\delta$ over the sample and simultaneously for every $h \in \mathcal{H}$, $$ L_{\mathcal{D}}(h) \;\le\; \hat{L}_S(h) + 2\hat{\mathfrak{R}}_S(\mathcal{H}) + 3\sqrt{\frac{\ln(2/\delta)}{2m}}, $$ which for $\hat{\mathfrak{R}}_S \approx 1$ certifies a risk of at least $2$. Since the risk of the worst possible classifier is $1$, the bound is not merely loose; it carries no information at all. The same verdict applies to any bound whose capacity term is a property of the hypothesis class as a whole. The diagnosis is in the words "simultaneously for every $h$". Uniform-convergence bounds insure against the worst member of the class, and the trained network is not the worst member; it is the one stochastic gradient descent produced from that data. Any explanation of its behaviour must therefore mention the algorithm and where the algorithm goes — which is what recommends a geometric account, since the geometry of the loss surface determines where an optimiser can come to rest. Flatness made precise, and a step the compressed version got wrong Write $L(\theta)$ for the training loss with $\theta \in \mathbb{R}^d$ the vector of all weights, and let $\theta^*$ be a minimum with Hessian $H = \nabla^2 L(\theta^*)$. The minimum is flat when the eigenvalues of $H$ are small, so the loss rises slowly in every direction, and sharp when some are large, so a small displacement of the weights is expensive. The second-order expansion around the minimum is $$ L(\theta^* + \delta\theta) \approx L(\theta^*) + \nabla L(\theta^*)^T \delta\theta + \frac{1}{2} \delta\theta^T H \delta\theta , $$ and since $\nabla L(\theta^*) = 0$ the increase is governed entirely by the quadratic form $\frac{1}{2}\delta\theta^T H \delta\theta$, which for a flat minimum is small even for a displacement $\delta\theta$ of appreciable size. Here the compressed version of this essay took a step that does not follow, and it is worth naming because the same step is common in the literature's informal register. It said that a model at a sharp minimum is sensitive to noise in the inputs and to shifts in the data distribution, citing the expansion above in support. But $\delta\theta$ is a displacement of the weights . The expansion says nothing about a perturbation of the input $x$, which is governed by the derivatives of the network with respect to $x$, nor about a shift in the distribution, which is not a perturbation of the model at all. Flatness in parameter space and robustness in input space are different properties, and neither implies the other. What is needed instead is an argument in which a perturbation of the weights is exactly the right object — and there are two, both older than the current interest in the topic. Two arguments in which weight perturbations are the right object The first is a coding argument, and it is the origin of the term. Sepp Hochreiter and Jürgen Schmidhuber, in 1997, defined a flat minimum as a large connected region of weight space throughout which the training error stays approximately constant, and observed that such a region is cheap to describe: specifying a weight vector only to within a box of side $2\epsilon_i$ in coordinate $i$ saves about $-\log_2 \epsilon_i$ bits, and a flat region permits large $\epsilon_i$. Under a minimum-description-length reading of induction, the hypothesis needing fewest bits — for the weights as well as for the residual errors — is the one to prefer, and they turned this into a training objective, computing the admissible box size from second derivatives. Two features matter later: the box is axis-aligned in weight space, and its size is measured in the units the weights happen to be written in. The second argument is a bound. The PAC-Bayes theorem, in