Data to 7 Oct 2026

Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data

arXiv 1808.01204 ↗First posted 3 Aug 2018cs.LG stat.MLcited by 260

Not on the map. Why?

Abstract (arXiv)

Neural networks have many successful applications, while much less theoretical understanding has been gained. Towards bridging this gap, we study the problem of learning a two-layer overparameterized ReLU neural network for multi-class classification via stochastic gradient descent (SGD) from random initialization. In the overparameterized setting, when the data comes from mixtures of well-separated distributions, we prove that SGD learns a network with a small generalization error, albeit the network has enough capacity to fit arbitrary labels. Furthermore, the analysis provides interesting insights into several aspects of learning neural networks and can be verified based on empirical studies on synthetic data and on the MNIST dataset.

Key facts. Cited by 260 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Aug 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 87; 2022: 57; 2023: 49; 2024: 40; 2025: 15; 2026: 11.

260 papers.

Sort:

By area:

2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,084
2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 413
2021The Values Encoded in Machine Learning Researchcited by 172
2022Neural Networks can Learn Representations with Gradient Descentcited by 161
2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
2022A Kernel-Based View of Language Model Fine-Tuningcited by 118
2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
2021Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Trainingcited by 107
2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 106
2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 101
2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 90
2021Learning with invariances in random features and kernel modelscited by 89

38 more

2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
2022Understanding the unstable convergence of gradient descentcited by 84
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 75
2021On the geometry of generalization and memorization in deep neural networkscited by 71
2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 67
2023Transformers as Support Vector Machinescited by 67
2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
2022Towards Understanding Mixture of Experts in Deep Learningcited by 52
2023JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attentioncited by 52
2021Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularizationcited by 48
2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
2023An Over-parameterized Exponential Regressioncited by 45
2022Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regressioncited by 42
2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 39
2021HYDRA: Hypergradient Data Relevance Analysis for Interpreting Deep Neural Networkscited by 38
2022Why neural networks find simple solutions: the many regularizers of geometric complexitycited by 38
2023A Survey on Efficient Training of Transformerscited by 37
2021On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layerscited by 35
2023Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networkscited by 35
2021Early-stopped neural networks are consistentcited by 34
2021Fast Margin Maximization via Dual Accelerationcited by 33
2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
2022GEMEL: Model Merging for Memory-Efficient, Real-Time Video Analytics at the Edgecited by 32
2021Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environmentscited by 30
2023On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domainscited by 30
2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
2022One-Pixel Shortcut: on the Learning Preference of Deep Neural Networkscited by 29
2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
2021Properties of the After Kernelcited by 27
2021Subquadratic Overparameterization for Shallow Neural Networkscited by 26
2021Rethinking Influence Functions of Neural Networks in the Over-parameterized Regimecited by 26
2023How to Protect Copyright Data in Optimization of Large Language Models?cited by 26
2022On the Generalization Mystery in Deep Learningcited by 25
2023Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuroncited by 25

50 most cited of 260 All 260 (JSON)