mlsanityData to 14 Oct 2026

Gradient Descent Finds Over-Parameterized Neural Networks with Sharp Generalization for Nonparametric Regression

arXiv 2411.02904 ↗First posted 5 Nov 2024stat.ML cs.IT cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

We study nonparametric regression by an over-parameterized two-layer neural network trained by gradient descent (GD) in this paper. We show that, if the neural network is trained by GD with early stopping, then the trained network renders a sharp rate of the nonparametric regression risk of O(εn2), which is the same rate as that for the classical kernel regression trained by GD with early stopping, where εn is the critical population rate of the Neural Tangent Kernel (NTK) associated with the network and n is the size of the training data. It is remarked that our result does not require distributional assumptions about the covariate as long as the covariate is bounded, in a strong contrast with many existing results which rely on specific distributions of the covariates such as the spherical uniform data distribution or distributions satisfying certain restrictive conditions. The rate O(εn2) is known to be minimax optimal for specific cases, such as the case that the NTK has a polynomial eigenvalue decay rate which happens under certain distributional assumptions on the covariates. Our result formally fills the gap between training a classical kernel regression model and training an over-parameterized but finite-width neural network by GD for nonparametric regression without distributional assumptions on the bounded covariate. We also provide confirmative answers to certain open questions or address particular concerns in the literature of training over-parameterized neural networks by GD with early stopping for nonparametric regression, including the characterization of the stopping time, the lower bound for the network width, and the constant learning rate used in GD.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 28 of its 52 references that are in the map. First posted on arXiv 5 Nov 2024.

Builds on

28 of 52 references.

References · 28

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  3. 2018On Lazy Training in Differentiable Programmingcited by 675
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  5. 2016Error bounds for approximations with deep ReLU networkscited by 574
  6. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  7. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  8. 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
  9. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  10. 2021Deep learning: a statistical viewpointcited by 240
  11. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
  12. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
16 more
  1. 2019Linearized two-layers neural networks in high dimensioncited by 155
  2. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 121
  3. 2013Early stopping and non-parametric regression: An optimal data-dependent stopping rulecited by 89
  4. 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
  5. 2020Deep Equals Shallow for ReLU Networks in Kernel Regimescited by 85
  6. 2018Deep Neural Networks Learn Non-Smooth Functions Effectivelycited by 57
  7. 2024How Feature Learning Can Improve Neural Scaling Lawscited by 56
  8. 2020Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Networkcited by 38
  9. 2020Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regimecited by 35
  10. 2023On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domainscited by 31
  11. 2019On Learning Over-parameterized Neural Networks: A Functional Approximation Perspectivecited by 28
  12. 2023Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimensioncited by 26
  13. 2015Minimax Optimal Rates of Estimation in High Dimensional Additive Models: Universal Phase Transitioncited by 13
  14. 2022Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive?cited by 10
  15. 2021Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stoppingcited by 5
  16. 2024Universal Consistency of Wide and Deep ReLU Neural Networks and Minimax Optimal Convergence Rates for Kolmogorov-Donoho Optimal Function Classescited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attentioncited by 0
  2. 2026Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Ratecited by 0