How Optimization Dynamics Drive Generalization in Over-parameterized Models — Epoche C2
The experiment that made capacity an inadequate explanation A small Inception-style convolutional network of roughly 1.6 million parameters, trained on the 50,000 images of CIFAR-10 with every label replaced by a class drawn uniformly at random, reaches zero training error. Chiyuan Zhang and colleagues reported this in 2017, together with the corollary that the same architecture and the same optimiser, trained on the true labels, generalises about as well as anything else of its size. Roughly 32 parameters per training example is enough to memorise an arbitrary assignment of 50,000 labels, and the network duly does so. This is the fact that everything below exists to accommodate. What it rules out is a whole style of explanation, and the reason is worth stating rather than gesturing at. Any generalisation bound of the shape $$ R(h) \ \le \ \hat{R}_S(h) \ + \ \mathfrak{R}_S(\mathcal{H}) \ + \ O\!\left(\sqrt{\frac{\log(1/\delta)}{n}}\right) $$ controls the true risk $R(h)$ by the empirical risk $\hat{R}_S(h)$ plus a term measuring the richness of the whole hypothesis class $\mathcal{H}$ on the sample $S$. If $\mathcal{H}$ can realise every labelling of $S$ — which is exactly what the random-label experiment demonstrates — then its empirical Rademacher complexity $\mathfrak{R}_S(\mathcal{H})$ is $1$, and the right-hand side exceeds $1$ while the risk it bounds can never exceed $1$. The bound is vacuous, and so is every bound of that form, whatever complexity measure is substituted, because they all depend on the class and not on which member of it was selected. Zhang and colleagues added a second observation with the same moral: weight decay, dropout and data augmentation change test error by a couple of percentage points and do not prevent the network from fitting random labels, so explicit regularisation is neither necessary nor sufficient for the generalisation observed. The selection must therefore be doing the work, and the only thing that selects is the optimiser. The claim of this essay is that the dynamics of optimisation, not the capacity of the model, determine which of the many zero-training-error solutions is reached, and that the classical intuition about flat minima is a partly correct description of that mechanism which needs three corrections before it can be relied on. Why flatness was ever expected to matter Before correcting the flat-minima account it is necessary to say what argument it rests on, because the version usually given — that a flat minimum is robust to perturbation and therefore transfers better — is a restatement rather than a reason. The loss landscape is the graph of the training loss $L$ over parameter space. A minimiser $\theta^*$ is called sharp when the loss rises quickly for small displacements and flat when it does not, and the curvature at the minimum is summarised by the eigenvalues of the Hessian, the largest of which gives $$ S(\theta^*) \ = \ \max_i \lambda_i\!\left(\nabla^2 L(\theta^*)\right). $$ The argument that this should matter is due to Sepp Hochreiter and Jürgen Schmidhuber in 1997, and it is a description-length argument rather than an appeal to robustness. A flat minimum occupies a large region of weight space on which the loss remains low; a learner therefore need only specify its weights precisely enough to land somewhere inside that region, and the number of bits required is the logarithm of the ratio between the volume available a priori and the volume of the region. Minimum description length then converts short codes into generalisation guarantees. The quantitative force is easy to see: a box of half-width $\delta$ in each of $d$ coordinates has volume $(2\delta)^d$, so doubling the tolerable displacement in every coordinate multiplies the volume by $2^d$ and saves exactly $d$ bits. For a network with $d = 10^6$ parameters that is $10^6$ bits, or 125 kilobytes, removed from the description length by a factor of two in permitted slack. Hochreiter and Schmidhuber built an algorithm, Flat Minimum Search, around a penalty approximating the logarithm of that volume. Note carefully what the argument needs: a volume . Curvature at the minimum enters only as a local proxy for volume, and the difference between the two is where the first correction comes from. First correction: the sharpness formula is not a property of the function The displayed quantity $S(\theta^*)$ was presented in the earlier version of this essay as though it measured something about the trained model. It does not, and the demonstration is a two-line computation that Laurent Dinh, Razvan Pascanu, Samy Bengio and Yoshua Bengio published in 2017. Take a two-layer rectified network $f(x) = \theta_2\,\mathrm{ReLU}(\theta_1 x)$. Because the rectifier is positively homogeneous, $\mathrm{ReLU}(\alpha z) = \alpha\,\mathrm{ReLU}(z)$ for every $\alpha \gt 0$, the reparameterisation $(\theta_1, \theta_2) \mapsto (\alpha\theta_1, \alpha^{-1}\theta_2)$ leaves the input-output map exactly unchanged. Training loss, test loss and generalisation gap are therefore all unchanged along this orbit. The Hessian is not. Writing $\tilde{\theta}_2 = \alpha^{-1}\theta_2$ for the new second-layer coordinate, we have $\partial/\partial\tilde{\theta}_2 = \alpha\,\partial/\partial\theta_2$, so second derivatives in that block are multiplied by $\alpha^2$, while those in the first-layer block are multiplied by $\alpha^{-2}$. Letting $\alpha$ grow sends $S(\theta^*)$ to infinity along a path on which nothing observable about the model changes at all. The consequence is not cosmetic. The proposition "flat minima generalise better" is not well posed until the parameterisation is fixed, because for rectified networks the sharpness of a given function can be set to any value one likes. What survives is the description-length argument, but only if one is careful: the volume it requires is measured against a prior over weights, and the rescaling changes the region and the prior together. The invariance