# Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 51 references that are in the map.
- First posted on arXiv 20 Feb 2023.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (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)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (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)
- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Convergence Analysis of Two-layer Neural Networks with ReLU Activation](https://mlsanity.com/paper/1705.09886/) (2017)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs](https://mlsanity.com/paper/2206.00939/) (2022)
- [A Rigorous Framework for the Mean Field Limit of Multilayer Neural Networks](https://mlsanity.com/paper/2001.11443/) (2020)
- [Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs](https://mlsanity.com/paper/1702.07966/) (2017)
- [A Mean-field Analysis of Deep ResNet and Beyond: Towards Provable Optimization Via Overparameterization From Depth](https://mlsanity.com/paper/2003.05508/) (2020)
- [Learning ReLUs via Gradient Descent](https://mlsanity.com/paper/1705.04591/) (2017)
- [An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis](https://mlsanity.com/paper/1703.00560/) (2017)
- [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)
- [Learning a Single Neuron with Gradient Methods](https://mlsanity.com/paper/2001.05205/) (2020)
- [A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network](https://mlsanity.com/paper/2102.02410/) (2021)
- [Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/2007.01452/) (2020)
- [Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima](https://mlsanity.com/paper/1712.00779/) (2017)
- [Singularity, Misspecification, and the Convergence Rate of EM](https://mlsanity.com/paper/1810.00828/) (2018)

## Built on by (most cited first, 25 of 25)

- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attention](https://mlsanity.com/paper/2310.00535/) (2023)
- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Time](https://mlsanity.com/paper/2306.16361/) (2023)
- [LoRA Training Provably Converges to a Low-Rank Global Minimum or It Fails Loudly (But it Probably Won't Fail)](https://mlsanity.com/paper/2502.09376/) (2025)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs](https://mlsanity.com/paper/2306.06479/) (2023)
- [Simplicity Bias of Two-Layer Networks beyond Linearly Separable Data](https://mlsanity.com/paper/2405.17299/) (2024)
- [Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergence](https://mlsanity.com/paper/2411.08798/) (2024)
- [Should Under-parameterized Student Networks Copy or Average Teacher Weights?](https://mlsanity.com/paper/2311.01644/) (2023)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Models](https://mlsanity.com/paper/2407.00490/) (2024)
- [On the Limitations of Language Targeted Pruning: Investigating the Calibration Language Impact in Multilingual LLM Pruning](https://mlsanity.com/paper/2408.14398/) (2024)
- [On the Benefits of Weight Normalization for Overparameterized Matrix Sensing](https://mlsanity.com/paper/2510.01175/) (2025)
- [Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussian](https://mlsanity.com/paper/2511.22069/) (2025)
- [When Both Layers Learn: Training Dynamics of Representing Linear Models via ReLU Networks](https://mlsanity.com/paper/2606.04476/) (2026)
- [Hidden Gauge Controls Feature Specialization in ReLU Networks](https://mlsanity.com/paper/2608.06766/) (2026)
- [First-order ANIL provably learns representations despite overparametrization](https://mlsanity.com/paper/2303.01335/) (2023)
- [Disentangle Sample Size and Initialization Effect on Perfect Generalization for Single-Neuron Target](https://mlsanity.com/paper/2405.13787/) (2024)
- [The Role of Depth, Width, and Tree Size in Expressiveness of Deep Forest](https://mlsanity.com/paper/2407.05108/) (2024)
- [A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyond](https://mlsanity.com/paper/2510.19382/) (2025)
- [Zero Generalization Error Theorem for Random Interpolators via Algebraic Geometry](https://mlsanity.com/paper/2512.06347/) (2025)
- [A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity](https://mlsanity.com/paper/2604.13393/) (2026)
- [Local linear convergence of gradient methods for overparameterized Gaussian mixtures](https://mlsanity.com/paper/2605.30936/) (2026)
- [Two-Timescale Fine-tuning Provably Learns New Features for Two-Layer ReLU Networks](https://mlsanity.com/paper/2609.34667/) (2026)

## Abstract (arXiv)

We revisit the problem of learning a single neuron with ReLU activation under Gaussian input with square loss. We particularly focus on the over-parameterization setting where the student network has n≥ 2 neurons. We prove the global convergence of randomly initialized gradient descent with a Oleft(T-3right) rate. This is the first global convergence result for this problem beyond the exact-parameterization setting (n=1) in which the gradient descent enjoys an exp(-Omega(T)) rate. Perhaps surprisingly, we further present an Omegaleft(T-3right) lower bound for randomly initialized gradient flow in the over-parameterization setting. These two bounds jointly give an exact characterization of the convergence rate and imply, for the first time, that over-parameterization can exponentially slow down the convergence rate. To prove the global convergence, we need to tackle the interactions among student neurons in the gradient descent dynamics, which are not present in the exact-parameterization case. We use a three-phase structure to analyze GD's dynamics. Along the way, we prove gradient descent automatically balances student neurons, and use this property to deal with the non-smoothness of the objective function. To prove the convergence rate lower bound, we construct a novel potential function that characterizes the pairwise distances between the student neurons (which cannot be done in the exact-parameterization case). We show this potential function converges slowly, which implies the slow convergence rate of the loss function.