# Convergence Analysis of Two-layer Neural Networks with ReLU Activation

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

## Key facts

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

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

- [Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models](https://mlsanity.com/paper/2208.06677/) (2022)
- [Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learning](https://mlsanity.com/paper/2105.15134/) (2021)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021)
- [Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscape](https://mlsanity.com/paper/2201.08025/) (2022)
- [The Mechanism of Prediction Head in Non-contrastive Self-supervised Learning](https://mlsanity.com/paper/2205.06226/) (2022)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [On the Power of Foundation Models](https://mlsanity.com/paper/2211.16327/) (2022)
- [Scaling MLPs: A Tale of Inductive Bias](https://mlsanity.com/paper/2306.13575/) (2023)
- [FedCP: Separating Feature Information for Personalized Federated Learning via Conditional Policy](https://mlsanity.com/paper/2307.01217/) (2023)
- [Taxonomizing local versus global structure in neural network loss landscapes](https://mlsanity.com/paper/2107.11228/) (2021)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Implicit Full Waveform Inversion with Deep Neural Representation](https://mlsanity.com/paper/2209.03525/) (2022)
- [Evaluating the design space of diffusion-based generative models](https://mlsanity.com/paper/2406.12839/) (2024)
- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron](https://mlsanity.com/paper/2302.10034/) (2023)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Parameter identifiability of a deep feedforward ReLU neural network](https://mlsanity.com/paper/2112.12982/) (2021)
- [Generalizing Weather Forecast to Fine-grained Temporal Scales via Physics-AI Hybrid Modeling](https://mlsanity.com/paper/2405.13796/) (2024)
- [On the Impact of Overparameterization on the Training of a Shallow Neural Network in High Dimensions](https://mlsanity.com/paper/2311.03794/) (2023)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function](https://mlsanity.com/paper/2205.12856/) (2022)
- [Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression](https://mlsanity.com/paper/2306.00788/) (2023)
- [GradSign: Model Performance Inference with Theoretical Insights](https://mlsanity.com/paper/2110.08616/) (2021)
- [How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis](https://mlsanity.com/paper/2201.08514/) (2022)
- [Understanding the Role of Nonlinearity in Training Dynamics of Contrastive Learning](https://mlsanity.com/paper/2206.01342/) (2022)
- [GPFL: Simultaneously Learning Global and Personalized Feature Information for Personalized Federated Learning](https://mlsanity.com/paper/2308.10279/) (2023)
- [On Learnability via Gradient Method for Two-Layer ReLU Neural Networks in Teacher-Student Setting](https://mlsanity.com/paper/2106.06251/) (2021)

## Abstract (arXiv)

In recent years, stochastic gradient descent (SGD) based techniques has become the standard tools for training neural networks. However, formal theoretical understanding of why SGD can train neural networks in practice is largely missing. In this paper, we make progress on understanding this mystery by providing a convergence analysis for SGD on a rich subset of two-layer feedforward networks with ReLU activations. This subset is characterized by a special structure called "identity mapping". We prove that, if input follows from Gaussian distribution, with standard O(1/√d) initialization of the weights, SGD converges to the global minimum in polynomial number of steps. Unlike normal vanilla networks, the "identity mapping" makes our network asymmetric and thus the global minimum is unique. To complement our theory, we are also able to show experimentally that multi-layer networks with this mapping have better performance compared with normal vanilla networks. Our convergence theorem differs from traditional non-convex optimization techniques. We show that SGD converges to optimal in "two phases": In phase I, the gradient points to the wrong direction, however, a potential function g gradually decreases. Then in phase II, SGD enters a nice one point convex region and converges. We also show that the identity mapping is necessary for convergence, as it moves the initial point to a better place for optimization. Experiment verifies our claims.