# Can SGD Learn Recurrent Neural Networks with Provable Generalization?

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2019.

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

- [Liquid Structural State-Space Models](https://mlsanity.com/paper/2209.12951/) (2022)
- [Physics of Language Models: Part 4.1, Architecture Design and the Magic of Canon Layers](https://mlsanity.com/paper/2512.17351/) (2025)
- [SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs](https://mlsanity.com/paper/2107.05074/) (2021)
- [LoR-VP: Low-Rank Visual Prompting for Efficient Vision Model Adaptation](https://mlsanity.com/paper/2502.00896/) (2025)
- [The Discovery of Dynamics via Linear Multistep Methods and Deep Learning: Error Estimation](https://mlsanity.com/paper/2103.11488/) (2021)
- [From Generalization Analysis to Optimization Designs for State Space Models](https://mlsanity.com/paper/2405.02670/) (2024)
- [Characterization of Generalizability of Spike Timing Dependent Plasticity trained Spiking Neural Networks](https://mlsanity.com/paper/2105.14677/) (2021)
- [Convergence of Gradient Descent for Recurrent Neural Networks: A Nonasymptotic Analysis](https://mlsanity.com/paper/2402.12241/) (2024)
- [On the Provable Generalization of Recurrent Neural Networks](https://mlsanity.com/paper/2109.14142/) (2021)
- [Understanding the Generalization Benefits of Late Learning Rate Decay](https://mlsanity.com/paper/2401.11600/) (2024)
- [On the Expressivity of Selective State-Space Layers: A Multivariate Polynomial Approach](https://mlsanity.com/paper/2502.02209/) (2025)
- [One-pass Stochastic Gradient Descent in Overparametrized Two-layer Neural Networks](https://mlsanity.com/paper/2105.00262/) (2021)
- [Beyond accuracy: generalization properties of bio-plausible temporal credit assignment rules](https://mlsanity.com/paper/2206.00823/) (2022)
- [Learning and Generalization in RNNs](https://mlsanity.com/paper/2106.00047/) (2021)
- [Linear RNNs Provably Learn Linear Dynamic Systems](https://mlsanity.com/paper/2211.10582/) (2022)
- [On the Role of Noise in the Sample Complexity of Learning Recurrent Neural Networks: Exponential Gaps for Long Sequences](https://mlsanity.com/paper/2305.18423/) (2023)
- [packetLSTM: Dynamic LSTM Framework for Streaming Data with Varying Feature Space](https://mlsanity.com/paper/2410.17394/) (2024)

## Abstract (arXiv)

Recurrent Neural Networks (RNNs) are among the most popular models in sequential data analysis. Yet, in the foundational PAC learning language, what concept class can it learn? Moreover, how can the same recurrent unit simultaneously learn functions from different input tokens to different output tokens, without affecting each other? Existing generalization bounds for RNN scale exponentially with the input length, significantly limiting their practical implications. In this paper, we show using the vanilla stochastic gradient descent (SGD), RNN can actually learn some notable concept class efficiently, meaning that both time and sample complexity scale polynomially in the input length (or almost polynomially, depending on the concept). This concept class at least includes functions where each output token is generated from inputs of earlier tokens using a smooth two-layer neural network.