Deep learning generalizes because the parameter-function map is biased towards simple functions

In plain words

Large neural networks have far more knobs than training examples, yet they usually do not memorise noise. This paper proposes a reason: when you pick a network's settings at random, the function it ends up computing is far more likely to be a simple one than a convoluted one. The paper argues that the network's design, when its settings are picked at random, already tilts the odds toward simple answers.

The authors test this on a tiny network that takes seven yes/no inputs, and then on larger image networks. They also use a known result from learning theory: if the prior over functions favours simple ones, you can bound how far a trained model's error can be from its training error. Approximating the network with a Gaussian process makes that bound computable, and on the image datasets the bounds move with the real test error. The paper is a first-order argument and says so: several training details are not explained by it.

TL;DR

• Random-weight networks produce simple Boolean functions far more often than complex ones; probability falls exponentially with a complexity measure §4 eq. 1.
• Replacing the prior over parameters with a prior over functions (via a Gaussian-process approximation) gives PAC-Bayes bounds that correlate with test error on binarized MNIST, fashion-MNIST and CIFAR10 §5 §6.
• The argument needs an unverified assumption: SGD samples the zero-error region close to uniformly. Evidence is partial and limited to the small Boolean net §7.

Problem

Classical complexity bounds (VC dimension, Rademacher complexity) grow with the number of parameters, so for over-parameterised networks they become vacuous §1. Regularisers such as dropout or weight decay are not necessary for generalisation: networks trained on randomly relabelled CIFAR10 can memorise it §1. Flatness-based and SGD-based explanations exist but do not say why flatness or the SGD bias differs between solutions §1. The paper asks why networks generalise at all, treating the parameter-function map as the object of study §1 §2.

Method

Parameter-function map. For a model with parameter vector θ in Θ, the map M sends θ to the function f_θ that the model computes on the input space. The search algorithm works in parameter space, but generalisation depends on the function it lands on §2, Def. 1.

Simplicity bias from algorithmic information theory. The authors reuse a bound from earlier work by Dingle et al. (cited as simpbias): for an input-output map with suitable conditions, the probability of an output x under uniform random inputs is bounded by an exponential in an approximate Kolmogorov complexity §3 eq. 1.

P(x) \leq 2^{-a \tilde{K}(x) + b} eq. 1

Here K̃(x) approximates the uncomputable Kolmogorov complexity of x, and a and b depend on the map but not on x. The bound needs the map to be simple, the map to have redundancy (many inputs per output), the output space to be large, the map to be nonlinear, and the map not to produce pseudorandom outputs §3 app. E.

The authors argue that a DNN parameter-function map meets these conditions §3 app. E. The conditions are checked by argument, not by proof.

Boolean-net experiment. Take a network with 7 Boolean inputs, two hidden layers of 40 ReLU units each, and one Boolean output. Its input space has 2^7 = 128 points and its function space is at most 2^128 functions §4. Draw parameters from a Gaussian (or a uniform distribution in a hypercube) and count how often each function appears. The rank-frequency curve fits a normalised Zipf law, P(r) = (ln(N_O) r)^(-1), with N_O = 2^128 and no fitted parameters. The authors estimate that this spans about 39 orders of magnitude §4.

# Estimate P(f) for a random 7-40-40-1 ReLU net  [§4] [fig. 1]
# Parameters are drawn i.i.d. from a zero-mean Gaussian  [§4] [app. A]

def estimate_function_probabilities(num_samples):
    counts = {}
    for _ in range(num_samples):
        # Draw all weights and biases of the net  [§4]
        params = sample_random_params()
        # Evaluate the net on all 2^7 binary inputs  [§4]
        truth_table = evaluate_on_all_inputs(params)  # 128 bits
        counts[truth_table] = counts.get(truth_table, 0) + 1
    # Empirical frequency approximates P(f)  [§4] [fig. 1]
    return {f: c / num_samples for f, c in counts.items()}

Complexity measures. The authors check that probability falls with complexity for several measures, not only one. The main measure is Lempel-Ziv (LZ) complexity of the 128-bit truth table app. F.1 eq. 5.

K_{LZ}(x) = \begin{cases} \log_2 n & x = 0^n \text{ or } 1^n \\ \log_2 n \cdot \frac{N_w(x_1 \dots x_n) + N_w(x_n \dots x_1)}{2} & \text{otherwise} \end{cases} eq. 5

Here n is the string length and N_w is the number of dictionary words the LZ compressor produces. Other measures in the appendix are Boolean-expression size, a generalisation complexity app. F.1, entropy app. F.5 and the critical sample ratio app. F.1.

# LZ-based complexity of a Boolean function  [app. F.1] [eq. 5]
# bits: the truth table as a string of length n

def lz_complexity(bits):
    n = len(bits)
    # Constant strings get the minimum value  [eq. 5]
    if all_equal(bits):
        return log2(n)
    # Average the phrase counts of the string and its reverse  [eq. 5]
    forward = lz_phrase_count(bits)
    backward = lz_phrase_count(reverse(bits))
    return log2(n) * (forward + backward) / 2

Larger networks. For a 4-layer CNN, the authors restrict the inputs to 1000 random CIFAR10 images, sample random networks to label them, and compute the probability of each labelling together with its critical sample ratio. The two correlate strongly §4 fig. 2.

PAC-Bayes bound. The paper uses a PAC-Bayes theorem with a prior P over functions and a posterior Q: with probability at least 1 − δ over m training examples, the KL-type inequality below holds for all Q [thm. 1]. The realizable case, where zero training error is achievable, gives a simpler corollary for the posterior Q*(c) = P(c)/P(U) restricted to labellings consistent with the training set [cor. 1] §5.

\hat{\epsilon}(Q)\ln\frac{\hat{\epsilon}(Q)}{\epsilon(Q)} + (1-\hat{\epsilon}(Q))\ln\frac{1-\hat{\epsilon}(Q)}{1-\epsilon(Q)} \leq \frac{\mathrm{KL}(Q\|P) + \ln(2m/\delta)}{m-1} eq. 2

-\ln\left(1-\epsilon(Q^*)\right) \leq \frac{\ln\frac{1}{P(U)} + \ln\frac{2m}{\delta}}{m-1} [cor. 1]

Here P(U) is the prior probability that the training labels occur, which is the marginal likelihood of the data under the prior. The correction P(U) is the hard part §5.

The step from a prior over parameters to one over functions uses the distribution over functions induced by sampling parameters, P(c) = P̃(M⁻¹(c)). The key assumption is that SGD, restricted to zero-error parameters, samples them close to uniformly, so that its output distribution matches this prior §5 §7.

Gaussian-process approximation. Infinitely wide networks with i.i.d. parameters are Gaussian processes §5.1. The label distribution on a finite input set is then

P_{\theta \sim \tilde{P}}\big(f_\theta(x_1)=\tilde{y}_1,\dots,f_\theta(x_n)=\tilde{y}_n\big) \propto \exp\!\Big(-\tfrac{1}{2}\tilde{\mathbf{y}}^{T}\mathbf{K}^{-1}\tilde{\mathbf{y}}\Big) eq. 3

with K_ij = k(x_i, x_j). The kernel depends on architecture and on the weight variance σ_w²/n and bias variance σ_b² §5.1. For fully connected ReLU nets the kernel has a closed form (arc-cosine kernel); for convolutional nets the authors use code from Garriga-Alonso et al. §5.1. Converting the real-valued output to labels uses a step function; the authors use a Bernoulli likelihood with a probit link as an approximation §5.1 app. A.

# Approximate P(U), the marginal likelihood of training labels  [§5.1]
# inputs: m training inputs; labels: m labels in {0, 1}

def gp_log_marginal(inputs, labels, sigma_w, sigma_b):
    # Covariance over the training inputs  [§5.1] [eq. 3]
    K = architecture_kernel(inputs, sigma_w, sigma_b)  # (m, m)
    # Bernoulli likelihood with probit link  [app. A]
    # Expectation propagation gives the evidence  [§5.1]
    return expectation_propagation_log_evidence(K, labels)

Training protocol for the bound experiments. Binarize MNIST, fashion-MNIST and CIFAR10 (label 0 for the first five classes, 1 otherwise) §6. Train with SGD until 100% training accuracy, then compute the bound from the GP approximation of P(U) §6 app. A. Sweep the fraction of corrupted labels to see whether error and bound move together §6 fig. 3.

SGD versus Bayesian sampling. The authors compare the probability that SGD-like training (advSGD and Adam) lands on each function with the GP approximation of the prior, for a target of LZ complexity 84.0 §7. The authors' variant of SGD, called advSGD, is used for the small Boolean net; it is modelled on adversarial training and weights examples by their recent error app. A.

# advSGD: sample hard examples more often  [app. A]
# errors: running average of per-example error, one value per training example

def adv_sgd_step(net, examples, errors, batch_size=10):
    # Turn the running error scores into sampling probabilities  [app. A]
    probs = softmax(errors)
    batch = sample_examples(examples, probs, batch_size)
    loss = binary_cross_entropy(net(batch.inputs), batch.labels)
    net.update(loss)
    # Update each sampled example's running error  [app. A]
    errors[batch.ids] = update_running_error(errors[batch.ids], batch)

Hyperparameters

Results

Author-reported. Setup: binarized datasets of 10000 examples, CNN (4 layers) and FC nets, GP-approximated prior, realizable bound §6 tab. 1.

Other reported results (author-reported):

• Boolean net: the rank-frequency curve follows the Zipf fit over about 39 orders of magnitude §4 fig. 1.
• Boolean net: probability falls as LZ complexity rises, with high-probability functions all of low complexity §4 fig. 1.
• Four-layer CNN on 1000 CIFAR10 inputs: probability and critical sample ratio correlate strongly §4 fig. 2.
• Label-corruption sweep (CNN and FC): bounds follow the same trend as the measured error; marginal likelihood P(U) falls by many orders of magnitude as corruption grows §6 fig. 3.
• Target of LZ complexity 84.0: SGD-like vs GP-prior average probability, Pearson ρ = 0.99 (advSGD, p = 3e-31; Adam, p = 8e-42) with σ_w = σ_b = 10 §7 fig. 4. With σ = 1 the correlation is lower (ρ = 0.72 advSGD, ρ = 0.66 Adam) app. D.
• The GP prior and a sampled network agree closely for 10 MNIST inputs; the EP and Laplace approximations each track the sampled frequencies app. B fig. 2.

Paper vs code

The official-looking repository is guillefix/nnbias at commit 09f7dcc12d8c13872511cf94d1029364b322f9d8. Searches: the paper, abstract and bibliography contain no code link. GitHub repository searches for "parameter-function map simplicity bias", "simplicity bias DNN" and the author names returned nothing relevant. A user search for "Guillermo Valle" returned guillefix, whose profile name is "Guillermo Valle" and whose bio describes an ML theory PhD. The repository matches the paper's topic and its scripts refer to a cluster path /users/guillefix/bias/nn_bias/bias_cpp run_sample_net.sh. We treat the owner as the first author. The repository has no LICENSE and no README, so code_license is "not stated"; the code is cited by path and line only, with no quotation.

What the repository contains: C++ samplers for random nets, LZ complexity, exhaustive enumeration, and ABI-style counting. It does not contain the GP/EP marginal-likelihood code, the CNN or FC training code, the advSGD training code, or the code that produced Table 1. Those parts cannot be reproduced from this repository.

Discrepancies:

• Weight scale. Paper footnote: weights from a distribution of "variance 1/√n" §4 app. F.3. Code draws each weight from a Gaussian with std σ_w/√(fan-in), i.e. variance σ_w²/n, which is the GP convention in §5.1 sample_funs.cpp. At σ_w = 1 the code's variance is 1/n, not 1/√n. The shell notes sample with σ_w = 1.0 and σ_b = 0.0 notes.
• Bias scale. Code bias std is σ_b, default 0.0 sample_funs.cpp sample_funs.cpp. The paper does not state the bias scale for the Boolean net §4.
• Output threshold. Code maps the output as floor((sign(out)+1)/2). A pre-activation of exactly 0 gives sign 0 and therefore output 0 nn_pheno_bool_2hl.hpp. The paper does not state a tie rule.
• Training-set size in the SGD-vs-ABI check. Paper text: 118 app. D. Code: m = 64 abi_from_sample.cpp abi_from_sample_v2.cpp. The first code version draws the 64 training inputs at random without replacement abi_from_sample.cpp; the second reads them from an argument abi_from_sample_v2.cpp.
• Error on off-training inputs. The code computes the error as 1 − (agreements − m)/(128 − m) over the 128 − m inputs not in training abi_from_sample_v2.cpp. The paper does not write this formula, so the code is the only definition.
• LZ reversal bug. The reversed string is built with strrev[i] = s[L-i] KC.h. This reads s[L] (the terminator) first and omits s[0], so the "reverse" term is not the reversal of the string. The forward phrase count and the constant-string case match the paper KC.h eq. 5. Implementers should reverse correctly.
• Non-compiling file. abi_from_sample.cpp defines entropy inside main abi_from_sample.cpp. Use abi_from_sample_v2.cpp, which defines it at top level abi_from_sample_v2.cpp.
• advSGD. Only plotting code for advSGD results is present; the result files are not in the repository analyze_abi.py.

Pitfalls

• The central assumption is not verified. The PAC-Bayes bound assumes SGD samples the zero-error region close to uniformly §5. The evidence is an experiment on a 7-input Boolean net with advSGD and Adam, not on the CNN and FC nets in Table 1 §7. The authors list this as the main open source of error §8.
• Training tricks are not explained. The authors say the approach cannot yet explain the effect of common practical tricks, which they note usually change accuracy by a few percent §8.
• Sign of b. Eq. 1 in the main text is 2^(−aK̃+b) §3 eq. 1. The appendix version is 2^(−(aK̃+b)) app. F eq. 4. Implementers must choose one; the appendix form makes b enter with the opposite sign.
• δ is not given. The bounds in Table 1 do not state δ tab. 1. Evaluating the bound requires a value.
• Inverting the corollary is not described. The paper says the right-hand side can be inverted to bound ε §5. It gives no procedure. The closed form ε ≤ 1 − exp(−r) with r = the right-hand side of [cor. 1] follows from −ln(1−ε) ≤ r; it is this card's derivation, not the paper's.
• P(U) is an approximation with known bias. The text says the EP approximation "appears to overestimate probabilities" app. D. Over 1000 inputs, the EP and Laplace log-likelihoods differ by less than about 10% §5.1.
• Variance choice dominates. σ_w and σ_b change the bound a lot app. C. At σ_w = 1 the bound for MNIST exceeds that for fashion-MNIST in the FC net, reversing the ordering app. C. Using the variance measured after SGD (an order of magnitude smaller) gave bounds above 50% at every corruption level app. C. The choice used for the results was fixed per architecture and "above the phase transition" app. C; the exact procedure is not stated.
• Zero training error is required. The corollary assumes the training data are realizable [cor. 1]. The experiments train to 100% training accuracy with early stopping app. A.
• Output nonlinearity for CNN/FC is unclear. The appendix says the last layer is "a single Softmax neuron" app. A. A softmax over one unit is constant, so the intended output is probably a sigmoid; the paper does not say.
• Depth conflicts. Figure 3 caption: the FC network has 1 hidden layer fig. 3. Table 1 caption: "1 layer FC" tab. 1. The appendix figure caption: a two-layer FC network app. C. The 4-layer CNN is consistent across sources.
• Generalisation-complexity formula has a typo. The second term is labelled C_1 instead of C_2 app. F.1.
• LZ depends on bit ordering. The authors use numerical ordering of inputs, which they say has little effect app. F.1. Other orderings are untested.
• Finite-sample artefacts. For a sample of size N, the smallest estimable probability is 1/N, so rare functions are over-counted app. G. Points at frequency 10^-8 are removed from plots fig. 1.
• Extrapolated range. The "39 orders of magnitude" range extends a Zipf fit beyond the sampled ranks §4.
• Cost is not stated. The paper gives no runtime or memory figures for the GP/EP computations or the sampling runs.
• Critical sample ratio is ambiguous for CIFAR. For the Boolean net it is the fraction of inputs with a Hamming-distance-1 neighbour of different output app. F.1. For the CIFAR CNN the neighbour set (within the 1000 sampled inputs or over all inputs) is not stated fig. 2.

Lineage

• Builds on: the simplicity-bias bound of Dingle, Camargo and Louis (cited as simpbias) §3 eq. 1; the PAC-Bayes theorem of Langford and Seeger [thm. 1] and the realizable corollary of McAllester [cor. 1] §5; Gaussian-process equivalence of wide networks by Lee et al. and Matthews et al. §5.1; the arc-cosine kernel §5.1; CNN Gaussian-process kernel code by Garriga-Alonso et al. §5.1.
• Compared against: Zhang et al. (label randomisation) §1; Wu et al. (flatness and basin volume) §1 §5; Arpit et al. (learning simple patterns first) app. J; Dziugaite and Roy's non-vacuous PAC-Bayes bounds §5 app. J.
• Superseded by: not stated.