Neural Networks Generalize on Low Complexity Data
Not on the map. Why?
Abstract (arXiv)
We show that feedforward neural networks with ReLU activation generalize on low complexity data, suitably defined. Given i.i.d.~data generated from a simple programming language, the minimum description length (MDL) feedforward neural network which interpolates the data generalizes with high probability. We define this simple programming language, along with a notion of description length of such networks. We provide several examples on basic computational tasks, such as checking primality of a natural number. For primality testing, our theorem shows the following and more. Suppose that we draw an i.i.d.~sample of n numbers uniformly at random from 1 to N. For each number xi, let yi = 1 if xi is a prime and 0 if it is not. Then, the interpolating MDL network accurately answers, with probability 1- O((ln N)/n), whether a newly drawn number between 1 and N is a prime or not. Note that the network is not designed to detect primes; minimum description learning discovers a network which does so. Extensions to noisy data are also discussed, suggesting that MDL neural network interpolators can demonstrate tempered overfitting.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 47 of its 82 references that are in the map. First posted on arXiv 19 Sep 2024.
Builds on
47 of 82 references.
References · 47
- 2017Attention Is All You Needcited by 59,932
- 2020Language Models are Few-Shot Learnerscited by 32,199
- 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
- 2023Progress measures for grokking via mechanistic interpretabilitycited by 822
- 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
- 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 667
- 2019Benign Overfitting in Linear Regressioncited by 544
- 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
- 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 291
- 2020Transformers as Soft Reasoners over Languagecited by 265
- 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
- 2022Transformers Learn Shortcuts to Automatacited by 260
35 more
- 2021Deep learning: a statistical viewpointcited by 239
- 2023Looped Transformers as Programmable Computerscited by 224
- 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
- 2021Thinking Like Transformerscited by 182
- 2018Deep learning generalizes because the parameter-function map is biased towards simple functionscited by 180
- 2020Benign overfitting in ridge regressioncited by 152
- 2023Representational Strengths and Limitations of Transformerscited by 132
- 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
- 2023What Formal Languages Can Transformers Express? A Surveycited by 120
- 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
- 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 99
- 2023Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcited by 82
- 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
- 2022An Introduction to Neural Data Compressioncited by 78
- 2019Nonparametric Regression on Low-Dimensional Manifolds using Deep ReLU Networks : Function Approximation and Statistical Recoverycited by 73
- 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
- 2014On the Computational Efficiency of Training Neural Networkscited by 71
- 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
- 2023The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learningcited by 63
- 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
- 2024Neural Redshift: Random Networks are not Random Functionscited by 43
- 2023Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Modelscited by 39
- 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 35
- 2024Transformers Can Represent n-gram Language Modelscited by 31
- 2017Recurrent Neural Networks as Weighted Language Recognizerscited by 30
- 2024Learning Universal Predictorscited by 29
- 2019Neural networks are a priori biased towards Boolean functions with low entropycited by 24
- 2021Minimum Description Length Recurrent Neural Networkscited by 23
- 2024On Provable Length and Compositional Generalizationcited by 22
- 2024Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannotcited by 21
- 2018A Provably Correct Algorithm for Deep Learning that Actually Workscited by 19
- 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
- 2023On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networkscited by 8
- 2023Interpolation Learning With Minimum Description Lengthcited by 5
- 2024Understanding Deep Learning via Notions of Rankcited by 1
Built on by
Citing papers per year: 2025: 3.
3 papers.