# Learning and Generalization in RNNs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 50 references that are in the map.
- First posted on arXiv 31 May 2021.

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

- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [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)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Time Series Forecasting With Deep Learning: A Survey](https://mlsanity.com/paper/2004.13408/) (2020)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [Tensor Programs I: Wide Feedforward or Recurrent Neural Networks of Any Architecture are Gaussian Processes](https://mlsanity.com/paper/1910.12478/) (2019)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Echo state networks are universal](https://mlsanity.com/paper/1806.00797/) (2018)
- [O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers](https://mlsanity.com/paper/2006.04862/) (2020)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [The Recurrent Neural Tangent Kernel](https://mlsanity.com/paper/2006.10246/) (2020)
- [Stable Recurrent Models](https://mlsanity.com/paper/1805.10369/) (2018)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [On Generalization Bounds of a Family of Recurrent Neural Networks](https://mlsanity.com/paper/1910.12947/) (2019)
- [Reverse engineering recurrent networks for sentiment classification reveals line attractor dynamics](https://mlsanity.com/paper/1906.10720/) (2019)
- [On the Computational Power of RNNs](https://mlsanity.com/paper/1906.06349/) (2019)
- [Can SGD Learn Recurrent Neural Networks with Provable Generalization?](https://mlsanity.com/paper/1902.01028/) (2019)
- [Stochastic Gradient Descent Learns State Equations with Nonlinear Activations](https://mlsanity.com/paper/1809.03019/) (2018)
- [Implicit Bias of Linear RNNs](https://mlsanity.com/paper/2101.07833/) (2021)
- [Formal Language Theory Meets Modern NLP](https://mlsanity.com/paper/2102.10094/) (2021)

## Abstract (arXiv)

Simple recurrent neural networks (RNNs) and their more advanced cousins LSTMs etc. have been very successful in sequence modeling. Their theoretical understanding, however, is lacking and has not kept pace with the progress for feedforward networks, where a reasonably complete understanding in the special case of highly overparametrized one-hidden-layer networks has emerged. In this paper, we make progress towards remedying this situation by proving that RNNs can learn functions of sequences. In contrast to the previous work that could only deal with functions of sequences that are sums of functions of individual tokens in the sequence, we allow general functions. Conceptually and technically, we introduce new ideas which enable us to extract information from the hidden state of the RNN in our proofs -- addressing a crucial weakness in previous work. We illustrate our results on some regular language recognition problems.