# Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectory

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 42 references that are in the map.
- First posted on arXiv 23 Feb 2021.

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

- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Speech Recognition with Deep Recurrent Neural Networks](https://mlsanity.com/paper/1303.5778/) (2013)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [AntisymmetricRNN: A Dynamical System View on Recurrent Neural Networks](https://mlsanity.com/paper/1902.09689/) (2019)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [Finite Sample Analysis of Stochastic System Identification](https://mlsanity.com/paper/1903.09122/) (2019)
- [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017)
- [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019)
- [Can recurrent neural networks warp time?](https://mlsanity.com/paper/1804.11188/) (2018)
- [Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems](https://mlsanity.com/paper/2002.08538/) (2020)
- [Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories](https://mlsanity.com/paper/2009.00739/) (2020)
- [Active Learning for Identification of Linear Dynamical Systems](https://mlsanity.com/paper/2002.00495/) (2020)
- [Covariance Estimation in High Dimensions via Kronecker Product Expansions](https://mlsanity.com/paper/1302.2686/) (2013)
- [Stochastic Gradient Descent Learns State Equations with Nonlinear Activations](https://mlsanity.com/paper/1809.03019/) (2018)
- [A recurrent neural network without chaos](https://mlsanity.com/paper/1612.06212/) (2016)
- [An Accelerated Randomized Kaczmarz Algorithm](https://mlsanity.com/paper/1310.2887/) (2013)
- [Nonparametric Finite Time LTI System Identification](https://mlsanity.com/paper/1902.01848/) (2019)
- [Convex Programming for Estimation in Nonlinear Recurrent Models](https://mlsanity.com/paper/1908.09915/) (2019)
- [RNN-based Online Learning: An Efficient First-Order Optimization Algorithm with a Convergence Guarantee](https://mlsanity.com/paper/2003.03601/) (2020)

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

- [Large-Scale System Identification Using a Randomized SVD](https://mlsanity.com/paper/2109.02703/) (2021)
- [Learning Linear Models Using Distributed Iterative Hessian Sketching](https://mlsanity.com/paper/2112.04101/) (2021)
- [System Identification via Nuclear Norm Regularization](https://mlsanity.com/paper/2203.16673/) (2022)

## Abstract (arXiv)

This work investigates the problem of estimating the weight matrices of a stable time-invariant linear dynamical system from a single sequence of noisy measurements. We show that if the unknown weight matrices describing the system are in Brunovsky canonical form, we can efficiently estimate the ground truth unknown matrices of the system from a linear system of equations formulated based on the transfer function of the system, using both online and offline stochastic gradient descent (SGD) methods. Specifically, by deriving concrete complexity bounds, we show that SGD converges linearly in expectation to any arbitrary small Frobenius norm distance from the ground truth weights. To the best of our knowledge, ours is the first work to establish linear convergence characteristics for online and offline gradient-based iterative methods for weight matrix estimation in linear dynamical systems from a single trajectory. Extensive numerical tests verify that the performance of the proposed methods is consistent with our theory, and show their superior performance relative to existing state of the art methods.