Data to 14 Oct 2026

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

arXiv 1811.04918 ↗First posted 12 Nov 2018cs.LG cs.DS cs.NEcited by 340

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 92; 2022: 91; 2023: 53; 2024: 51; 2025: 36; 2026: 17.

340 papers.

Sort:

By area:

2022Not All Patches are What You Need: Expediting Vision Transformers via Token Reorganizationscited by 363
2021Training Neural Networks with Fixed Sparse Maskscited by 214
2021The Values Encoded in Machine Learning Researchcited by 172
2022Neural Networks can Learn Representations with Gradient Descentcited by 161
2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
2022A Kernel-Based View of Language Model Fine-Tuningcited by 121
2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 107
2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 102
2022The Design Space of E(3)-Equivariant Atom-Centered Interatomic Potentialscited by 101
2021Theory of overparametrization in quantum neural networkscited by 100

38 more

2022Neural Collapse: A Review on Modelling Principles and Generalizationcited by 95
2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 91
2021Learning with invariances in random features and kernel modelscited by 89
2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 83
2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
2021Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Modelscited by 76
2022Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputscited by 76
2021On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)cited by 73
2023FedExP: Speeding Up Federated Averaging via Extrapolationcited by 69
2021Model Complexity of Deep Learning: A Surveycited by 65
2024Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning?cited by 65
2021Wide Neural Networks Forget Less Catastrophicallycited by 64
2021Lost in Pruning: The Effects of Pruning Neural Networks beyond Test Accuracycited by 62
2022Towards Understanding Mixture of Experts in Deep Learningcited by 52
2022Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networkscited by 52
2022Predicting Out-of-Distribution Error with the Projection Normcited by 50
2021Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularizationcited by 49
2024From Lazy to Rich: Exact Learning Dynamics in Deep Linear Networkscited by 49
2022Beyond Explaining: Opportunities and Challenges of XAI-Based Model Improvementcited by 48
2021Heavy Tails in SGD and Compressibility of Overparametrized Neural Networkscited by 44
2022Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPscited by 42
2024Neural Network-Based Score Estimation in Diffusion Models: Optimization and Generalizationcited by 42
2024Get rich quick: exact solutions reveal how unbalanced initializations promote rapid feature learningcited by 42
2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
2021Recent Advances on Neural Network Pruning at Initializationcited by 41
2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 40
2022Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descentcited by 39
2023A Survey on Efficient Training of Transformerscited by 39
2022The Mechanism of Prediction Head in Non-contrastive Self-supervised Learningcited by 38
2022Pareto Invariant Risk Minimization: Towards Mitigating the Optimization Dilemma in Out-of-Distribution Generalizationcited by 38
2022On the Power of Foundation Modelscited by 37
2023Scaling MLPs: A Tale of Inductive Biascited by 37
2023On the Stepwise Nature of Self-Supervised Learningcited by 36
2021On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layerscited by 35
2022Understanding Deep Contrastive Learning via Coordinate-wise Optimizationcited by 35
2022Limitations of the NTK for Understanding Generalization in Deep Learningcited by 35
2023Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networkscited by 35

50 most cited of 340 All 340 (JSON)