mlsanityData to 7 Oct 2026

Gradient Descent Learns Linear Dynamical Systems

arXiv 1609.05191 ↗First posted 16 Sep 2016cs.LG cs.DS math.OCcited by 78

Not on the map. Why?

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.

Key facts. Cited by 78 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Sep 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 19; 2022: 9; 2023: 11; 2024: 13; 2025: 16; 2026: 9.

78 papers.

Sort:

By area:

  1. 2023Resurrecting Recurrent Neural Networks for Long Sequencescited by 397
  2. 2022Statistical Learning Theory for Control: A Finite Sample Perspectivecited by 52
  3. 2025The Surprising Agreement Between Convex Optimization Theory and Learning-Rate Scheduling for Large Model Trainingcited by 31
  4. 2023StableSSM: Alleviating the Curse of Memory in State-space Models through Stable Reparameterizationcited by 29
  5. 2024Recurrent neural networks: vanishing and exploding gradients are not the end of the storycited by 25
  6. 2023A New Approach to Learning Linear Dynamical Systemscited by 23
  7. 2023Aiming towards the minimizers: fast convergence of SGD for overparametrized problemscited by 22
  8. 2024Geometry of Polynomial Neural Networkscited by 21
  9. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 20
  10. 2021Stochastic Polyak Stepsize with a Moving Targetcited by 19
  11. 2021Streaming Linear System Identification with Reverse Experience Replaycited by 17
  12. 2021Global Convergence and Stability of Stochastic Gradient Descentcited by 17
38 more
  1. 2021Almost Surely Stable Deep Dynamicscited by 16
  2. 2024Tuning Frequency Bias of State Space Modelscited by 16
  3. 2021Task-Optimal Exploration in Linear Dynamical Systemscited by 15
  4. 2023A Brief Survey on the Approximation Theory for Sequence Modellingcited by 15
  5. 2021On Riemannian Stochastic Approximation Schemes with Fixed Step-Sizecited by 12
  6. 2022Finite Sample Identification of Bilinear Dynamical Systemscited by 12
  7. 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
  8. 2024HOPE for a Robust Parameterization of Long-memory State Space Modelscited by 11
  9. 2023Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systemscited by 10
  10. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  11. 2023An Interventional Perspective on Identifiability in Gaussian LTI Systems with Independent Component Analysiscited by 9
  12. 2024Model Stealing for Any Low-Rank Language Modelcited by 9
  13. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
  14. 2024Structure learning of Hamiltonians from real-time evolutioncited by 8
  15. 2022On the Implicit Bias of Gradient Descent for Temporal Extrapolationcited by 7
  16. 2022Learning Low Dimensional State Spaces with Overparameterized Recurrent Neural Netscited by 7
  17. 2024Convergence of Gradient Descent for Recurrent Neural Networks: A Nonasymptotic Analysiscited by 7
  18. 2024Loss Landscape Characterization of Neural Networks without Over-Parametrizationcited by 7
  19. 2021On the Provable Generalization of Recurrent Neural Networkscited by 6
  20. 2021Deep inference of latent dynamics with spatio-temporal super-resolution using selective backpropagation through timecited by 6
  21. 2022Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradientscited by 6
  22. 2024Flash STU: Fast Spectral Transform Unitscited by 6
  23. 2024Learning Linear Dynamics from Bilinear Observationscited by 6
  24. 2026On the Role of Batch Size in Stochastic Conditional Gradient Methodscited by 6
  25. 2021On the Memory Mechanism of Tensor-Power Recurrent Modelscited by 5
  26. 2023Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimizationcited by 5
  27. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5
  28. 2025Expected Variational Inequalitiescited by 5
  29. 2025Universal Learning of Nonlinear Dynamicscited by 5
  30. 2026Universal Dynamics of Warmup Stable Decay: understanding WSD beyond Transformerscited by 5
  31. 2021On the Stability of Nonlinear Receding Horizon Control: A Geometric Perspectivecited by 4
  32. 2021Metric Entropy Limits on Recurrent Neural Network Learning of Linear Dynamical Systemscited by 4
  33. 2021Time varying regression with hidden linear dynamicscited by 4
  34. 2023Non-Asymptotic Pointwise and Worst-Case Bounds for Classical Spectrum Estimatorscited by 4
  35. 2025Finite Sample Identification of Partially Observed Bilinear Dynamical Systemscited by 4
  36. 2025Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEscited by 4
  37. 2021Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectorycited by 3
  38. 2021Robust Learning of Recurrent Neural Networks in Presence of Exogenous Noisecited by 3

50 most cited of 78 All 78 (JSON)