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

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2020.

## Built on by (most cited first, 30 of 35)

- [A Tale of Tails: Model Collapse as a Change of Scaling Laws](https://mlsanity.com/paper/2402.07043/) (2024)
- [Model Collapse Demystified: The Case of Regression](https://mlsanity.com/paper/2402.07712/) (2024)
- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networks](https://mlsanity.com/paper/2104.03093/) (2021)
- [A Survey on Statistical Theory of Deep Learning: Approximation, Training Dynamics, and Generative Models](https://mlsanity.com/paper/2401.07187/) (2024)
- [The Spectral Bias of Polynomial Neural Networks](https://mlsanity.com/paper/2202.13473/) (2022)
- [A Scaling Law for Synthetic-to-Real Transfer: How Much Is Your Pre-training Effective?](https://mlsanity.com/paper/2108.11018/) (2021)
- [Learning curves for Gaussian process regression with power-law priors and targets](https://mlsanity.com/paper/2110.12231/) (2021)
- [Understanding Square Loss in Training Overparametrized Neural Network Classifiers](https://mlsanity.com/paper/2112.03657/) (2021)
- [Mean-field Analysis on Two-layer Neural Networks from a Kernel Perspective](https://mlsanity.com/paper/2403.14917/) (2024)
- [Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent](https://mlsanity.com/paper/2205.07331/) (2022)
- [How many Neurons do we need? A refined Analysis for Shallow Networks trained with Gradient Descent](https://mlsanity.com/paper/2309.08044/) (2023)
- [Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions](https://mlsanity.com/paper/2202.00992/) (2022)
- [Deep Networks Provably Classify Data on Curves](https://mlsanity.com/paper/2107.14324/) (2021)
- [How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning](https://mlsanity.com/paper/2407.05664/) (2024)
- [On the Double Descent of Random Features Models Trained with SGD](https://mlsanity.com/paper/2110.06910/) (2021)
- [A Gaussian Process View on Observation Noise and Initialization in Wide Neural Networks](https://mlsanity.com/paper/2502.01556/) (2025)
- [Universal scaling laws in the gradient descent training of neural networks](https://mlsanity.com/paper/2105.00507/) (2021)
- [Analysis of the expected L2 error of an over-parametrized deep neural network estimate learned by gradient descent without regularization](https://mlsanity.com/paper/2311.14609/) (2023)
- [Generalization Analysis of Online Stochastic Gradient Descent for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/2407.07670/) (2024)
- [Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification](https://mlsanity.com/paper/2510.02779/) (2025)
- [On the rate of convergence of an over-parametrized Transformer classifier learned by gradient descent](https://mlsanity.com/paper/2312.17007/) (2023)
- [Gradient Descent Finds Over-Parameterized Neural Networks with Sharp Generalization for Nonparametric Regression](https://mlsanity.com/paper/2411.02904/) (2024)
- [Random feature approximation for general spectral methods](https://mlsanity.com/paper/2506.16283/) (2025)
- [Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2601.22409/) (2026)
- [Random Features for Operator-Valued Kernels: Bridging Kernel Methods and Neural Operators](https://mlsanity.com/paper/2603.00971/) (2026)
- [Painless step size adaptation for SGD](https://mlsanity.com/paper/2102.00853/) (2021)
- [Neural Optimization Kernel: Towards Robust Deep Learning](https://mlsanity.com/paper/2106.06097/) (2021)
- [Random feature approximation for general spectral methods](https://mlsanity.com/paper/2308.15434/) (2023)
- [Towards a Statistical Understanding of Neural Networks: Beyond the Neural Tangent Kernel Theories](https://mlsanity.com/paper/2412.18756/) (2024)

## Abstract (arXiv)

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.