# Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks

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

## Key facts

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

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

- [Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training](https://mlsanity.com/paper/2101.12699/) (2021)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [On the Convergence and Robustness of Adversarial Training](https://mlsanity.com/paper/2112.08304/) (2021)
- [Understanding Gradient Descent on Edge of Stability in Deep Learning](https://mlsanity.com/paper/2205.09745/) (2022)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training](https://mlsanity.com/paper/2102.02887/) (2021)
- [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)
- [Tensor Programs IIb: Architectural Universality of Neural Tangent Kernel Training Dynamics](https://mlsanity.com/paper/2105.03703/) (2021)
- [Deep Kronecker neural networks: A general framework for neural networks with adaptive activation functions](https://mlsanity.com/paper/2105.09513/) (2021)
- [A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Features](https://mlsanity.com/paper/2206.01717/) (2022)
- [LoRA Training in the NTK Regime has No Spurious Local Minima](https://mlsanity.com/paper/2402.11867/) (2024)
- [Beyond the Quadratic Approximation: the Multiscale Structure of Neural Network Loss Landscapes](https://mlsanity.com/paper/2204.11326/) (2022)
- [Embedding Principle of Loss Landscape of Deep Neural Networks](https://mlsanity.com/paper/2105.14573/) (2021)
- [On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layers](https://mlsanity.com/paper/2102.07346/) (2021)
- [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024)
- [Early-stopped neural networks are consistent](https://mlsanity.com/paper/2106.05932/) (2021)
- [Continuous vs. Discrete Optimization of Deep Neural Networks](https://mlsanity.com/paper/2107.06608/) (2021)
- [The Future is Log-Gaussian: ResNets and Their Infinite-Depth-and-Width Limit at Initialization](https://mlsanity.com/paper/2106.04013/) (2021)
- [Scaling Neural Tangent Kernels via Sketching and Random Features](https://mlsanity.com/paper/2106.07880/) (2021)
- [Spectral Evolution and Invariance in Linear-width Neural Networks](https://mlsanity.com/paper/2211.06506/) (2022)
- [Subquadratic Overparameterization for Shallow Neural Networks](https://mlsanity.com/paper/2111.01875/) (2021)
- [On the Generalization Mystery in Deep Learning](https://mlsanity.com/paper/2203.10036/) (2022)
- [Overparameterization of deep ResNet: zero loss and mean-field analysis](https://mlsanity.com/paper/2105.14417/) (2021)
- [Embedding Principle: a hierarchical structure of loss landscape of deep neural networks](https://mlsanity.com/paper/2111.15527/) (2021)
- [Characterizing the Spectrum of the NTK via a Power Series Expansion](https://mlsanity.com/paper/2211.07844/) (2022)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [Learning with convolution and pooling operations in kernel methods](https://mlsanity.com/paper/2111.08308/) (2021)
- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)

## Abstract (arXiv)

We study the problem of training deep neural networks with Rectified Linear Unit (ReLU) activation function using gradient descent and stochastic gradient descent. In particular, we study the binary classification problem and show that for a broad family of loss functions, with proper random weight initialization, both gradient descent and stochastic gradient descent can find the global minima of the training loss for an over-parameterized deep ReLU network, under mild assumption on the training data. The key idea of our proof is that Gaussian random initialization followed by (stochastic) gradient descent produces a sequence of iterates that stay inside a small perturbation region centering around the initial weights, in which the empirical loss function of deep ReLU networks enjoys nice local curvature properties that ensure the global convergence of (stochastic) gradient descent. Our theoretical results shed light on understanding the optimization for deep learning, and pave the way for studying the optimization dynamics of training modern deep neural networks.