Gradient Descent Finds Over-Parameterized Neural Networks with Sharp Generalization for Nonparametric Regression: A Distribution-Free Analysis

• URL: http://arxiv.org/abs/2411.02904v2
• Date: Wed, 06 Nov 2024 10:45:04 GMT
• Title: Gradient Descent Finds Over-Parameterized Neural Networks with Sharp Generalization for Nonparametric Regression: A Distribution-Free Analysis
• Authors: Yingzhen Yang, Ping Li,
• Abstract summary: 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 $cO(eps_n2)$. It is remarked that our result does not require distributional assumptions on the training data.
• Score: 19.988762532185884
• License:
• Abstract: 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 $\cO(\eps_n^2)$, which is the same rate as that for the classical kernel regression trained by GD with early stopping, where $\eps_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 on the training data, in a strong contrast with many existing results which rely on specific distributions such as the spherical uniform data distribution or distributions satisfying certain restrictive conditions. The rate $\cO(\eps_n^2)$ 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. 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. 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.

Related papers

• Preconditioned Gradient Descent Finds Over-Parameterized Neural Networks with Sharp Generalization for Nonparametric Regression [8.130817534654089]
  We consider nonparametric regression by a two-layer neural network trained by gradient descent (GD) or its variant in this paper. We show that, if the neural network is trained with a novel Preconditioned Gradient Descent (PGD) with early stopping and the target function has spectral bias widely studied in the deep learning literature, the trained network renders a particularly sharp generalization bound with a minimax optimal rate of $cO(1/n4alpha/(4alpha+1)$.
  arXiv  Detail & Related papers  (2024-07-16T03:38:34Z)
• Implicit Bias of Gradient Descent for Two-layer ReLU and Leaky ReLU Networks on Nearly-orthogonal Data [66.1211659120882]
  The implicit bias towards solutions with favorable properties is believed to be a key reason why neural networks trained by gradient-based optimization can generalize well. While the implicit bias of gradient flow has been widely studied for homogeneous neural networks (including ReLU and leaky ReLU networks), the implicit bias of gradient descent is currently only understood for smooth neural networks.
  arXiv  Detail & Related papers  (2023-10-29T08:47:48Z)
• How many Neurons do we need? A refined Analysis for Shallow Networks trained with Gradient Descent [0.0]
  We analyze the generalization properties of two-layer neural networks in the neural tangent kernel regime. We derive fast rates of convergence that are known to be minimax optimal in the framework of non-parametric regression.
  arXiv  Detail & Related papers  (2023-09-14T22:10:28Z)
• Gradient Descent in Neural Networks as Sequential Learning in RKBS [63.011641517977644]
  We construct an exact power-series representation of the neural network in a finite neighborhood of the initial weights. We prove that, regardless of width, the training sequence produced by gradient descent can be exactly replicated by regularized sequential learning.
  arXiv  Detail & Related papers  (2023-02-01T03:18:07Z)
• Learning Low Dimensional State Spaces with Overparameterized Recurrent Neural Nets [57.06026574261203]
  We provide theoretical evidence for learning low-dimensional state spaces, which can also model long-term memory. Experiments corroborate our theory, demonstrating extrapolation via learning low-dimensional state spaces with both linear and non-linear RNNs.
  arXiv  Detail & Related papers  (2022-10-25T14:45:15Z)
• Mean-field Analysis of Piecewise Linear Solutions for Wide ReLU Networks [83.58049517083138]
  We consider a two-layer ReLU network trained via gradient descent. We show that SGD is biased towards a simple solution. We also provide empirical evidence that knots at locations distinct from the data points might occur.
  arXiv  Detail & Related papers  (2021-11-03T15:14:20Z)
• A global convergence theory for deep ReLU implicit networks via over-parameterization [26.19122384935622]
  Implicit deep learning has received increasing attention recently. This paper analyzes the gradient flow of Rectified Linear Unit (ReLU) activated implicit neural networks.
  arXiv  Detail & Related papers  (2021-10-11T23:22:50Z)
• Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping [11.24426822697648]
  We show that trained neural networks are smooth with respect to their inputs when trained by Gradient Descent (GD) In the noise-free case the proof does not rely on any kernelization and can be regarded as a finite-width result.
  arXiv  Detail & Related papers  (2021-07-12T11:56:53Z)
• Differentially private training of neural networks with Langevin dynamics forcalibrated predictive uncertainty [58.730520380312676]
  We show that differentially private gradient descent (DP-SGD) can yield poorly calibrated, overconfident deep learning models. This represents a serious issue for safety-critical applications, e.g. in medical diagnosis.
  arXiv  Detail & Related papers  (2021-07-09T08:14:45Z)
• Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network [20.132432350255087]
  Overparametrized neural networks trained by tangent descent (GD) can provably overfit any training data. This paper studies how well overparametrized neural networks can recover the true target function in the presence of random noises.
  arXiv  Detail & Related papers  (2020-07-06T01:02:23Z)
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks [87.23360438947114]
  We show that noisy gradient descent with weight decay can still exhibit a " Kernel-like" behavior. This implies that the training loss converges linearly up to a certain accuracy. We also establish a novel generalization error bound for two-layer neural networks trained by noisy gradient descent with weight decay.
  arXiv  Detail & Related papers  (2020-02-10T18:56:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.