# One-pass Stochastic Gradient Descent in Overparametrized Two-layer Neural Networks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 40 references that are in the map.
- First posted on arXiv 1 May 2021.

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

- [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)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit](https://mlsanity.com/paper/1902.06015/) (2019)
- [An Improved Analysis of Training Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/1906.04688/) (2019)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Enhanced Convolutional Neural Tangent Kernels](https://mlsanity.com/paper/1911.00809/) (2019)
- [On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective](https://mlsanity.com/paper/1905.10826/) (2019)
- [How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?](https://mlsanity.com/paper/1805.07883/) (2018)
- [Can SGD Learn Recurrent Neural Networks with Provable Generalization?](https://mlsanity.com/paper/1902.01028/) (2019)
- [The Generalization Error of the Minimum-norm Solutions for Over-parameterized Neural Networks](https://mlsanity.com/paper/1912.06987/) (2019)
- [A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks](https://mlsanity.com/paper/2002.04026/) (2020)

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

- [On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization](https://mlsanity.com/paper/2211.07675/) (2022)
- [Non-asymptotic Convergence of Stochastic Gradient Descent in Score-based Generative Models](https://mlsanity.com/paper/2607.04775/) (2026)
- [Mutual Information Learned Regressor: an Information-theoretic Viewpoint of Training Regression Systems](https://mlsanity.com/paper/2211.12685/) (2022)

## Abstract (arXiv)

There has been a recent surge of interest in understanding the convergence of gradient descent (GD) and stochastic gradient descent (SGD) in overparameterized neural networks. Most previous works assume that the training data is provided a priori in a batch, while less attention has been paid to the important setting where the training data arrives in a stream. In this paper, we study the streaming data setup and show that with overparamterization and random initialization, the prediction error of two-layer neural networks under one-pass SGD converges in expectation. The convergence rate depends on the eigen-decomposition of the integral operator associated with the so-called neural tangent kernel (NTK). A key step of our analysis is to show a random kernel function converges to the NTK with high probability using the VC dimension and McDiarmid's inequality.