Gradient Descent Learns Linear Dynamical Systems
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets
Optimistic bilevel optimization with manifold lower-level minimizers is differentiable if the optimistic selection is unique, yielding a pseudoinverse hyper-gradient and a convergent HG-MS algorithm whose rate depends...
-
Structure learning of Hamiltonians from real-time evolution
New algorithm learns unknown local Hamiltonians from real-time evolution with total time O(log n / ε), without knowing terms, for bounded-norm interactions.
-
Introduction to Online Control
An introduction to online nonstochastic control that applies online convex optimization and convex relaxations to achieve low regret against the best hindsight policy in adversarial settings for classical control problems.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.