mlsanityData to 14 Oct 2026

Linear RNNs Provably Learn Linear Dynamic Systems

arXiv 2211.10582 ↗First posted 19 Nov 2022cs.LG cs.SY eess.SYcited by 0

Not on the map. Why?

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.

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

17 of 24 references.

References · 17

  1. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  2. 2013Exact solutions to the nonlinear dynamics of learning in deep linear neural networkscited by 763
  3. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  4. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  5. 2016Deep Learning without Poor Local Minimacited by 234
  6. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
  7. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  8. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  9. 2016Gradient Descent Learns Linear Dynamical Systemscited by 79
  10. 2019Width Provably Matters in Optimization for Deep Linear Neural Networkscited by 52
  11. 2017Learning Linear Dynamical Systems via Spectral Filteringcited by 46
  12. 2018Spectral Filtering for General Linear Dynamical Systemscited by 37
5 more
  1. 2020On the Global Convergence of Training Deep Linear ResNetscited by 29
  2. 2017When is a Convolutional Filter Easy To Learn?cited by 21
  3. 2019Can SGD Learn Recurrent Neural Networks with Provable Generalization?cited by 17
  4. 2015A Linear Dynamical System Model for Textcited by 6
  5. 2021On the Provable Generalization of Recurrent Neural Networkscited by 6

Built on by

Not cited yet.