mlsanityData to 14 Oct 2026

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

arXiv 2306.16361 ↗First posted 28 Jun 2023cs.LGcited by 20

Not on the map. Why?

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.

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

23 of 80 references.

References · 23

  1. 2018On Lazy Training in Differentiable Programmingcited by 675
  2. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  3. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
  4. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  5. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 413
  6. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  7. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  8. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  9. 2016Identity Matters in Deep Learningcited by 109
  10. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  11. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  12. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
11 more
  1. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 63
  2. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  3. 2017An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysiscited by 52
  4. 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
  5. 2016No bad local minima: Data independent training error guarantees for multilayer neural networkscited by 30
  6. 2016Gradient Descent Converges to Minimizerscited by 25
  7. 2023Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuroncited by 25
  8. 2020Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learningcited by 19
  9. 2022Feature selection with gradient descent on two-layer networks in low-rotation regimescited by 14
  10. 2023Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuroncited by 8
  11. 2023Toward L_∞-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fieldscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 4; 2024: 10; 2025: 1; 2026: 5.

20 papers.

Sort:

By area:

  1. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  2. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 46
  3. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 39
  4. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  5. 2024Pretrained transformer efficiently learns low-dimensional target functions in-contextcited by 31
  6. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 15
  7. 2024Mean-field Analysis on Two-layer Neural Networks from a Kernel Perspectivecited by 13
  8. 2023Symmetric Single Index Learningcited by 5
  9. 2024Robust Feature Learning for Multi-Index Models in High Dimensionscited by 5
  10. 2024How Does Gradient Descent Learn Features -- A Local Analysis for Regularized Two-Layer Neural Networkscited by 4
  11. 2024Generalization of Scaled Deep ResNets in the Mean-Field Regimecited by 3
  12. 2026Uniform-in-Time Weak Propagation-of-Chaos in Shallow Neural Networkscited by 3
8 more
  1. 2024Geometric Inductive Biases of Deep Networks: The Role of Data and Architecturecited by 2
  2. 2024Mean-Field Analysis for Learning Subspace-Sparse Polynomials with Gaussian Inputcited by 1
  3. 2024A Unified Kernel for Neural Network Learningcited by 1
  4. 2026The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledgecited by 1
  5. 2025A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyondcited by 0
  6. 2026Neuron Block Dynamics for XOR Classification with Zero-Margincited by 0
  7. 2026How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysiscited by 0
  8. 2026Singular perturbations and hierarchical learning in two-layer neural networkscited by 0