Gradient descent learns linear dynamical systems
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5081233 (Why is no real title available?)
- scientific article; zbMATH DE number 1254125 (Why is no real title available?)
- scientific article; zbMATH DE number 3318178 (Why is no real title available?)
- scientific article; zbMATH DE number 3187044 (Why is no real title available?)
- A Learning Theory Approach to System Identification and Stochastic Adaptive Control
- Atomic Norm Denoising With Applications to Line Spectral Estimation
- Finite sample properties of system identification methods
- Inequalities of A. Markoff and S. Bernstein for polynomials and related functions
- Iterative minimization of \(H_2\) control performance criteria
- Linear systems theory.
- Probability in Banach spaces. Isoperimetry and processes
- Robust convergence of the steepest descent method for data-based control
- Some properties of the output error method
- Uniqueness of estimated k-step prediction models of ARMA processes
- Uniqueness of prediction error estimates of multivariable moving average models
Cited in
(30)- Convergence of gradient descent for recurrent neural networks: a nonasymptotic analysis
- A brief survey on the approximation theory for sequence modelling
- Signed-perturbed sums estimation of ARX systems: exact coverage and strong consistency
- scientific article; zbMATH DE number 7307490 (Why is no real title available?)
- First-Order Methods for Nonconvex Quadratic Minimization
- Improved rates for prediction and identification of partially observed linear dynamical systems
- Sequential subspace optimization for quasar-convex optimization problems with inexact gradient
- On the optimization landscape of tensor decompositions
- Convergence properties of gradient descent noise reduction
- scientific article; zbMATH DE number 7625195 (Why is no real title available?)
- scientific article; zbMATH DE number 7733450 (Why is no real title available?)
- Gradient descent with identity initialization efficiently learns positive-definite linear transformations by deep residual networks
- Metric entropy limits on recurrent neural network learning of linear dynamical systems
- Accelerated methods for weakly-quasi-convex optimization problems
- Learning Dynamical Systems with Side Information
- On the sample complexity of the linear quadratic regulator
- Quantum Langevin dynamics for optimization
- Geometry of polynomial neural networks
- Data-dependent analysis of model validation errors for linear system identification
- scientific article; zbMATH DE number 7625185 (Why is no real title available?)
- The projected heavy-ball method for quasar-monotone variational inequalities and quasar-convex optimization
- The theory of online control
- Linear RNNs provably learn linear dynamical systems
- scientific article; zbMATH DE number 1843025 (Why is no real title available?)
- A modular analysis of adaptive (non-)convex optimization: optimism, composite objectives, variance reduction, and variational bounds
- Identification of linear dynamical systems and machine learning
- Maximum likelihood identification of stable linear dynamical systems
- Power-law dynamic arising from machine learning
- scientific article; zbMATH DE number 7370543 (Why is no real title available?)
- Joint learning of linear time-invariant dynamical systems
This page was built for publication: Gradient descent learns linear dynamical systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558171)
