Deep neural networks (DNNs) generalize remarkably well without explicit regularization even in the strongly over-parametrized regime  where classical learning theory would instead predict that they would severely overfit.   While many proposals for some kind of implicit regularization have been made to rationalise this success, there is no consensus for the fundamental reason why DNNs do not strongly overfit.   In this paper, we provide a new explanation. By applying a very general probability-complexity bound recently derived from  algorithmic information theory (AIT), we argue that the parameter-function map of many DNNs should be exponentially biased towards simple functions. We then provide clear evidence for this strong simplicity bias in a model DNN for Boolean functions, as well as in much larger fully connected and convolutional networks trained on CIFAR10 and MNIST.
 As the target functions in many real problems are expected to be highly structured, this intrinsic simplicity bias helps explain why deep networks generalize well on real world problems.
 This picture also facilitates a novel PAC-Bayes approach where the prior is taken over the DNN input-output function space, rather than  the more conventional prior over parameter space.   If we assume that the training algorithm samples parameters close to uniformly within the zero-error region then the PAC-Bayes theorem can be used to guarantee good expected generalization for target functions producing high-likelihood training sets.   By exploiting recently discovered connections between DNNs and Gaussian processes to estimate the marginal likelihood,  we produce relatively tight generalization PAC-Bayes error bounds which correlate well with the true error on realistic datasets such as MNIST and CIFAR10 and for architectures including convolutional and fully connected networks. Deep learning is a machine learning paradigm based on very large, expressive and composable models, which most often require similarly large data sets to train. The name comes from the main component in the models: deep neural networks (DNNs) with many layers of representation. These models have been remarkably successful in domains ranging from image recognition and synthesis, to natural language processing, and reinforcement learning (Mnih et al. (2015) ; LeCun et al. (2015) ; BID7 ; BID12 ). There has been work on understanding the expressive power of certain classes of deep networks ), their learning dynamics BID0 ; ), and generalization properties (Kawaguchi et al. (2017) ; BID5 ; BID1 ). However, a full theoretical understanding of many of these properties is still lacking.DNNs are typically overparametrized, with many more parameters than training examples. Classical learning theory suggests that overparamterized models lead to overfitting, and so poorer generalization performance. By contrast, for deep learning there is good evidence that increasing the number of parameters leads to improved generalization (see e.g. BID2 ). For a typical supervised learning scenario, classical learning theory provides bounds on the generalization error (f ) for target function f that typically scale as the complexity of the hypothesis class H. Complexity measures include simply the number of functions in H, the VC dimension, and the Rademacher complexity BID15 ). Since neural networks are highly expressive, typical measures of C(H) will be extremely large, leading to trivial bounds.Many empirical schemes such as dropout BID18 ), weight decay (Krogh & Hertz (1992) ), early stopping (Morgan & Bourlard (1990) ), have been proposed as sources of regularization that effectively lower C(H). However, in an important recent paper BID27 ), it was explicitly demonstrated that these regularization methods are not necessary to obtain good generalization. Moreover, by randomly labelling images in the well known CIFAR10 data set (Krizhevsky & Hinton (2009) ), these authors showed that DNNs are sufficiently expressive to memorize a data set in not much more time than it takes to train on uncorrupted CIFAR10 data. By showing that it is relatively easy to train DNNs to find functions f that do not generalize at all, this work sharpened the question as to why DNNs generalize so well when presented with uncorrupted training data. This study stimulated much recent work, see e.g. (Kawaguchi et al. (2017) ; Arora et al. (2018) ; Morcos et al. (2018) ; BID1 ; Dziugaite & Roy (2017; ; Neyshabur et al. (2017a; ), but there is no consensus as to why DNNs generalize so well.Because DNNs have so many parameters, minimizing the loss function L to find a minimal training set error is a challenging numerical problem. The most popular methods for performing such optimization rely on some version of stochastic gradient descent (SGD). In addition, many authors have also argued that SGD may exploit certain features of the loss-function to find solutions that generalize particularly well BID17 ; BID28 ) However, while SGD is typically superior to other standard minimization methods in terms of optimization performance, there is no consensus in the field on how much of the remarkable generalization performance of DNNs is linked to SGD (Krueger et al. (2017) ). In fact DNNs generalize well when other optimization methods are used (from variants of SGD, like Adam (Kingma & Ba (2014) ), to gradient-free methods )). For example, in recent papers BID23 ; BID29 ; Keskar et al. (2016) simple gradient descent (GD) was shown to lead to differences in generalization with SGD of at most a few percent. Of course in practical applications such small improvements in generalization performance can be important. However, the question we want to address in this paper is the broader one of Why do DNNs generalize at all, given that they are so highly expressive and overparameterized? . While SGD is important for optimization, and may aid generalization, it does not appear to be the fundamental source of generalization in DNNs.Another longstanding family of arguments focuses on the local curvature of a stationary point of the loss function, typically quantified in terms of products of eigenvalues of the local Hessian matrix. Flatter stationary points (often simply called minima) are associated with better generalization performance (Hochreiter & Schmidhuber (1997) ; Hinton & van Camp (1993) ). Part of the intuition is that flatter minima are associated with simpler functions (Hochreiter & Schmidhuber (1997) ; BID23 ), which should generalize better. Recent work (Dinh et al. (2017) ) has pointed out that flat minima can be transformed to sharp minima under suitable re-scaling of parameters, so care must be taken in how flatness is defined. In an important recent paper BID23 ) an attack data set was used to vary the generalization performance of a standard DNN from a few percent error to nearly 100% error. This performance correlates closely with a robust measure of the flatness of the minima (see also BID29 for a similar correlation over a much smaller range, but with evidence that SGD leads to slightly flatter minima than simple GD does). The authors also conjectured that this large difference in local flatness would be reflected in large differences between the volume V good of the basin of attraction for solutions that generalize well and V bad for solutions that generalize badly. If these volumes differ sufficiently, then this may help explain why SGD and other methods such as GD converge to good solutions; these are simply much easier to find than bad ones. Although this line of argument provides a tantalizing suggestion for why DNNs generalize well in spite of being heavily overparameterized, it still begs the fundamental question of Why do solutions vary so much in flatness or associated properties such as basin volume?In this paper we build on recent applications of algorithmic information theory (AIT) (Dingle et al. (2018) ) to suggest that the large observed differences in flatness observed by BID23 ) can be correlated with measures of descriptional complexity. We then apply a connection between Gaussian processes and DNNS to empirically demonstrate for several different standard architectures that the probability of obtaining a function f in DNNs upon a random choice of parameters varies over many orders of magnitude. This bias allows us to apply a classical result from PAC-Bayes theory to help explain why DNNs generalize so well. In this paper, we present an argument that we think offers a first-order explanation of generalization in highly overparameterized DNNs. First, PAC-Bayes shows how priors which are sufficiently biased towards the true distribution can result in generalization in highly expressive models, e.g. even if there are many more parameters than data points. Second, the huge bias towards simple functions in the parameter-function map strongly suggests that neural networks have a similarly biased prior. The number of parameters in a fully expressive DNN does not strongly affect the bias. Third, since real-world problems tend to be far from random, using these same complexity measures, we expect the prior to be biased towards the right class of solutions for real-world datasets and problems. Figure 4: Average probability of finding a function for a variant of SGD, versus average probability of finding a function when using the Gaussian process approximation. This is done for a randomly chosen, but fixed, target Boolean function of Lempel-Ziv complexity 84.0. See Appendix D for details. The Gaussian process parameters are σ w = 10.0, and σ b = 10.0. For advSGD, we have removed functions which only appared once in the whole sample, to avoid finite-size effects. In the captions, ρ refers to the 2-tailed Pearson correlation coefficient, and p to its corresponding p value.To demonstrate the bias in the parameter-function map, we used both direct sampling for a small network and an equivalence with Gaussian processes for larger networks. We also used arguments from AIT to show that functions f that obtain with higher P (f ) are likely to be simple. However, a more complete understanding of this bias is still called for.We also demonstrated how to make this approach quantitative, approximating neural networks as Gaussian processes to calculate PAC-Bayesian bounds on the generalization error.It should be noted that our approach is not yet able to explain the effects that different tricks used in practice have on generalization. However, most of these improvements tend to be of the order of a few percent in the accuracy. The aim of this paper is to explain the bulk of the generalization, which classical learning theory would predict to be poor in this highly overparametrized regime. It is still an open question whether our approach can be extended to explain some of the tricks used in practice, as well as to methods other than neural networks (Belkin et al. (2018) ) that may also have simple parameter-function maps. To stimulate work in improving our bounds, we summarize here the main potential sources of error for our bounds:1. The probability that the training algorithm (like SGD) finds a particular function in the zero-error region can be approximated by the probability that the function obtains upon i.i.d. sampling of parameters.2. Gaussian processes model neural networks with i.i.d.-sampled parameters well even for finite widths.3. Expectation-propagation gives a good approximation of the Gaussian process marginal likelihood.
The parameter-function map of deep networks is hugely biased; this can explain why they generalize. We use PAC-Bayes and Gaussian processes to obtain nonvacuous bounds. The paper studies the generalization capabilities of deep neural networks, with the help of the PAC-Bayesian learning theory and empirically backed intuitions. This paper proposes an explaination of the generalization behaviors of large over-parameterized neural networks by claiming the parameter-function map in neural networks are biased towards "simple" functions and generalization behavior will be good if the target concept is also "simple".