### Why do neural networks generalize well?

One of the most important outstanding theoretical issues in machine learning today is explaining generalization in deep neural networks. Despite the fact that these models sometimes contain several orders of magnitude more parameters than the number of data points they are trained on, they do not seem to overfit the data easily and they are able to generalize successfully to new data. This highly over-parametrized regime makes the generalization error bounds derived with standard tools in statistical learning theory mostly vacuous. So, coming up with new theoretical ideas that can give non-vacuous quantitative bounds on the generalization performance of deep neural networks has been a top priority in theoretical machine learning in recent years.

There is a fair amount of empirical observation in the literature on what makes a neural network generalize better or worse. These empirical observations typically report significant correlations between the generalization performance of models on a test set and some measure of their noise robustness or degeneracy. For example, Morcos et al. (2018) observe that models that generalize better are less sensitive to perturbations in randomly selected directions in the network’s activity space. Similarly, Novak et al. (2018) observe that models that generalize better have smaller mean Jacobian norms, , than models that don’t generalize well. The Jacobian norm at a given point can be considered as an estimate of the average sensitivity of the model to perturbations around that point. So, similar to Morcos et al.’s observation, this result amounts to a correlation between the model’s generalization performance and a particular measure of its noise robustness. Wu et al. (2017) observe that models that generalize better have smaller Hessian norms (Frobenius) than models that don’t generalize well. The Hessian norm can be considered as a measure of the total degeneracy of the model, i.e. the flatness of the loss landscape around the solution. Hence this result is in line with earlier hypotheses (by Hochreiter & Schmidhuber and by Hinton & Van Camp) about a possible connection between the generalization capacity of neural networks and the local flatness of the loss landscape. For two-layer shallow networks, Wu et al. also establish a link between the noise robustness of the models as measured by their mean Jacobian norm and the local flatness of the loss landscape as measured by the Hessian norm (in a nutshell, under some fairly plausible assumptions, the mean Jacobian norm can be upper-bounded by the Hessian norm -see Corollary 1 in the paper-).

Although these observations are all informative, they do not provide a rigorous quantitative explanation for why heavily over-parametrized neural networks generalize as well as they do in practice. Such an explanation would take the form of a rigorous quantitative bound on the generalization error of a model given what we know about the model’s various properties. As I mentioned above, standard theoretical tools have so far not been able to yield non-vacuous, i.e. meaningful, bounds on generalization error for models operating in the highly over-parametrized regime.

In this post, I’d like to highlight a recent paper by Wenda Zhou and colleagues that was able to derive non-vacuous generalization error bounds for ImageNet-scale models for the first time. Following prior work by Dziugaite & Roy, their starting point is PAC-Bayes theory. They leverage the compressibility of the trained deep neural nets to derive a non-vacuous (but still very loose) PAC-Bayes bound on the generalization error of large-scale image recognition models.

Roughly speaking, PAC-Bayes theory gives bounds on the generalization error that are of the following form: , where is the number of training points, is a data-dependent posterior distribution over the “hypotheses” (think of a distribution over neural network parameters) specific to a learning algorithm and training data and is a data-independent prior distribution over the hypotheses. The main challenge in coming up with useful bounds in this framework is finding a good prior that would minimize the -divergence between the prior and the posterior in the bound. This basically requires guessing what kinds of structure are favored by the training algorithm, training data and model class we happen to use (previously, Dziugaite & Roy had directly minimized the PAC-Bayes bound with respect to *the posterior distribution *instead of guessing an appropriate prior, assuming a Gaussian form with diagonal covariance for the posterior, and came up with non-vacuous and fairly tight bounds for MNIST models. Although this is a clever idea, it obscures which properties of trained neural nets specifically lead to better generalization).

The main idea in the paper by Wenda Zhou and colleagues is to choose such that greater probability mass is assigned to models with short code length, i.e. more compressible models. This implicitly expresses the hypothesis that neural networks trained with SGD on real-world datasets are more likely to yield compressible solutions. When we choose and , where denotes the number of bits required to describe the model according to some pre-specified compression scheme and denotes the compressed version of the trained model, we get a bound like the following (Theorem 4.1 simplified):

This means that the more compressible the model is, the better the generalization error bound will be. The authors then refine this bound by making the compression scheme more explicit and also incorporating the noise robustness property of the trained networks into the bound. I won’t go into those details here, but definitely do check out the paper if you are interested. They then apply a state-of-the-art compression method (based on dynamic network surgery) to pre-trained deep networks to instantiate the bound. This gives non-vacuous but still very loose bounds for models trained on both MNIST and ImageNet. For example, for ImageNet, they obtain a top-1 error bound of , whereas their compressed model achieves an actual error of on the validation data.

So, although it is encouraging to get a non-vacuous bound for an ImageNet model for the first time, there is still a frustratingly large gap between the actual generalization performance of the model and the derived bound, i.e. the bounds are nowhere near tight. Why is this? There are two possibilities as I see it:

- The authors’ approach of using a PAC-Bayes bound based on compression is on the right track, however the current compression algorithms are not as good as they can be, hence the bounds are not as tight as they can be. If true, this would be a practically exciting possibility, since it suggests that a few orders of magnitude better compression can be achieved with better compression methods currently not yet available.
- Just exploiting compression (or compression + noise robustness) will not be enough to construct a tight PAC-Bayes bound. We have to incorporate more specific properties of the trained neural networks that generalize well in order to come up with a better prior .

The second possibility would imply the existence of models that have similar training errors and are compressible to a similar extent, yet have quite different generalization errors. I’m not aware of any reports of such models, but it would be interesting to test this hypothesis.