# SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data

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

## Key facts

- Cited by 79 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2017.

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

- [Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training](https://mlsanity.com/paper/2102.02887/) (2021)
- [Theory of overparametrization in quantum neural networks](https://mlsanity.com/paper/2109.11676/) (2021)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias](https://mlsanity.com/paper/2110.13905/) (2021)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [On the geometry of generalization and memorization in deep neural networks](https://mlsanity.com/paper/2105.14602/) (2021)
- [Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.09974/) (2022)
- [Neural networks trained with SGD learn distributions of increasing complexity](https://mlsanity.com/paper/2211.11567/) (2022)
- [Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data](https://mlsanity.com/paper/2210.07082/) (2022)
- [On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths](https://mlsanity.com/paper/2101.09612/) (2021)
- [Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscape](https://mlsanity.com/paper/2201.08025/) (2022)
- [Understanding and Improving Feature Learning for Out-of-Distribution Generalization](https://mlsanity.com/paper/2304.11327/) (2023)
- [Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networks](https://mlsanity.com/paper/2306.04073/) (2023)
- [Early Neuron Alignment in Two-layer ReLU Networks with Small Initialization](https://mlsanity.com/paper/2307.12851/) (2023)
- [Implicit Full Waveform Inversion with Deep Neural Representation](https://mlsanity.com/paper/2209.03525/) (2022)
- [Graph Neural Networks Use Graphs When They Shouldn't](https://mlsanity.com/paper/2309.04332/) (2023)
- [Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs](https://mlsanity.com/paper/2110.05518/) (2021)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Experts](https://mlsanity.com/paper/2405.16646/) (2024)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [A Closer Look at Model Adaptation using Feature Distortion and Simplicity Bias](https://mlsanity.com/paper/2303.13500/) (2023)
- [Towards Understanding Learning in Neural Networks with Linear Teachers](https://mlsanity.com/paper/2101.02533/) (2021)
- [How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis](https://mlsanity.com/paper/2201.08514/) (2022)
- [Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise](https://mlsanity.com/paper/2101.01152/) (2021)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization](https://mlsanity.com/paper/2406.08654/) (2024)
- [Dynamic Sparse Training via Balancing the Exploration-Exploitation Trade-off](https://mlsanity.com/paper/2211.16667/) (2022)
- [Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks](https://mlsanity.com/paper/2110.09548/) (2021)
- [To update or not to update? Neurons at equilibrium in deep models](https://mlsanity.com/paper/2207.09455/) (2022)
- [ResMem: Learn what you can and memorize the rest](https://mlsanity.com/paper/2302.01576/) (2023)

## Abstract (arXiv)

Neural networks exhibit good generalization behavior in the over-parameterized regime, where the number of network parameters exceeds the number of observations. Nonetheless, current generalization bounds for neural networks fail to explain this phenomenon. In an attempt to bridge this gap, we study the problem of learning a two-layer over-parameterized neural network, when the data is generated by a linearly separable function. In the case where the network has Leaky ReLU activations, we provide both optimization and generalization guarantees for over-parameterized networks. Specifically, we prove convergence rates of SGD to a global minimum and provide generalization guarantees for this global minimum that are independent of the network size. Therefore, our result clearly shows that the use of SGD for optimization both finds a global minimum, and avoids overfitting despite the high capacity of the model. This is the first theoretical demonstration that SGD can avoid overfitting, when learning over-specified neural network classifiers.