Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime

Abstract

We analyze the convergence of the averaged stochastic gradient descent for overparameterized two-layer neural networks for regression problems. It was recently found that a neural tangent kernel (NTK) plays an important role in showing the global convergence of gradient-based methods under the NTK regime, where the learning dynamics for overparameterized neural networks can be almost characterized by that for the associated reproducing kernel Hilbert space (RKHS). However, there is still room for a convergence rate analysis in the NTK regime. In this study, we show that the averaged stochastic gradient descent can achieve the minimax optimal convergence rate, with the global convergence guarantee, by exploiting the complexities of the target function and the RKHS associated with the NTK. Moreover, we show that the target function specified by the NTK of a ReLU network can be learned at the optimal convergence rate through a smooth approximation of a ReLU network under certain conditions.

arXiv comment35 pages

References in corpus (27)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Searching for Activation Functions
• A Convergence Theory for Deep Learning via Over-Parameterization
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• On Exact Computation with an Infinitely Wide Neural Net
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Generalization Properties of Learning with Random Features
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• On the Spectral Bias of Neural Networks
• The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies
• On the Convergence Rate of Training Recurrent Neural Networks
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
• Learning with SGD and Random Features
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Stochastic Particle Gradient Descent for Infinite Ensembles
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Exponential convergence of testing error for stochastic gradient methods
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK

Cited by in corpus (7)

• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network
• Universal scaling laws in the gradient descent training of neural networks
• On the Double Descent of Random Features Models Trained with SGD
• Learning curves for Gaussian process regression with power-law priors and targets
• Painless step size adaptation for SGD
• Neural Optimization Kernel: Towards Robust Deep Learning