# Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Time

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 80 references that are in the map.
- First posted on arXiv 28 Jun 2023.

## Builds on (most cited first, 23 of 23)

- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (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)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs](https://mlsanity.com/paper/1702.07966/) (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)
- [Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval](https://mlsanity.com/paper/1910.12837/) (2019)
- [No bad local minima: Data independent training error guarantees for multilayer neural networks](https://mlsanity.com/paper/1605.08361/) (2016)
- [Gradient Descent Converges to Minimizers](https://mlsanity.com/paper/1602.04915/) (2016)
- [Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron](https://mlsanity.com/paper/2302.10034/) (2023)
- [Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning](https://mlsanity.com/paper/2001.04413/) (2020)
- [Feature selection with gradient descent on two-layer networks in low-rotation regimes](https://mlsanity.com/paper/2208.02789/) (2022)
- [Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron](https://mlsanity.com/paper/2303.02255/) (2023)
- [Toward L_∞-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields](https://mlsanity.com/paper/2305.00322/) (2023)

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

- [On Learning Gaussian Multi-index Models with Gradient Flow](https://mlsanity.com/paper/2310.19793/) (2023)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023)
- [Gradient-Based Feature Learning under Structured Data](https://mlsanity.com/paper/2309.03843/) (2023)
- [Pretrained transformer efficiently learns low-dimensional target functions in-context](https://mlsanity.com/paper/2411.02544/) (2024)
- [Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics](https://mlsanity.com/paper/2408.07254/) (2024)
- [Mean-field Analysis on Two-layer Neural Networks from a Kernel Perspective](https://mlsanity.com/paper/2403.14917/) (2024)
- [Symmetric Single Index Learning](https://mlsanity.com/paper/2310.02117/) (2023)
- [Robust Feature Learning for Multi-Index Models in High Dimensions](https://mlsanity.com/paper/2410.16449/) (2024)
- [How Does Gradient Descent Learn Features -- A Local Analysis for Regularized Two-Layer Neural Networks](https://mlsanity.com/paper/2406.01766/) (2024)
- [Generalization of Scaled Deep ResNets in the Mean-Field Regime](https://mlsanity.com/paper/2403.09889/) (2024)
- [Uniform-in-Time Weak Propagation-of-Chaos in Shallow Neural Networks](https://mlsanity.com/paper/2605.22010/) (2026)
- [Geometric Inductive Biases of Deep Networks: The Role of Data and Architecture](https://mlsanity.com/paper/2410.12025/) (2024)
- [Mean-Field Analysis for Learning Subspace-Sparse Polynomials with Gaussian Input](https://mlsanity.com/paper/2402.08948/) (2024)
- [A Unified Kernel for Neural Network Learning](https://mlsanity.com/paper/2403.17467/) (2024)
- [The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledge](https://mlsanity.com/paper/2605.12908/) (2026)
- [A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyond](https://mlsanity.com/paper/2510.19382/) (2025)
- [Neuron Block Dynamics for XOR Classification with Zero-Margin](https://mlsanity.com/paper/2602.00172/) (2026)
- [How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysis](https://mlsanity.com/paper/2605.24749/) (2026)
- [Singular perturbations and hierarchical learning in two-layer neural networks](https://mlsanity.com/paper/2607.10869/) (2026)

## Abstract (arXiv)

Despite recent theoretical progress on the non-convex optimization of two-layer neural networks, it is still an open question whether gradient descent on neural networks without unnatural modifications can achieve better sample complexity than kernel methods. This paper provides a clean mean-field analysis of projected gradient flow on polynomial-width two-layer neural networks. Different from prior works, our analysis does not require unnatural modifications of the optimization algorithm. We prove that with sample size n = O(d3.1) where d is the dimension of the inputs, the network trained with projected gradient flow converges in poly(d) time to a non-trivial error that is not achievable by kernel methods using n ll d4 samples, hence demonstrating a clear separation between unmodified gradient descent and NTK. As a corollary, we show that projected gradient descent with a positive learning rate and a polynomial number of iterations converges to low error with the same sample complexity.