# Why does deep and cheap learning work so well?

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

## Key facts

- Cited by 100 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2016.

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

- [KAN: Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2404.19756/) (2024)
- [Deep physical neural networks enabled by a backpropagation algorithm for arbitrary physical systems](https://mlsanity.com/paper/2104.13386/) (2021)
- [On the approximation of functions by tanh neural networks](https://mlsanity.com/paper/2104.08938/) (2021)
- [Why neural networks find simple solutions: the many regularizers of geometric complexity](https://mlsanity.com/paper/2209.13083/) (2022)
- [Deep neural networks have an inbuilt Occam's razor](https://mlsanity.com/paper/2304.06670/) (2023)
- [Image sensing with multilayer, nonlinear optical neural networks](https://mlsanity.com/paper/2207.14293/) (2022)
- [GenPhys: From Physical Processes to Generative Models](https://mlsanity.com/paper/2304.02637/) (2023)
- [Deep ReLU Networks Preserve Expected Length](https://mlsanity.com/paper/2102.10492/) (2021)
- [Renormalizing Diffusion Models](https://mlsanity.com/paper/2308.12355/) (2023)
- [Towards quantifying information flows: relative entropy in deep neural networks and the renormalization group](https://mlsanity.com/paper/2107.06898/) (2021)
- [Explicitly antisymmetrized neural network layers for variational Monte Carlo simulation](https://mlsanity.com/paper/2112.03491/) (2021)
- [Precision Machine Learning](https://mlsanity.com/paper/2210.13447/) (2022)
- [Bayesian Renormalization](https://mlsanity.com/paper/2305.10491/) (2023)
- [Why flatness does and does not correlate with generalization for deep neural networks](https://mlsanity.com/paper/2103.06219/) (2021)
- [Tensor networks and efficient descriptions of classical data](https://mlsanity.com/paper/2103.06872/) (2021)
- [Impossibility Results in AI: A Survey](https://mlsanity.com/paper/2109.00484/) (2021)
- [Do We Always Need the Simplicity Bias? Looking for Optimal Inductive Biases in the Wild](https://mlsanity.com/paper/2503.10065/) (2025)
- [Reverse Engineering the Neural Tangent Kernel](https://mlsanity.com/paper/2106.03186/) (2021)
- [Decomposing neural networks as mappings of correlation functions](https://mlsanity.com/paper/2202.04925/) (2022)
- [Wavelet Conditional Renormalization Group](https://mlsanity.com/paper/2207.04941/) (2022)
- [Machine-Learning Non-Conservative Dynamics for New-Physics Detection](https://mlsanity.com/paper/2106.00026/) (2021)
- [Hierarchical quantum circuit representations for neural architecture search](https://mlsanity.com/paper/2210.15073/) (2022)
- [A Hyperparameter Study for Quantum Kernel Methods](https://mlsanity.com/paper/2310.11891/) (2023)
- [Universality of Winning Tickets: A Renormalization Group Perspective](https://mlsanity.com/paper/2110.03210/) (2021)
- [When Expressivity Meets Trainability: Fewer than n Neurons Can Work](https://mlsanity.com/paper/2210.12001/) (2022)
- [The Autodidactic Universe](https://mlsanity.com/paper/2104.03902/) (2021)
- [Renormalization in the neural network-quantum field theory correspondence](https://mlsanity.com/paper/2212.11811/) (2022)
- [Multilevel Generative Samplers for Investigating Critical Phenomena](https://mlsanity.com/paper/2503.08918/) (2025)
- [Compositionality Unlocks Deep Interpretable Models](https://mlsanity.com/paper/2504.02667/) (2025)
- [A Mathematical Philosophy of Explanations in Mechanistic Interpretability -- The Strange Science Part I.i](https://mlsanity.com/paper/2505.00808/) (2025)

## Abstract (arXiv)

We show how the success of deep learning could depend not only on mathematics but also on physics: although well-known mathematical theorems guarantee that neural networks can approximate arbitrary functions well, the class of functions of practical interest can frequently be approximated through "cheap learning" with exponentially fewer parameters than generic ones. We explore how properties frequently encountered in physics such as symmetry, locality, compositionality, and polynomial log-probability translate into exceptionally simple neural networks. We further argue that when the statistical process generating the data is of a certain hierarchical form prevalent in physics and machine-learning, a deep neural network can be more efficient than a shallow one. We formalize these claims using information theory and discuss the relation to the renormalization group. We prove various "no-flattening theorems" showing when efficient linear deep networks cannot be accurately approximated by shallow ones without efficiency loss, for example, we show that n variables cannot be multiplied using fewer than 2n neurons in a single hidden layer.