# A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 41 references that are in the map.
- First posted on arXiv 4 Feb 2021.

## Builds on (most cited first, 30 of 31)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit](https://mlsanity.com/paper/1902.06015/) (2019)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Mean Field Analysis of Neural Networks: A Central Limit Theorem](https://mlsanity.com/paper/1808.09372/) (2018)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [A Rigorous Framework for the Mean Field Limit of Multilayer Neural Networks](https://mlsanity.com/paper/2001.11443/) (2020)
- [A Mean-field Analysis of Deep ResNet and Beyond: Towards Provable Optimization Via Overparameterization From Depth](https://mlsanity.com/paper/2003.05508/) (2020)
- [Stochastic Particle Gradient Descent for Infinite Ensembles](https://mlsanity.com/paper/1712.05438/) (2017)
- [Learning One-hidden-layer ReLU Networks via Gradient Descent](https://mlsanity.com/paper/1806.07808/) (2018)
- [Sparse Optimization on Measures with Over-parameterized Gradient Descent](https://mlsanity.com/paper/1907.10300/) (2019)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/2007.01452/) (2020)
- [The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks](https://mlsanity.com/paper/2006.01005/) (2020)
- [Learning Two-layer Neural Networks with Symmetric Inputs](https://mlsanity.com/paper/1810.06793/) (2018)
- [Learning One Convolutional Layer with Overlapping Patches](https://mlsanity.com/paper/1802.02547/) (2018)

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

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs](https://mlsanity.com/paper/2206.00939/) (2022)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Features](https://mlsanity.com/paper/2206.01717/) (2022)
- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron](https://mlsanity.com/paper/2302.10034/) (2023)
- [Parameter identifiability of a deep feedforward ReLU neural network](https://mlsanity.com/paper/2112.12982/) (2021)
- [On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias](https://mlsanity.com/paper/2205.09072/) (2022)
- [Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization)](https://mlsanity.com/paper/2209.07263/) (2022)
- [On Learnability via Gradient Method for Two-Layer ReLU Neural Networks in Teacher-Student Setting](https://mlsanity.com/paper/2106.06251/) (2021)
- [Gradient Descent on Infinitely Wide Neural Networks: Global Convergence and Generalization](https://mlsanity.com/paper/2110.08084/) (2021)
- [Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/2307.06887/) (2023)
- [Provable Guarantees for Neural Networks via Gradient Feature Learning](https://mlsanity.com/paper/2310.12408/) (2023)
- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [On Feature Learning in Neural Networks with Global Convergence Guarantees](https://mlsanity.com/paper/2204.10782/) (2022)
- [The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge to Extreme Points of the Dual Convex Program](https://mlsanity.com/paper/2110.06488/) (2021)
- [Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time](https://mlsanity.com/paper/2402.03625/) (2024)
- [Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methods](https://mlsanity.com/paper/2205.14818/) (2022)
- [Efficient Uncertainty Quantification and Reduction for Over-Parameterized Neural Networks](https://mlsanity.com/paper/2306.05674/) (2023)
- [Sparse Bayesian Deep Learning for Dynamic System Identification](https://mlsanity.com/paper/2107.12910/) (2021)
- [Depth Separation with Multilayer Mean-Field Networks](https://mlsanity.com/paper/2304.01063/) (2023)
- [When Expressivity Meets Trainability: Fewer than n Neurons Can Work](https://mlsanity.com/paper/2210.12001/) (2022)
- [Deep Networks Provably Classify Data on Curves](https://mlsanity.com/paper/2107.14324/) (2021)
- [Early Stage Convergence and Global Convergence of Training Mildly Parameterized Neural Networks](https://mlsanity.com/paper/2206.02139/) (2022)
- [Optimizing the Performative Risk under Weak Convexity Assumptions](https://mlsanity.com/paper/2209.00771/) (2022)
- [Global Convergence of SGD On Two Layer Neural Nets](https://mlsanity.com/paper/2210.11452/) (2022)
- [Finite Sample Identification of Wide Shallow Neural Networks with Biases](https://mlsanity.com/paper/2211.04589/) (2022)
- ["Yes, My LoRD." Guiding Language Model Extraction with Locality Reinforced Distillation](https://mlsanity.com/paper/2409.02718/) (2024)
- [Toward L_∞-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields](https://mlsanity.com/paper/2305.00322/) (2023)

## Abstract (arXiv)

While over-parameterization is widely believed to be crucial for the success of optimization for the neural networks, most existing theories on over-parameterization do not fully explain the reason -- they either work in the Neural Tangent Kernel regime where neurons don't move much, or require an enormous number of neurons. In practice, when the data is generated using a teacher neural network, even mildly over-parameterized neural networks can achieve 0 loss and recover the directions of teacher neurons. In this paper we develop a local convergence theory for mildly over-parameterized two-layer neural net. We show that as long as the loss is already lower than a threshold (polynomial in relevant parameters), all student neurons in an over-parameterized two-layer neural network will converge to one of teacher neurons, and the loss will go to 0. Our result holds for any number of student neurons as long as it is at least as large as the number of teacher neurons, and our convergence rate is independent of the number of student neurons. A key component of our analysis is the new characterization of local optimization landscape -- we show the gradient satisfies a special case of Lojasiewicz property which is different from local strong convexity or PL conditions used in previous work.