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

Guillermo Valle-Pérez; Chico Q. Camargo; Ard A. Louis

Source-linked AI summary

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

Guillermo Valle-Pérez, Chico Q. Camargo, Ard A. Louis

arXiv:1805.08522v5May 22, 2018stat.MLcs.AIcs.LGcs.NE

TL;DR

The paper asks why highly overparameterized DNNs generalize without explicit regularization despite classical overfitting predictions. It uses AIT, function-space PAC-Bayes analysis, and Gaussian-process approximations to argue for a simplicity-biased parameter-function map, finding bounds that track true-error behavior while leaving practical training tricks unexplained.

Problem
Highly overparameterized DNNs generalize well despite classical learning theory predicting overfitting, and existing explanations lack consensus on the fundamental reason.
Method
The paper applies AIT to the parameter-function map and estimates function-space marginal likelihoods with Gaussian processes for PAC-Bayes bounds.
Results
The PAC-Bayes bounds closely follow the trends of true generalization error across the evaluated datasets and architectures.
Takeaways & Limitations
The results support parameter-function bias toward simple functions as a main contributor to generalization in highly overparameterized DNNs.
Takeaways & Limitations
The approach does not yet explain the effects of practical training tricks, and extending it to those effects remains an open question.

Abstract

from arXiv · show

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 applied to 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.

1 INTRODUCTION

Deep neural networks generalize well despite overparameterization, challenging classical overfitting predictions and motivating explanations based on optimization, loss geometry, and parameter-function bias.

DNNs often have more parameters than training examples, whereas classical learning theory associates overparameterization with overfitting and poorer generalization.
Randomly labelled CIFAR10 images showed that DNNs can memorize data nearly as readily as they train on uncorrupted data, sharpening the generalization puzzle.
SGD and flat stationary points have been proposed as explanations for why solutions generalize well, but these accounts do not provide a consensus fundamental explanation.
The paper studies whether the parameter-function map is biased toward simple functions and connects that bias to generalization through AIT and PAC-Bayes.

2 THE PARAMETER-FUNCTION MAP

The parameter-function map sends model parameters to the functions implemented by a supervised learning model. Its behavior matters because parameter-space search methods induce corresponding behavior in function space, where generalization is determined.

For a model with parameter space Θ and expressible function space F, the parameter-function map associates each parameter vector θ with its implemented function f_θ.
The map determines how algorithms searching parameter space, such as SGD, behave after their solutions are viewed in function space.
Generalization is governed by the resulting function-space behavior rather than parameter-space behavior alone.

3 ALGORITHMIC INFORMATION THEORY AND SIMPLICITY-BIAS IN THE PARAMETER-FUNCTION MAP

AIT supplies a probability-complexity bound linking output probability to descriptional complexity when the input-output map is sufficiently simple and redundant. Applied to DNNs, this motivates an expected simplicity bias in their parameter-function maps.

The AIT bound upper-bounds output probability using an approximation to Kolmogorov complexity, with map-dependent scalar parameters.
The bound requires a simplicity criterion for the map, additional conditions including redundancy, and typically simple or uniform input sampling.
If output complexity varies substantially, the bound predicts probability differences spanning many orders of magnitude, though it does not itself prove that a map is biased.
The DNN parameter-function map is argued to satisfy the relevant simplicity and redundancy conditions, suggesting that many DNNs exhibit simplicity bias.

4 SIMPLICITY BIAS IN A DNN IMPLEMENTING BOOLEAN FUNCTIONS

Random-parameter experiments show that a Boolean-function DNN strongly favors some functions over others, with high-probability functions tending to be simpler. The experiments connect this bias to generalization and motivate tests in larger networks.

Random parameter sampling estimates each function’s probability by counting how often sampled parameters produce that function.
The Boolean network uses 7 inputs, two hidden layers of 40 ReLU neurons, and one Boolean output, enabling a discrete function-space experiment.
Function probabilities span many orders of magnitude, while changing the parameter distribution has little effect on the overall probability-rank curve.
The probability-rank plot fits a parameter-free normalized Zipf law with NO = 2^128.
The fitted behavior implies an estimated 39-order-of-magnitude range in function probabilities and predicts limited dependence on parameter count once the network expresses all functions.
High-probability functions have low Lempel-Ziv complexity, with similar probability correlations appearing for Boolean-expression size and sensitivity-based measures.
The choice of complexity measure remains unresolved because different measures differ in how well they recognize regularity.
The experiments extend simplicity-bias testing to larger networks by sampling labelings produced by a four-layer CNN on 1,000 CIFAR10 images.

5 PAC-BAYES GENERALIZATION ERROR BOUNDS

The paper formulates PAC-Bayes bounds using a prior over DNN functions and estimates the required marginal likelihood through Gaussian-process approximations. Under an assumption that SGD samples nearly uniformly within the zero-error region, this yields bounds for expected generalization error.

PAC-Bayes bounds expected generalization error using a training-set-independent prior P over functions and a posterior distribution Q.The bound uses empirical error and the KL divergence between Q and P.
In the realizable case, the posterior Q* weights training-consistent functions proportionally to their prior probability P(c).This posterior minimizes the general PAC-Bayes bound, and its KL divergence simplifies to the data marginal likelihood P(U).
The function prior is induced by the parameter distribution through the parameter-function map, whose unequal parameter-space volumes create bias among functions.The analysis commonly uses a sufficiently broad Gaussian parameter distribution as an approximation to uniform sampling.
Infinite-width neural networks correspond to Gaussian processes, enabling estimates of function probabilities and marginal likelihoods from architecture-dependent kernels.The fully connected ReLU kernel has an analytical arccosine form, while convolutional and residual-network kernels can be computed efficiently.
Applying this construction to DNNs requires calculating P(U), the probability of the training-set output labels, also called marginal likelihood.For binary classification, real-valued network outputs are converted to labels through an output nonlinearity.
Direct sampling on small MNIST input sets shows agreement between neural-network and corresponding Gaussian-process labeling frequencies, supporting the approximation.The comparison uses m = 10 random MNIST images.

6 EXPERIMENTAL RESULTS FOR PAC BAYES

Experiments on binarized MNIST, fashion-MNIST, and CIFAR10 show that the PAC-Bayes bounds track generalization-error trends as label corruption increases. The estimated marginal likelihood falls sharply with corruption, distinguishing functions that generalize from those that merely memorize.

P(U) decreases over many orders of magnitude as label corruption increases, serving as a proxy for function complexity.The marginal likelihood is computed using the Gaussian-process approximation.
At low corruption, generalizing functions have much higher probability than high-corruption functions that merely memorize the training data.The result supports the paper’s proposed simplicity bias in the function prior.
At 0 label corruption, Table 1 reports mean generalization errors and PAC-Bayes bounds for convolutional and fully connected networks across three datasets.The networks are a 4-layer CNN and a 1-layer fully connected network, evaluated on samples of 10000.

7 SGD VERSUS BAYESIAN SAMPLING

The paper tests whether SGD behaves like near-uniform parameter sampling within the zero-error region by comparing SGD-trained networks with Bayesian and Gaussian-process approximations. The evidence is encouraging but remains limited and inconclusive.

The comparison evaluates SGD-trained networks against Bayesian parameter sampling and Gaussian-process approximations.The broader motivation is that Bayesian sampling has been reported to yield performance similar to SGD-trained networks.
The experiments provide direct evidence that two SGD variants find functions with probabilities close to those obtained by uniform parameter sampling within the zero-error region.The probability estimates are averaged over training sets and use the neural network from Section 4.
For a target Boolean function with LZ complexity 84.0, estimated probabilities of finding functions agree closely between SGD-like algorithms and approximate Bayesian inference.The agreement includes some scatter, partly attributable to sampling error and possible overestimation by the EP approximation.
The SGD-uniformity assumption remains an open question because the experiments are computationally limited and SGD may sometimes diverge from Bayesian parameter sampling.The authors describe the current evidence as promising rather than conclusive.

8 CONCLUSION AND FUTURE WORK

The paper argues that parameter-function bias toward simple functions provides a first-order explanation for generalization in highly overparameterized DNNs. Its PAC-Bayes analysis depends on several approximations and does not yet explain practical training tricks.

PAC-Bayes can support generalization guarantees for highly expressive models when priors are sufficiently biased toward the true distribution.The paper applies this idea to a prior over functions induced by DNN parameter-function maps.
The parameter-function map is argued to be strongly biased toward simple functions, with this bias expected to favor structured real-world solutions.The proposed explanation uses algorithmic information theory and descriptional complexity.
The approach does not yet explain how practical training tricks affect generalization, whose reported improvements are generally only a few percentage points.The stated aim is to explain the bulk of generalization in the highly overparameterized regime.
The PAC-Bayes bounds depend on approximating training-algorithm sampling, finite-width Gaussian-process behavior, marginal likelihood, and the correct function-space prior.The paper identifies these assumptions as potential sources of bound inaccuracy.
The bounds’ agreement with true-error behavior supports the overall approximation approach, although further validation—especially of the training-algorithm approximation—is needed.The authors state that one approximation is very good, while two others are reasonably good.

A BASIC EXPERIMENTAL DETAILS

The experiments use fully connected and convolutional ReLU networks trained mainly with SGD, while Boolean-function experiments additionally use adversarial SGD when ordinary SGD fails to reach zero error.

The main experiments use fully connected and convolutional architectures with ReLU activations and a single Softmax output neuron.Fully connected hidden-layer size matches the input dimension; convolutional networks use 200 filters.
Training uses SGD with learning rate 0.01 and early stopping when the entire training set reaches 100% accuracy.
Boolean-function experiments use adversarial SGD because ordinary SGD often fails to find zero-training-error solutions even after many iterations.The adversarial method succeeds in almost all cases described.
Adversarial SGD updates moving-average error scores for mini-batch examples and uses those scores to emphasize examples the network predicts poorly.
All experiments use binary cross entropy, although Adam learned the smaller Boolean networks only with mean-squared error.
Gaussian-process marginal-likelihood approximations use a Bernoulli likelihood with a probit link to approximate the Heaviside true likelihood.

B TESTING THE APPROXIMATIONS TO THE GAUSSIAN PROCESS MARGINAL

The study tests Gaussian-process marginal-likelihood approximations against empirical frequencies from parameter-sampled neural networks on random MNIST image labelings.

Empirical labeling frequencies from a two-hidden-layer, 784-unit-per-layer ReLU network are compared with Laplace and expectation-propagation Gaussian-process approximations.The network uses weight and bias variances σw = σb = 1.0 and a sample of 10 random MNIST images.

C THE CHOICE OF VARIANCE HYPERPARAMETERS

The PAC-Bayes bounds depend on weight and bias variance hyperparameters, with robustness varying by architecture and dataset. Variance choices that reflect trained parameter dispersions can substantially worsen the bounds.

The variance of weights and biases used to define the equivalent Gaussian process is a limitation because not all observed trends are robust to that choice.
For fully connected networks, weight variance has a larger effect than bias variance, while CIFAR10 bounds are best near the Gaussian-process phase transition.
Using variances measured after SGD training produces bounds above 50% for all corruption levels, substantially worse than the experimental variance choices.The measured variances were an order of magnitude smaller.
The measured post-training variance may reflect the zero-error surface as well as the prior, so it does not necessarily identify the Gaussian prior that best models SGD.
Figure 6 varies one standard-deviation hyperparameter at a time for 10000-instance samples and a two-layer fully connected network.The other parameter is fixed at 1.0.
Four-layer convolutional networks show sharper weight-variance transitions and greater dependence on bias variance than the fully connected case.

D DETAILS ON THE EXPERIMENTS COMPARING THE PROBABILITY OF FINDING A FUNCTION BY SGD AND NEURAL NETWORK GAUSSIAN PROCESSES

The experiments compare how often SGD and approximate Bayesian inference produce functions, then relate function probability to descriptional complexity using several measures. The analyses support a robust simplicity-bias pattern while documenting limitations of the complexity proxies and sampling setup.

Comparing function probabilities: Average probability estimates how often a function f is obtained across multiple training sets, separating algorithmic behavior from dependence on one dataset.For SGD-like methods, P(f|S_i) is estimated from repeated randomized runs; ABI uses a prior-based expression for consistent functions.
Comparing function probabilities: ABI assigns consistent functions probability proportional to their prior P(f), normalized by the training-set marginal likelihood P(S_i).The prior is computed from the Gaussian process corresponding to the architecture using an EP approximation.
Comparing function probabilities: Lower Gaussian-process hyperparameter variance produced significantly worse correlation between SGD and ABI function probabilities.Figure 8 compares the two probability estimates and reports correlation using Pearson ρ and its corresponding p value.
Simplicity-bias framework: Simplicity bias requires a simple map, input redundancy, finite output size, nonlinearity, and outputs that are not primarily pseudorandom.These conditions allow output probabilities to vary substantially and support complexity-based approximations to Kolmogorov complexity.
Simplicity-bias framework: For neural networks, parameters are inputs to the parameter-function map and induced functions are outputs; overparameterization and nonlinearity generally support the framework’s conditions.The paper notes that the well-behaved condition is less understood, while the absence of high-probability, high-complexity functions provides empirical validation.
Complexity measures: Different descriptional complexity measures show the same qualitative simplicity-bias behavior, suggesting robustness across measures.The experiments include Lempel-Ziv complexity, critical sample ratio, entropy, and Boolean-expression complexity; Lempel-Ziv is the primary measure in the main text.
Complexity measures: Lempel-Ziv complexity estimates regularity in Boolean-function strings, but its value depends on input ordering; numerical ordering is expected to make this effect negligible.The measure uses the number of words in a Lempel-Ziv dictionary, symmetrized over both string directions and scaled by log2(n).
Complexity measures: Entropy correlates with Lempel-Ziv complexity when entropy is low, but high entropy can still accompany low Lempel-Ziv complexity in regular strings.Alternating strings provide an example of high entropy with low descriptional complexity.

F.5 LEMPEL-ZIV VERSUS ENTROPY

The experiments separate entropy from richer complexity measures, showing that generalization varies among fixed-entropy target functions and that network depth changes the simplicity-bias distribution.

Complexity versus entropy: Fixed entropy does not determine generalization error: target-function complexity still correlates positively with error.Figure 17 fixes entropy at 1.0 and compares LZ and generalisation complexity.
Complexity versus entropy: Maximum-entropy functions that are simple under LZ complexity can generalize better than an unbiased learner.This indicates that entropy alone does not capture the complexity relevant to the network’s bias.
Sampling effects: The probability estimates for low-frequency functions suffer finite-size effects because a sample of size N cannot estimate probabilities below 1/N reliably.Figure 18 illustrates the changing frequency estimates for N = 10^6, 10^7, and 10^8.
Effect of depth: Increasing depth initially produces more higher-complexity functions, but from two hidden layers onward the complexity distribution shifts toward lower complexity.The authors attribute the initial increase to expressivity and report little further expressivity change beyond two layers.
Complexity-measure scope: LZ complexity is closer to Kolmogorov complexity than entropy, but it can still fail to measure some structured sequences such as the digits of π.The paper therefore treats stronger complexity measures as a better description of the networks’ simplicity bias.