Learning Linear Dynamical Systems via Spectral Filtering

By Elad Hazan, Karan Singh, Cyril Zhang. 2017

122 citations recorded by the source corpus.

We present an efficient and practical algorithm for the online prediction of discrete-time linear dynamical systems with a symmetric transition matrix. We circumvent the non-convex optimization problem using improper learning: carefully overparameterize the class of LDSs by a polylogarithmic factor, in exchange for convexity of the loss functions. From this arises a polynomial-time algorithm with a near-optimal regret guarantee, with an analogous sample complexity bound for agnostic learning. Our algorithm is based on a novel filtering technique, which may be of independent interest: we convolve the time series with the eigenvectors of a certain Hankel matrix.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Statistical Learning Theory, Signal Processing

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 Computational Mechanics

In Management Science and Operations Research

In Statistical Learning Theory

In Signal Processing

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).”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “Followups in this line of research include [27, 28].”
Non-asymptotic Identification of LTI Systems from a Single Trajectory (2018, methodology): “Putting aside the reinforcement learning literature and restricting our attention to linear state-space models, the work in this area can be divided into two categories: (i) directly learning the control inputs to optimize a control objective or analyzing the predictive power of the learned represen”
Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator (2018, background): “(Hazan et al., 2017; Arora et al., 2018) are restricted to systems with symmetric dynamics (symmetric A matrix), while (Hazan et al., 2018) handles a more general setting.”
Kronecker-factored Curvature Approximations for Recurrent Neural Networks (2018, background): “Linear dynamical systems with symmetric transition matrices arise frequently in machine learning and related areas (Huang et al., 2016; Hazan et al., 2017), particularly because of the algorithmic techniques they enable.”
Spectral Filtering for General Linear Dynamical Systems (2018, methodology): “Like Algorithm 1 from [15], the algorithm will “compress” the input time series using a time-domain convolution of the input time series with filters derived from these eigenvectors.”
On the Sample Complexity of the Linear Quadratic Regulator (2017, background): “[27,28] study the problem of prediction in a linear dynamical system via a novel spectral filtering algorithm.”
Long-term Forecasting with TiDE: Time-series Dense Encoder (2023, methodology): “In horizons 96-336 we see a statistically significant drop in performance without the residual connections.”