# On the Provable Generalization of Recurrent Neural Networks

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 42 references that are in the map.
- First posted on arXiv 29 Sep 2021.

## Builds on (most cited first, 30 of 31)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [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)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [Topology and Geometry of Half-Rectified Network Optimization](https://mlsanity.com/paper/1611.01540/) (2016)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?](https://mlsanity.com/paper/1911.12360/) (2019)
- [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)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks](https://mlsanity.com/paper/1910.01619/) (2019)
- [The Recurrent Neural Tangent Kernel](https://mlsanity.com/paper/2006.10246/) (2020)
- [Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective](https://mlsanity.com/paper/2002.06262/) (2020)
- [Towards Understanding Hierarchical Learning: Benefits of Neural Representations](https://mlsanity.com/paper/2006.13436/) (2020)
- [On Generalization Bounds of a Family of Recurrent Neural Networks](https://mlsanity.com/paper/1910.12947/) (2019)
- [Stabilizing Gradients for Deep Neural Networks via Efficient SVD Parameterization](https://mlsanity.com/paper/1803.09327/) (2018)
- [When is a Convolutional Filter Easy To Learn?](https://mlsanity.com/paper/1709.06129/) (2017)
- [Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK](https://mlsanity.com/paper/2007.04596/) (2020)
- [Can SGD Learn Recurrent Neural Networks with Provable Generalization?](https://mlsanity.com/paper/1902.01028/) (2019)

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

- [Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks](https://mlsanity.com/paper/2204.02892/) (2022)
- [From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency](https://mlsanity.com/paper/2410.05459/) (2024)
- [Designing Universal Causal Deep Learning Models: The Case of Infinite-Dimensional Dynamical Systems from Stochastic Analysis](https://mlsanity.com/paper/2210.13300/) (2022)
- [A Brief Survey on the Approximation Theory for Sequence Modelling](https://mlsanity.com/paper/2302.13752/) (2023)
- [Global Convergence of Over-parameterized Deep Equilibrium Models](https://mlsanity.com/paper/2205.13814/) (2022)
- [Linear RNNs Provably Learn Linear Dynamic Systems](https://mlsanity.com/paper/2211.10582/) (2022)

## Abstract (arXiv)

Recurrent Neural Network (RNN) is a fundamental structure in deep learning. Recently, some works study the training process of over-parameterized neural networks, and show that over-parameterized networks can learn functions in some notable concept classes with a provable generalization error bound. In this paper, we analyze the training and generalization for RNNs with random initialization, and provide the following improvements over recent works: 1) For a RNN with input sequence x=(X1,X2,...,XL), previous works study to learn functions that are summation of f(βTlXl) and require normalized conditions that ||Xl||≤ε with some very small ε depending on the complexity of f. In this paper, using detailed analysis about the neural tangent kernel matrix, we prove a generalization error bound to learn such functions without normalized conditions and show that some notable concept classes are learnable with the numbers of iterations and samples scaling almost-polynomially in the input length L. 2) Moreover, we prove a novel result to learn N-variables functions of input sequence with the form f(βT[Xl1,...,XlN]), which do not belong to the "additive" concept class, i,e., the summation of function f(Xl). And we show that when either N or l0=max(l1,..,lN)-min(l1,..,lN) is small, f(βT[Xl1,...,XlN]) will be learnable with the number iterations and samples scaling almost-polynomially in the input length L.