Gradient Descent Learns Linear Dynamical Systems

By Moritz Hardt, Tengyu Ma, B. Recht. 2016

272 citations recorded by the source corpus.

We prove that 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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Recent works in this line of research include (Alaeddini et al., 2018; Arora et al., 2018b; Dean et al., 2017; 2018; Hardt et al., 2018; Hazan et al., 2017; 2018; Marecek & Tchrakian, 2018; Oymak & Ozay, 2018; Simchowitz et al., 2018).”
Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs (2017, background): “Another interesting case is linear dynamical systems, where (Hardt et al., 2016) show that under independence assumptions maximum likelihood is quasi-concave and hence solvable with gradient ascent.”
On the Convergence Rate of Training Recurrent Neural Networks (2018, methodology): “(When there is no activation function, RNN is known as linear dynamical system and Hardt et al. [23] proved the convergence for such linear dynamical systems.)”
Learning One-hidden-layer Neural Networks with Landscape Design (2017, methodology): “This is consistent with observations and theory that over-parameterization is important for training neural networks successfully (Livni et al., 2014; Hardt et al., 2016; Soudry & Carmon, 2016).”
SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data (2017, background): “Stability bounds for SGD in non-convex settings were given in Hardt et al. (2016); Kuzborskij & Lampert (2017).”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “Functions satisfying Assumption 1 are variously called quasi-strongly convex (Necoara et al., 2019), weakly strongly convex (Karimi et al., 2016) or (1, µ)-(strongly) quasar-convex in recent work by Hinder et al. (2019), extending a similar notion previously introduced in (Hardt et al., 2018).”
Algorithmic Regularization in Over-parameterized Matrix Recovery (2017, background): “Over-parameterization apparently improves the training: theoretical and empirical results have suggested that in simpliﬁed settings it can enhance the geometric properties of the optimization landscape [18, 15, 14, 26], and thus allows eﬃcient training.”
Data center cooling using model-predictive control (2018, result): “Non-asymptotic results are limited and often require additional stability assumptions [16, 14]; most recently, Dean et al.”
Linear Model Regression on Time-series Data: Non-asymptotic Error Bounds and Applications (2018, background): “In this direction, non-asymptotic bounds for finite sample complexity were obtained in [2]–[6] for the linear time-invariant systems.”
Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds (2018, methodology): “Earlier work gave combinatorial methods to learn random networks [2], guarantees for learning linear dynamical systems by GD [19] and ReLU networks with more restrictive assumptions [24].”
On the Sample Complexity of the Linear Quadratic Regulator (2017, methodology): “ al. [5] show that when the Amatrix is stable and induced by a sparse graph, then one can recover the support of Afrom a single trajectory using ‘ 1-penalized least squares. Furthermore, Hardt et al. [23] provide the rst polynomial time guarantee for identifying general, but stable linear systems. T”
Non-asymptotic Identification of LTI Systems from a Single Trajectory (2018, unknown): “from limited data [2], [3], [6], [14], [21], [24].”
SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation (2020, background): “We focus on two of the weakest conditions: the quasar (strongly) convex functions (Hinder et al., 2020; Hardt et al., 2018; Guminov and Gasnikov, 2017) and functions satisfying the PL condition (Polyak, 1987; Lojasiewicz, 1963; Karimi et al.”
Learning Linear Dynamical Systems via Spectral Filtering (2017, methodology): “In a recent result of [HMR16], it is shown for the ﬁrst time that for a restricted class of systems, gradient descent (also widely used in practice, perhaps better known in this setting as backpropagation) guarantees polynomial convergence rates and sample complexity in the batch setting.”
Can SGD Learn Recurrent Neural Networks with Provable Generalization? (2019, unknown): “On the optimization side, Hardt, Ma, and Recht [13] show that over-parameterization can help in the training process of a linear dynamic system, which is a special case of RNNs with linear activation functions.”
Spectral Filtering for General Linear Dynamical Systems (2018, background): “Recently [HMR16] show that for a restricted class of systems, gradient descent (also widely used in practice, perhaps better known in this setting as backpropagation) guarantees polynomial convergence rates and sample complexity in the batch setting.”
Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations (2017, methodology): “Over-parameterization — the technique of using more parameters than statistically necessary — apparently improves the training: theoretical and empirical results have suggested that it can enhance the geometric properties of the optimization landscape in simplified settings [21, 17, 16, 31] and thus”
Polynomial Convergence of Gradient Descent for Training One-Hidden-Layer Neural Networks (2018, methodology): “Earlier work gave combinatorial methods to learn random networks [2], guarantees for learning linear dynamical systems by gradient descent [15] and ReLU networks with more restrictive assumptions [19].”