Linear RNNs Provably Learn Linear Dynamical Systems

In this paper, we investigate the learning abilities of linear recurrent neural networks (RNNs) trained using Gradient Descent. We present a theoretical guarantee demonstrating that these linear RNNs can effectively learn any stable linear dynamical system with polynomial complexity. Importantly, our derived generalization error bound is independent of the episode length. For any stable linear system with a transition matrix C characterized by a parameter rho C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rho _C$$\end{document} related to the spectral radius, we prove that despite the non-convexity of the parameter optimization loss, a linear RNN can learn the system with polynomial sample and time complexity in 11-rho C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{1}{1-\rho _C}$$\end{document}, provided that the RNN has sufficient width. Notably, the required width of the hidden layers does not depend on the length of the input sequence. This work provides the first rigorous theoretical foundation for learning linear RNNs. Our findings suggest that linear RNNs are capable of efficiently learning complex dynamical systems, paving the way for further research into the learning capabilities of more general RNN architectures.