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

arXiv: https://arxiv.org/abs/1805.08522 · HTML: https://mlsanity.com/paper/1805.08522/

## Key facts

- Cited by 183 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2018.

## Built on by (most cited first, 30 of 183)

- [Sleeper Agents: Training Deceptive LLMs that Persist Through Safety Training](https://mlsanity.com/paper/2401.05566/) (2024)
- [The Platonic Representation Hypothesis](https://mlsanity.com/paper/2405.07987/) (2024)
- [The Alignment Problem from a Deep Learning Perspective](https://mlsanity.com/paper/2209.00626/) (2022)
- [Fishr: Invariant Gradient Variances for Out-of-Distribution Generalization](https://mlsanity.com/paper/2109.02934/) (2021)
- [The Low-Rank Simplicity Bias in Deep Networks](https://mlsanity.com/paper/2103.10427/) (2021)
- [Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMs](https://mlsanity.com/paper/2309.07311/) (2023)
- [Goal Misgeneralization in Deep Reinforcement Learning](https://mlsanity.com/paper/2105.14111/) (2021)
- [The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains](https://mlsanity.com/paper/2402.11004/) (2024)
- [SimBa: Simplicity Bias for Scaling Up Parameters in Deep Reinforcement Learning](https://mlsanity.com/paper/2410.09754/) (2024)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [Can Large Reasoning Models Self-Train?](https://mlsanity.com/paper/2505.21444/) (2025)
- [MaskTune: Mitigating Spurious Correlations by Forcing to Explore](https://mlsanity.com/paper/2210.00055/) (2022)
- [On the Foundations of Shortcut Learning](https://mlsanity.com/paper/2310.16228/) (2023)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [Which Shortcut Cues Will DNNs Choose? A Study from the Parameter-Space Perspective](https://mlsanity.com/paper/2110.03095/) (2021)
- [The Local Learning Coefficient: A Singularity-Aware Complexity Measure](https://mlsanity.com/paper/2308.12108/) (2023)
- [Mechanistic Mode Connectivity](https://mlsanity.com/paper/2211.08422/) (2022)
- [Neural networks trained with SGD learn distributions of increasing complexity](https://mlsanity.com/paper/2211.11567/) (2022)
- [Neural Redshift: Random Networks are not Random Functions](https://mlsanity.com/paper/2403.02241/) (2024)
- [Fortuitous Forgetting in Connectionist Networks](https://mlsanity.com/paper/2202.00155/) (2022)
- [A Little Robustness Goes a Long Way: Leveraging Robust Features for Targeted Transfer Attacks](https://mlsanity.com/paper/2106.02105/) (2021)
- [The Tunnel Effect: Building Data Representations in Deep Neural Networks](https://mlsanity.com/paper/2305.19753/) (2023)
- [Out-of-Domain Generalization in Dynamical Systems Reconstruction](https://mlsanity.com/paper/2402.18377/) (2024)
- [Overwriting Pretrained Bias with Finetuning Data](https://mlsanity.com/paper/2303.06167/) (2023)
- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [Neural Networks Learn Statistics of Increasing Complexity](https://mlsanity.com/paper/2402.04362/) (2024)
- [Don't blame Dataset Shift! Shortcut Learning due to Gradients and Cross Entropy](https://mlsanity.com/paper/2308.12553/) (2023)
- [Sensitivity as a Complexity Measure for Sequence Classification Tasks](https://mlsanity.com/paper/2104.10343/) (2021)
- [Deep neural networks have an inbuilt Occam's razor](https://mlsanity.com/paper/2304.06670/) (2023)
- [Mitigating and Evaluating Static Bias of Action Representations in the Background and the Foreground](https://mlsanity.com/paper/2211.12883/) (2022)

## Abstract (arXiv)

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.