# Linear RNNs Provably Learn Linear Dynamic Systems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 24 references that are in the map.
- First posted on arXiv 19 Nov 2022.

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

- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [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)
- [Width Provably Matters in Optimization for Deep Linear Neural Networks](https://mlsanity.com/paper/1901.08572/) (2019)
- [Learning Linear Dynamical Systems via Spectral Filtering](https://mlsanity.com/paper/1711.00946/) (2017)
- [Spectral Filtering for General Linear Dynamical Systems](https://mlsanity.com/paper/1802.03981/) (2018)
- [On the Global Convergence of Training Deep Linear ResNets](https://mlsanity.com/paper/2003.01094/) (2020)
- [When is a Convolutional Filter Easy To Learn?](https://mlsanity.com/paper/1709.06129/) (2017)
- [Can SGD Learn Recurrent Neural Networks with Provable Generalization?](https://mlsanity.com/paper/1902.01028/) (2019)
- [A Linear Dynamical System Model for Text](https://mlsanity.com/paper/1502.04081/) (2015)
- [On the Provable Generalization of Recurrent Neural Networks](https://mlsanity.com/paper/2109.14142/) (2021)

## Abstract (arXiv)

We study the learning ability of linear recurrent neural networks with Gradient Descent. We prove the first theoretical guarantee on linear RNNs to learn any stable linear dynamic system using any a large type of loss functions. For an arbitrary stable linear system with a parameter ρC related to the transition matrix C, we show that despite the non-convexity of the parameter optimization loss if the width of the RNN is large enough (and the required width in hidden layers does not rely on the length of the input sequence), a linear RNN can provably learn any stable linear dynamic system with the sample and time complexity polynomial in frac11-ρC. Our results provide the first theoretical guarantee to learn a linear RNN and demonstrate how can the recurrent structure help to learn a dynamic system.