Gradient Descent Learns Linear Dynamical Systems

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.

updated with more experimental results and references to prior work; published in JMLR 2018

References in corpus (2)

• Sequence to Sequence Learning with Neural Networks
• On the difficulty of training Recurrent Neural Networks

Cited by in corpus (51)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Learning One-hidden-layer Neural Networks with Landscape Design
• On the Convergence Rate of Training Recurrent Neural Networks
• On the Sample Complexity of the Linear Quadratic Regulator
• Stable Recurrent Models
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories
• Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification
• Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• Learning Linear Dynamical Systems with Semi-Parametric Least Squares
• Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
• Spectral Filtering for General Linear Dynamical Systems
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems
• From self-tuning regulators to reinforcement learning and back again
• The Role of Memory in Stochastic Optimization
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Kronecker Recurrent Units
• Natural Actor-Critic Converges Globally for Hierarchical Linear Quadratic Regulator
• Training Deep Networks without Learning Rates Through Coin Betting
• Global Convergence and Stability of Stochastic Gradient Descent
• Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
• No-Regret Prediction in Marginally Stable Systems
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation
• On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysis
• Convex Programming for Estimation in Nonlinear Recurrent Models
• Learning Linear Dynamical Systems via Spectral Filtering
• Uniform Convergence of Gradients for Non-Convex Learning and Optimization
• Improved Learning Rates for Stochastic Optimization
• Nonparametric Finite Time LTI System Identification
• Robust guarantees for learning an autoregressive filter
• Towards a Dimension-Free Understanding of Adaptive Linear Control
• SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory
• Streaming Linear System Identification with Reverse Experience Replay
• A Conservation Law Method in Optimization
• Convergence of Online Adaptive and Recurrent Optimization Algorithms
• A Study of Condition Numbers for First-Order Optimization
• Learning of Linear Dynamical Systems as a Non-Commutative Polynomial Optimization Problem
• Task-Optimal Exploration in Linear Dynamical Systems
• Convergence rates and approximation results for SGD and its continuous-time counterpart
• Improved rates for prediction and identification of partially observed linear dynamical systems
• Adaptive Gradient-type Methods for Convex Optimization Problems with Relative Accuracy and Sharp Minimum
• On the Provable Generalization of Recurrent Neural Networks
• RNN-based Online Learning: An Efficient First-Order Optimization Algorithm with a Convergence Guarantee
• Sample Complexity of the Robust LQG Regulator with Coprime Factors Uncertainty
• Learning and Generalization in RNNs
• Continuous-time Models for Stochastic Optimization Algorithms
• On the Approximation of Toeplitz Operators for Nonparametric ${\mathcal{H}}_{\infty }$-norm Estimation
• Linear Dynamics: Clustering without identification
• Learning in Gated Neural Networks