# Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers

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

## Key facts

- Cited by 340 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2018.

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

- [Not All Patches are What You Need: Expediting Vision Transformers via Token Reorganizations](https://mlsanity.com/paper/2202.07800/) (2022)
- [Training Neural Networks with Fixed Sparse Masks](https://mlsanity.com/paper/2111.09839/) (2021)
- [The Values Encoded in Machine Learning Research](https://mlsanity.com/paper/2106.15590/) (2021)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [A Kernel-Based View of Language Model Fine-Tuning](https://mlsanity.com/paper/2210.05643/) (2022)
- [Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learning](https://mlsanity.com/paper/2105.15134/) (2021)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [What Happens after SGD Reaches Zero Loss? --A Mathematical Framework](https://mlsanity.com/paper/2110.06914/) (2021)
- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [The Design Space of E(3)-Equivariant Atom-Centered Interatomic Potentials](https://mlsanity.com/paper/2205.06643/) (2022)
- [Theory of overparametrization in quantum neural networks](https://mlsanity.com/paper/2109.11676/) (2021)
- [Neural Collapse: A Review on Modelling Principles and Generalization](https://mlsanity.com/paper/2206.04041/) (2022)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction](https://mlsanity.com/paper/2206.07085/) (2022)
- [Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias](https://mlsanity.com/paper/2110.13905/) (2021)
- [A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity](https://mlsanity.com/paper/2302.06015/) (2023)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs](https://mlsanity.com/paper/2206.00939/) (2022)
- [On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)](https://mlsanity.com/paper/2102.12470/) (2021)
- [FedExP: Speeding Up Federated Averaging via Extrapolation](https://mlsanity.com/paper/2301.09604/) (2023)
- [Model Complexity of Deep Learning: A Survey](https://mlsanity.com/paper/2103.05127/) (2021)
- [Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning?](https://mlsanity.com/paper/2410.08292/) (2024)
- [Wide Neural Networks Forget Less Catastrophically](https://mlsanity.com/paper/2110.11526/) (2021)
- [Lost in Pruning: The Effects of Pruning Neural Networks beyond Test Accuracy](https://mlsanity.com/paper/2103.03014/) (2021)
- [Towards Understanding Mixture of Experts in Deep Learning](https://mlsanity.com/paper/2208.02813/) (2022)
- [Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.09974/) (2022)
- [Predicting Out-of-Distribution Error with the Projection Norm](https://mlsanity.com/paper/2202.05834/) (2022)
- [Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization](https://mlsanity.com/paper/2108.11371/) (2021)

## Abstract (arXiv)

The fundamental learning theory behind neural networks remains largely open. What classes of functions can neural networks actually learn? Why doesn't the trained network overfit when it is overparameterized? In this work, we prove that overparameterized neural networks can learn some notable concept classes, including two and three-layer networks with fewer parameters and smooth activations. Moreover, the learning can be simply done by SGD (stochastic gradient descent) or its variants in polynomial time using polynomially many samples. The sample complexity can also be almost independent of the number of parameters in the network. On the technique side, our analysis goes beyond the so-called NTK (neural tangent kernel) linearization of neural networks in prior works. We establish a new notion of quadratic approximation of the neural network (that can be viewed as a second-order variant of NTK), and connect it to the SGD theory of escaping saddle points.