# Generalization Analysis of Online Stochastic Gradient Descent for Overparameterized Two-Layer Neural Networks

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 38 references that are in the map.
- First posted on arXiv 10 Jul 2024.

## Builds on (most cited first, 20 of 20)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Universality of Deep Convolutional Neural Networks](https://mlsanity.com/paper/1805.10769/) (2018)
- [Convergence Analysis of Two-layer Neural Networks with ReLU Activation](https://mlsanity.com/paper/1705.09886/) (2017)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data](https://mlsanity.com/paper/1710.10174/) (2017)
- [A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networks](https://mlsanity.com/paper/2310.07891/) (2023)
- [Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime](https://mlsanity.com/paper/2006.12297/) (2020)
- [Learning with SGD and Random Features](https://mlsanity.com/paper/1807.06343/) (2018)
- [On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective](https://mlsanity.com/paper/1905.10826/) (2019)
- [Universal Consistency of Deep Convolutional Neural Networks](https://mlsanity.com/paper/2106.12498/) (2021)
- [Capacity dependent analysis for functional online learning algorithms](https://mlsanity.com/paper/2209.12198/) (2022)
- [How many Neurons do we need? A refined Analysis for Shallow Networks trained with Gradient Descent](https://mlsanity.com/paper/2309.08044/) (2023)
- [Fast and Strong Convergence of Online Learning Algorithms](https://mlsanity.com/paper/1710.03600/) (2017)
- [Optimality of Robust Online Learning](https://mlsanity.com/paper/2304.10060/) (2023)
- [Convergence of Unregularized Online Learning Algorithms](https://mlsanity.com/paper/1708.02939/) (2017)

## Built on by (most cited first, 4 of 4)

- [Spectral Algorithms in Misspecified Regression: Convergence under Covariate Shift](https://mlsanity.com/paper/2509.05106/) (2025)
- [Convergence of Stochastic Gradient Methods for Wide Two-Layer Physics-Informed Neural Networks for the Poisson Equation](https://mlsanity.com/paper/2508.21571/) (2025)
- [Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks](https://mlsanity.com/paper/2606.06764/) (2026)
- [Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descent](https://mlsanity.com/paper/2606.06772/) (2026)

## Abstract (arXiv)

We investigate the generalization performance of online stochastic gradient descent (SGD) for overparameterized two-layer neural networks under the Neural Tangent Kernel (NTK) regime. Leveraging the NTK approximation together with the convergence theory of stochastic approximation in reproducing kernel Hilbert spaces (RKHSs), we develop a unified framework that connects the optimization dynamics of neural networks with kernel-based statistical learning. This framework enables us to derive sharp convergence rates for the generalization error of the last iterate of online SGD. The obtained rates coincide with the optimal statistical rates for kernel methods under appropriate source assumptions on target function. In contrast to existing NTK analyses, which primarily establish optimization convergence or analyze averaged SGD, our results directly characterize the statistical behavior of the practically implemented last-iterate online SGD algorithm for streaming data. Moreover, our analysis substantially relaxes the required degree of overparameterization by reducing the network-width requirement from exponential to polynomial dependence on the sample size or the number of optimization iterations. These results provide a unified theoretical perspective on stochastic optimization, kernel methods, and statistical learning for overparameterized neural networks, while significantly narrowing the gap between existing theory and practical deep learning.