# Gradient Descent Learns Linear Dynamical Systems

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

## Key facts

- Cited by 79 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2016.

## Built on by (most cited first, 30 of 79)

- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [The Surprising Agreement Between Convex Optimization Theory and Learning-Rate Scheduling for Large Model Training](https://mlsanity.com/paper/2501.18965/) (2025)
- [StableSSM: Alleviating the Curse of Memory in State-space Models through Stable Reparameterization](https://mlsanity.com/paper/2311.14495/) (2023)
- [Recurrent neural networks: vanishing and exploding gradients are not the end of the story](https://mlsanity.com/paper/2405.21064/) (2024)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Aiming towards the minimizers: fast convergence of SGD for overparametrized problems](https://mlsanity.com/paper/2306.02601/) (2023)
- [On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator](https://mlsanity.com/paper/1901.03674/) (2019)
- [Geometry of Polynomial Neural Networks](https://mlsanity.com/paper/2402.00949/) (2024)
- [Stochastic Polyak Stepsize with a Moving Target](https://mlsanity.com/paper/2106.11851/) (2021)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Global Convergence and Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2110.01663/) (2021)
- [Tuning Frequency Bias of State Space Models](https://mlsanity.com/paper/2410.02035/) (2024)
- [Almost Surely Stable Deep Dynamics](https://mlsanity.com/paper/2103.14722/) (2021)
- [Task-Optimal Exploration in Linear Dynamical Systems](https://mlsanity.com/paper/2102.05214/) (2021)
- [A Brief Survey on the Approximation Theory for Sequence Modelling](https://mlsanity.com/paper/2302.13752/) (2023)
- [On Riemannian Stochastic Approximation Schemes with Fixed Step-Size](https://mlsanity.com/paper/2102.07586/) (2021)
- [Finite Sample Identification of Bilinear Dynamical Systems](https://mlsanity.com/paper/2208.13915/) (2022)
- [HOPE for a Robust Parameterization of Long-memory State Space Models](https://mlsanity.com/paper/2405.13975/) (2024)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2307.06538/) (2023)
- [How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2402.11173/) (2024)
- [An Interventional Perspective on Identifiability in Gaussian LTI Systems with Independent Component Analysis](https://mlsanity.com/paper/2311.18048/) (2023)
- [Structure learning of Hamiltonians from real-time evolution](https://mlsanity.com/paper/2405.00082/) (2024)
- [Model Stealing for Any Low-Rank Language Model](https://mlsanity.com/paper/2411.07536/) (2024)
- [Why Do Local Methods Solve Nonconvex Problems?](https://mlsanity.com/paper/2103.13462/) (2021)
- [Convergence of Gradient Descent for Recurrent Neural Networks: A Nonasymptotic Analysis](https://mlsanity.com/paper/2402.12241/) (2024)
- [Loss Landscape Characterization of Neural Networks without Over-Parametrization](https://mlsanity.com/paper/2410.12455/) (2024)
- [On the Implicit Bias of Gradient Descent for Temporal Extrapolation](https://mlsanity.com/paper/2202.04302/) (2022)
- [Learning Low Dimensional State Spaces with Overparameterized Recurrent Neural Nets](https://mlsanity.com/paper/2210.14064/) (2022)

## Abstract (arXiv)

We prove that stochastic gradient descent efficiently converges to the global optimizer of the maximum likelihood objective of an unknown linear time-invariant dynamical system from a sequence of noisy observations generated by the system. Even though the objective function is non-convex, we provide polynomial running time and sample complexity bounds under strong but natural assumptions. Linear systems identification has been studied for many decades, yet, to the best of our knowledge, these are the first polynomial guarantees for the problem we consider.