Do deep neural networks have an inbuilt Occam's razor?
The remarkable performance of overparameterized deep neural networks (DNNs)
must arise from an interplay between network architecture, training algorithms,
and structure in the data. To disentangle these three components, we apply a
Bayesian picture, based on the functions expressed by a DNN, to supervised
learning. The prior over functions is determined by the network, and is varied
by exploiting a transition between ordered and chaotic regimes. For Boolean
function classification, we approximate the likelihood using the error spectrum
of functions on data. When combined with the prior, this accurately predicts
the posterior, measured for DNNs trained with stochastic gradient descent. This
analysis reveals that structured data, combined with an intrinsic Occam's
razor-like inductive bias towards (Kolmogorov) simple functions that is strong
enough to counteract the exponential growth of the number of functions with
complexity, is a key to the success of DNNs.
Chris Mingard, Henry Rees, Guillermo Valle-Pérez, Ard A. Louis
# Do deep neural networks have an inbuilt Occam's razor?

###### Abstract

The remarkable performance of overparameterized deep neural networks (DNNs) must arise from an interplay between network architecture, training algorithms, and structure in the data. To disentangle these three components, we apply a Bayesian picture, based on the functions expressed by a DNN, to supervised learning. The prior over functions is determined by the network architecture, and is varied by exploiting a transition between ordered and chaotic regimes. For Boolean function classification, we approximate the likelihood using the error spectrum of functions on data. When combined with the prior, this accurately predicts the posterior, measured for DNNs trained with stochastic gradient descent. This analysis reveals that structured data, combined with an intrinsic Occam's razor-like inductive bias towards (Kolmogorov) simple functions that is strong enough to counteract the exponential growth of the number of functions with complexity, is a key to the success of DNNs.

+
Footnote †: These authors contributed equally.

+
Footnote †: These authors contributed equally.

Although deep neural networks (DNNs) have revolutionised modern machine learning [1; 2], a fundamental theoretical understanding of why they perform so well remains elusive [3; 4]. One of their most surprising features is that they work best in the overparameterized regime, with many more parameters than data points. As expressed in the famous quip: "_With four parameters \(I\) can fit an elephant, and with five \(I\) can make _him wiggle his trunk."_ (attributed by Enrico Fermi to John von Neumann [5]), it is widely believed that having too many parameters will lead to overfitting: a model will capture noise or other inconsequential aspects of the data, and therefore predict poorly.

In statistical learning theory [6] this intuition is formalised in terms of model capacity. It is not simply the number of parameters, but rather the complexity of the set of hypotheses a model can express that matters. The search for optimal performance is often expressed in terms of bias-variance trade-off. Models that are too simple introduce errors due to bias; they can't capture the underlying processes that generate the data. Models that are too complex are over-responsive to random fluctuations in the data, leading to variance in their predictions.

DNNs are famously highly expressive [7; 8; 9], i.e. they have extremely high capacity. Their ability to generalize therefore appears to break basic rules of statistical learning theory. Exactly how, without explicit regularisation, DNNs achieve this feat is a fundamental question that has remained open for decades [3; 4]. Although there has been much recent progress (see Appendix A for a literature overview) there is no consensus for why DNNs work so well in the overparameterized regime.

Here we study this conundrum in the context of supervised learning for classification, where inputs \(x_{i}\) are attached to labels \(y_{i}\). Given a training set \(S=\{(x_{i},y_{i})_{i=1}^{m}\}\) of \(m\) input-output pairs, sampled i.i.d. from a data distribution \(\mathcal{D}\), the task is to train a model on \(S\) such that it performs well (has low generalization error) at predicting output labels \(\hat{y}_{i}\) for a test set \(T\) of unseen inputs, sampled from \(\mathcal{D}\). For a DNN \(\mathcal{N}(\Theta)\), with parameters \(\Theta\subseteq\mathbb{R}^{p}\) (typically weights and biases), the accuracy on a training set can be captured by a loss-function \(L(\hat{y}_{i},y_{i})\) that measures how close, for input \(x_{i}\), the prediction \(\hat{y}_{i}\) of the DNN is to the true label \(y_{i}\). Training is typically done via some variant of stochastic gradient descent (SGD) which uses derivatives of \(L(\hat{y}_{i},y_{i})\) to adjust the parameters \(\Theta\) in order to minimise the loss on \(S\). Because DNNs are so highly expressive, and because SGD is typically a highly effective optimiser for DNNs, zero training error (all correct labels after thresholding) on \(S\) is routinely achieved [7].

**Functions and inductive bias**

For classification, the question of why overparameterized DNNs don't overfit can conveniently be expressed in terms of functions. For a given training set \(S\) and test set \(T\), a function \(f\) can be defined on a restricted domain \(S+T\). The inputs of \(f\) are the \(x_{i}\in S\cup T\), and the outputs include all possible sets of labels \(\{\hat{y}_{i}\}\). Only one function gives the true labels \(\{y_{i}\}\). For a given set of parameters \(\Theta\), the DNN then represents a particular function \(f\), which can be identified by the labels it outputs on the inputs \(x_{i}\in S\cup T\), after thresholding. Under the assumption that zero training error can be achieved, functions need only be distinguished by how they behave on the test set \(T\). For \(C\) classes there are \(N_{T}=C^{|T|}\) possible functions \(f\) with zero error on the training set, this number is typically unimaginably large. The overwhelming majority of these functions will not generalize well. Since DNNs are highly expressive, they should be able to represent all (or nearly all) of these functions. The fundamental question of overparameterized DNN performance becomes a question of _inductive bias_: Why, from the unimaginably large set of functions that give zero error on \(S\), do DNNs converge on a minuscule subset of functions that generalize well? Here, we will argue that an Occam's razor like inductive bias towards simple functions, combined with structured
data, helps answer this question.

**Distinguishing questions about generalization**

Before proceeding, it is important to distinguish the question above from a different and equally interesting question: Given a DNN that generalizes reasonably well (e.g. it solves the overparameterization/large capacity problem), can we understand how to improve its performance further? This 2nd-order question is what practitioners of deep learning typically care about. Differences in architecture, hyperparameter tuning, data augmentation etc. can indeed lead to important improvements in DNN performance. Exactly why these tweaks and tricks generate better inductive bias is typically not well understood either, and is an important subject of investigation. Because the two questions are often conflated, leading to confusion, we want to emphasise up front that this paper will focus on the 1st-order conundrum shared by all overparameterized DNNs. Understanding this basic problem should help frame important 2nd-order questions about how to improve DNN performance further.

**Learning Boolean functions: a model system**

Inspired by calls to study model systems [3; 4], we first examine how a fully connected network (FCN) learns Boolean functions \(f:\{0,1\}^{n}\rightarrow\{0,1\}\), which are key objects of study in computer science. Just as the Ising model does for magnetism, this simple but versatile model allows us to capture the essence of the overparameterization problem, while remaining highly tractable. For a system of size \(n\), there are \(2^{n}\) inputs, and \(2^{2^{n}}\) Boolean functions. Given a Boolean target function \(f_{t}\), the DNN is trained on a subset \(S\) of \(m<2^{n}\) inputs, and then provides a prediction on a test set \(T\) which consists of the rest of the inputs. A key advantage of this system is that data complexity can easily be varied by choice of target function \(f_{t}\). Moreover, the model's tractability allows us to calculate the prior \(P(f)\), likelihood, \(P(S|f)\) and posterior \(P(f|S)\) for different functions and targets, and so cast the tripartite schema of architecture, training algorithm, and structured data from [4] into a textbook Bayesian picture.

**Quantifying inductive bias with Bayesian priors**

The prior over functions, \(P(f)\), is the probability that a DNN \(\mathcal{N}(\Theta)\) expresses \(f\) upon random sampling of parameters over a parameter initialisation distribution \(P_{\text{par}}(\Theta)\):

\[P(f)=\int\mathbb{1}\left[\mathcal{N}(\Theta)==f\right]P_{\text{par}}(\Theta)d\Theta, \tag{1}\]

where \(\mathbb{1}\) is an indicator function (\(1\) if its argument is true, and \(0\) otherwise), and its argument is true if the parameters of \(\mathcal{N}(\Theta)\) are such that represents \(f\) It was shown in [10] that, for ReLU activation functions, \(P(f)\) for the Boolean system was insensitive to different choices of \(P_{\text{par}}(\Theta)\), and that it exhibits an exponential bias of the form \(P(f)\lesssim 2^{-a\tilde{K}(f)+b}\) towards simple functions with low exceptional complexity \(\tilde{K}(f)\), which is a proxy for the true (but uncomputable) Kolmogorov complexity. We will, as in [10], calculate \(\tilde{K}(f)\) using \(C_{LZ}\), a Lempel-Ziv (LZ) based complexity measure from [11] on the \(2^{n}\) long bitstring that describes the function, taken on an ordered list of inputs. Other complexity measures give similar results [12; 10], so there is nothing fundamental about this particular choice. To simplify notation, we will use \(K(f)\) instead of \(\tilde{K}(f)\). The exponential drop of \(P(f)\) with \(K(f)\) in the map from parameters to functions is consistent with an algorithmic information theory (AIT) coding theorem [13] inspired _simplicity bias_ bound [11] which works for a much wider set of input-output maps. It was argued in [10] that if this inductive bias in the priors matches the simplicity of structured data then it would help explain why DNNs generalize so well. However, the weakness of that work, and related works arguing for such a bias towards simplicity [12; 14; 15; 16; 17; 18; 19; 20; 21], is that it is typically not possible to significantly change the inductive bias towards simplicity, making it hard to conclusively show that it is not some other property of the network that instead generates the good performance. Here we exploit a particularity of tanh activation functions that enable us to significantly vary the inductive bias of DNNs. In particular, for a Gaussian \(P_{\text{par}}(\Theta)\) with standard deviation \(\sigma_{w}\), it was shown [22; 23] that, as \(\sigma_{w}\) increases, there is a transition to a chaotic regime. Moreover, it was recently demonstrated that the simplicity bias in \(P(f)\) becomes weaker in the chaotic regime [24] (see also Appendix C). We will exploit this behaviour to systematically vary the inductive bias over functions in the prior.

In Figures 0(a) and 0(b) we depict prior probabilities \(P(f)\) for functions \(f\) defined on all 128 inputs of a \(n=7\) Boolean system upon random sampling of parameters of an FCN with 10 layers and hidden width 40 (which is large enough to be fully expressive for this system [17]), and tanh activation functions. The simplicity bias in \(P(f)\) becomes weaker as the width \(\sigma_{w}\) of the Gaussian \(P_{\text{par}}(\sigma_{w})\) increases. By contrast, for ReLU activations, the bias in \(P(f)\) barely changes with \(\sigma_{w}\) (see Figure S3(a)). The effect of the decrease in simplicity bias on DNN generalization performance is demonstrated in Figure 0(c) for a DNN trained to zero error on a training set \(S\) of size \(m=64\) using advSGD (an SGD variant taken from [10]), and tested on the other 64 inputs \(x_{i}\in T\). The generalization error (the fraction of incorrect predictions on \(T\)) varies as a function of the complexity of the target function. Although all these DNNs exhibit simplicity bias, weaker forms of the bias correspond to significantly worse generalization on the simpler targets (see also Appendix J). For very complex targets, both networks perform poorly. Finally, we also show an unbiased learner, where functions \(f\) are chosen uniformly at random with the proviso that they exactly fit the training set \(S\). Not surprisingly, given the \(2^{64}\approx 2\times 10^{19}\) functions that can fit \(S\), the performance of this unbiased learner is no better than random chance.

The scatter plots of Figure 1 (d)-(f) depict a more fine-grained picture of the behaviour of the SGD-trained networks for three different target functions. For each target, 1000 independent initialisations of the SGD opti
miser, with initial parameters taken from \(P_{\text{par}}(\sigma_{w})\), are used. The generalization error and complexity of each function found when the DNN first reaches zero training error are plotted. Since there are \(2^{64}\) possible functions that give zero error on the training set \(S\), it is not surprising that the DNN converges to many different functions upon different random initialisations. For the \(\sigma_{w}=1\) network (where \(P(f)\) resembles that of ReLU networks) the most common function is typically simpler than the target. By contrast, the less biased network converges

Figure 1: **Priors over functions and over complexity** (a) Prior \(P(f)\) that a \(N_{l}\)-layer FCN with \(\tanh\) activations generates \(n=7\) Boolean functions \(f\), ranked by probability of individual functions, generated from \(10^{8}\) random samples of parameters \(\Theta\) over a Gaussian \(P_{\text{par}}(\Theta)\) with standard deviations \(\sigma_{w}=1\dots 8\). Also compared is a ReLU-activated DNN. The dotted blue line denotes a Zipf’s law prior [10]\(P(f)=1/((128\ln 2)Rank(f))\). (b) \(P(f)\) versus LZ complexity \(K\) for the networks from (a). (c) generalization error versus \(K\) of the target function for an unbiased learner (green), and \(\sigma_{w}=1,8\) tanh networks trained to zero error with advSGD [10] on cross-entropy loss with training set \(S\) of size \(m=64\), for 1000 random initialisations. The error is calculated on the remaining \(|T|=64\) functions. Error bars are one standard deviation. (d), (e), (f) Scatterplots of generalization error versus learned function LZ complexity, from 1000 random initialisations for three target functions from subfigure (c). The dashed vertical line denotes the target function complexity. The black cross represents the mode function. The histograms at the top (side) of the plots show the posterior probability upon training as a function of complexity,\(P_{\text{SGD}}(K|S)\) (error,\(P_{\text{SGD}}(\epsilon_{G}|S)\)). (g) The prior probability \(P(K)\) to obtain a function of LZ complexity \(K\) for uniform random sampling of \(10^{8}\), compared to a theoretical perfect compressor. 90% of the probability mass lies to the right of the vertical dotted lines, and the dash-dot line denotes an extrapolation to low \(K\). (h) \(P(K)\) is relatively uniform on \(K\) for the \(\sigma_{w}=1\) system, while it is highly biased towards complex functions for the \(\sigma_{w}=8\) networks. The large difference in these priors helps explain the significant variation in DNN performance. (i) generalization error for the K-learning restriction for the \(\sigma_{w}=1,8\) DNNs and for an unbiased learner, all for \(|S|=100\). \(\epsilon_{S}\) is the training error and \(\epsilon_{G}\) is the generalization error on the test set. The vertical dashed line is the complexity \(K_{t}\) of the target. Also compared are the standard realisable PAC and marginal-likelihood PAC-Bayes bounds for the unbiased learner. In \(10^{4}\) samples, no solutions were found with \(K\lesssim 70\) for the \(\sigma_{w}=8\) DNN, and with \(K\gtrsim 70\) for \(\sigma_{w}=1\) DNN.
on functions that are typically more complex than the target. As the target itself becomes more complex, the relative difference between the two generalization errors decreases, because the strong inductive bias towards simple functions of the first network becomes less useful. No free lunch theorems for supervised learning tell us that when averaged over all target functions, the three learners above will perform equally badly [25, 26] (see also Appendix D.3).

To understand why changes in the inductive bias towards simplicity that are small relative to the 38 or so orders of magnitude scale on which \(P(f)\) varies (see also Figure S3(b)) nevertheless lead to such significant differences in generalization performance, we need another important ingredient, namely how the _number_ of functions vary with complexity. Basic counting arguments imply that the number of strings of a fixed length that have complexity \(K\) scales exponentially as \(2^{K}\)[13]. Therefore, the vast majority of functions picked at random will have high complexity. This exponential growth of the number of functions with complexity can be captured in a more coarse-grained prior, the probability \(P(K)\) that the DNN expresses a function of complexity \(K\) upon random sampling of parameters over a parameter initialisation function \(P_{\text{par}}(\Theta)\), which can also be written in terms of functions as \(P(K^{\prime})=\sum_{f\in\mathcal{H}_{K^{\prime}}}P(f)\), the weighted sum over the set \(\mathcal{H}_{K^{\prime}}\) of all functions with complexity \(\tilde{K}(f)=K^{\prime}\). In Figure 1 (g) \(P(K)\) is shown for uniform random sampling of functions for \(10^{8}\) samples using the LZ measure, and also for the theoretical ideal compressor with \(P(K)=2^{K-K_{max}-1}\) over all \(2^{128}\approx 3\times 10^{38}\) functions (see also Appendix I). In (h) we display the dramatic difference between the fully simplicity-biased \(P(K)\) and the less-biased \(P(K)\). For the network with \(\sigma_{w}=1\)\(P(K)\) is nearly flat. This behaviour follows from the fact that the AIT coding-theorem like scaling [10, 11] of the prior over functions \(P(f)\sim 2^{-\tilde{K}(f)}\) counters the \(2^{K}\) growth in the number of functions. By contrast, for the more artefactual \(\sigma_{w}=8\) system, the simplicity bias is less strong. Even though there remains significant simplicity bias (we estimate that for the simplest functions, \(P(f)\) is about \(10^{25}\) times higher than the mean probability \(\left\langle P(f)\right\rangle=2^{-128}\approx 3\times 10^{-39}\)) this DNN is orders of magnitude more likely to throw up complex functions, an effect that SGD is unable to overcome.

The fact that the number of complex functions grows exponentially with complexity \(K\) lies at the heart of the classical explanation of why a complex learning agent suffers from variance: It can too easily find many different functions that all fit the data. The marked differences in the generalization performance between the two networks observed in Figure 1 (c)-(f) can be therefore traced to differences in the inductive bias of the networks, as measured by the differences in their priors. The \(\sigma_{w}=8\) network is not simplicity biased enough to overcome the growth in the number of functions, and so it suffers from the classic problem of overfitting and large variance. By contrast, the \(\sigma_{w}=1\) system, and the nearly identical ReLU system, solve this problem because their inductive bias cancels the exponential growth in complex functions.

**Artificially restricting model capacity** To further illustrate the effect of inductive bias we create a K-learner that only allows functions with complexity \(\leq K_{M}\) to be learned and discards all others. As can be seen in Figure 1 (i), the learners typically cannot reach zero training error on the training set if \(K_{M}\) is less than the target function complexity \(K_{t}\). For \(K_{M}\geq K_{t}\), zero training error can be reached and not surprisingly, the lowest generalization error occurs when \(K_{M}=K_{t}\). As the upper limit \(K_{M}\) is increased, all three learning agents are more likely to make errors in predictions due to variance. The random learner has an error that grows linearly with \(K_{M}\). This behaviour can be understood with a classic PAC bound [6] where the generalization error (with confidence \(0\geq(1-\delta)\leq 1\)) scales as \(\epsilon_{G}\leq(\ln|\mathcal{H}_{\leq K_{M}}|-\ln\delta)/m\), where \(|\mathcal{H}_{\leq K_{M}}|\ K\leq K_{M}\) is the size of the hypothesis class of all functions with \(K\leq K_{M}\); the bound scales linearly in \(K_{M}\), as the error does (see Appendix G for further discussion including the more sophisticated PAC-Bayes bound [27, 28].). The generalization error for the \(\sigma_{w}=1\) DNN does not change much with \(K_{M}\) for \(K_{M}>K_{t}\) because the strong inductive bias towards simple solutions means access to higher complexity solutions doesn't significantly change what the DNN converges on.

**Calculating the Bayesian posterior and likelihood** To better understand the generalization behaviour observed in Figure 1 we apply Bayes' rule, \(P(f|S)=P(S|f)P(f)/P(S)\) to calculate the Bayesian posterior \(P(f|S)\) from the prior \(P(f)\), the likelihood \(P(S|f)\), and the marginal likelihood \(P(S)\). Since we condition on zero training error, the likelihood takes on a simple form. \(P(S|f)=1\) if \(\forall x_{i}\in S,f(x_{i})=y_{i}\), while \(P(S|f)=0\) otherwise. For a fixed training set, all the variation in \(P(f|S)\) for \(f\in U(S)\), the set of all functions compatible with \(S\), comes from the prior \(P(f)\) since \(P(S)\) is constant. Therefore, in this Bayesian picture, the bias in the prior is translated over to the posterior.

The marginal likelihood also takes a relatively simple form for discrete functions, since \(P(S)=\sum_{f}P(S|f)P(f)=\sum_{f\in U(S)}P(f)\). It is equivalent to the probability that the DNN obtains zero error on the training set \(S\) upon random sampling of parameters, and so can be interpreted as a measure of the inductive bias towards the data. The Marginal-likelihood PAC-Bayes bound [28] makes a direct link \(P(S)\lesssim e^{-m\epsilon_{G}}\) to the generalization error \(\epsilon_{G}\) which captures the intuition that, for a given \(m\), a better inductive bias towards the data (larger \(P(S)\)) implies better performance (lower \(\epsilon_{G}\)).

One can also define the posterior probability \(P_{\text{SGD}}(f|S)\), that a network trained with SGD (or another optimiser) on training set \(S\), when initialised with \(P_{\text{par}}(\Theta)\), converges on function \(f\). For simplicity, we take this probability at the epoch where the system first reaches zero training error. Note that in Figure 1 (d)-(f) it is this SGD-based posterior that we plot in the histograms at the top and sides of the plots, with functions grouped
either by complexity, which we will call \(P_{\mathrm{SGD}}(K|S)\), or by generalization error \(\epsilon_{G}\), which we will call \(P_{\mathrm{SGD}}(\epsilon_{G}|S)\).

DNNs are typically trained by some form of SGD, and not by randomly sampling over parameters which is much less efficient. However, a recent study [29] which carefully compared the two posteriors has shown that to first order, \(P_{\mathrm{B}}(f|S)\approx P_{\mathrm{SGD}}(f|S)\), for many different data sets and DNN architectures. We demonstrate this close similarity in Figure S12 explicitly for our \(n=7\) Boolean system. This evidence suggests that Bayesian posteriors calculated by random sampling of parameters, which are much simpler to analyze, can be used to understand the dominant behaviour of an SGD-trained DNN, even if, for example, hyperparameter tuning can lead to 2nd-order deviations between the two methods (see also Appendix A).

To test the predictive power of our Bayesian picture, we first define the function error \(\epsilon(f)\) as the fraction of incorrect labels \(f\) produces on the full set of inputs. Next, we average Bayes' rule over all training sets \(S\) of size \(m\):

\[\langle P(f|S)\rangle_{m}=P(f)\langle\frac{P(S|f)}{P(S)}\rangle_{m}\approx \frac{P(f)\left(1-\epsilon(f)\right)^{m}}{\langle P(S)\rangle_{m}} \tag{2}\]

Figure 2: **How training data affects the posteriors:** (a), (b) and (c) depict the mean likelihood \(\langle(1-\epsilon_{G}(K))^{m}\rangle_{5}\) from Equation (3), averaged over training sets, and over the 5 lowest error functions at each \(K\). This term depends on data and is independent of the DNN architecture. With increasing \(m\) it peaks more sharply around the complexity of the target. In (d)–(f) we compare the posteriors over complexity, \(\langle P_{\mathrm{SGD}}(K|S)\rangle_{m}\), for SGD (darker blue and red) averaged over training sets of size \(m\), to the prediction of \(\langle P(K|S)\rangle_{m}\) from Equation (3) (lighter blue and orange), calculated by multiplying the Bayesian likelihood curves in Figs (a)–(c) by the prior \(P(K)\) shown in Figure 1(h). The light (Bayes) and dark (DNN) blue histograms are from the \(\sigma_{w}=1\) system, and the orange (Bayes) and red (DNN) histograms are from the \(\sigma_{w}=8\) system which has less bias towards simple functions. The Bayesian decoupling approximation (Eq. (3) captures the dominant trends in the behaviour of the SGD trained networks as a function of data complexity and training set size.
where the mean likelihood \(\langle P(S|f)\rangle_{m}=(1-\epsilon(f))^{m}\) is the probability of a function \(f\) obtaining zero error on a training set of size \(m\). In the second step, we approximate the average of the ratio with the ratio of the averages which should be accurate if \(P(S)\) is highly concentrated, as is expected if the training set is not too small.

Equation (2) is hard to calculate, so we coarse-grain it by grouping together functions by their complexity:

\[\langle P(K|S)\rangle_{m}=\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
There may be links to more formal arguments in AIT relating to the optimality of Solomonoff induction which is based on a universal prior that both takes into account all hypotheses consistent with the data (Epicurus's principle), but prioritises the (Kolmogorov) simpler ones [13; 33]. Similarly, the (nearly) flat \(P(K)\) means the DNN has access to hypotheses with a large range of complexities that can then interact with data. Needless to say, much more work is needed to work out whether these connections are superficial or profound (see also Appendix D.4).

We were not able to significantly increase the bias towards simplicity in DNNs. Too strong a bias towards simplicity can mean a loss of versatility because complex functions become hard to find [34; 12].

The methods used in this paper work well for classification of discrete functions. An important further piece of research, where kernel methods may play a more central role, is to study the inductive biases for regression problems with continuous functions.

While we have explored some key ingredients, the full question of why DNNs generalize so well remains open. Understanding what the extra 2nd-order effects of hyperparameter tuning etc. are, or how feature learning (which is not present in Bayesian GPs) improves generalization are important problems that our methods are unlikely to solve. Our results do not preclude the fact that SGD optimization itself can also introduce useful inductive biases (see also Appendix A). Simplicity bias is one of many inductive biases that DNNs likely exhibit. Much of the exciting recent progress in foundation models such as GPT-4 likely arises from inductive biases well beyond just simplicity, although simplicity bias plays an important role for such models [12]. Systematically studying and understanding how these biases interact with data remains one of the key challenges in modern machine learning.

Finally, our observations about inductive bias can be inverted to reveal properties of the data on which DNNs are successful at learning. For example, data cannot be too complex. Furthermore, the remarkable success of DNNs on a broad range of scientific problems [35; 36; 37; 38] suggests that their inductive biases must recapitulate something deep about the structure of the natural world [15]. Understanding why DNNs choose the solutions they do may, in turn, generate profound insights into nature itself.

Figure 3: **MNIST and CIFAR-10 data.** (a) MNIST generalization error for FCNs on a 1000 image training set versus \(\sigma_{w}\) for three depths. (b) CIFAR10 generalization error for FCNs trained on a 5000 image training set versus \(\sigma_{w}\) for three depths. The FCNs, made of multiple hidden layers of width 200, were trained with SGD with batch size 32 and lr=\(10^{-3}\) until 100% accuracy was first achieved on the training set. (c) Complexity prior \(P(K)\), for CSR complexity, for 1000 MNIST images for randomly initialised networks of 10 layers and \(\sigma_{w}=1,2\). Probabilities are estimated from a sample of \(2\times 10^{4}\) parameters. Figs (d), (e) and (f) are scatterplots of generalization error versus the CSR for 1000 networks trained to 100% accuracy on a training set of 1000 MNIST images and tested on 1000 different images. In (d) the training labels are uncorrupted, in (e) and (f) 25% and 50% of the training labels are corrupted respectively. Note the qualitative similarity to the scatter plots in Fig 1 (d)-(f).
## Acknowledgments

We thank Satwik Bhattamishra, Kamal Dingle, Nayara Fonseca, and Yoonsoo Nam for helpful discussions.
