Learning Linear Dynamical Systems via Spectral Filtering
Abstract
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.
Cite
Text
Hazan et al. "Learning Linear Dynamical Systems via Spectral Filtering." Neural Information Processing Systems, 2017.Markdown
[Hazan et al. "Learning Linear Dynamical Systems via Spectral Filtering." Neural Information Processing Systems, 2017.](https://mlanthology.org/neurips/2017/hazan2017neurips-learning/)BibTeX
@inproceedings{hazan2017neurips-learning,
title = {{Learning Linear Dynamical Systems via Spectral Filtering}},
author = {Hazan, Elad and Singh, Karan and Zhang, Cyril},
booktitle = {Neural Information Processing Systems},
year = {2017},
pages = {6702-6712},
url = {https://mlanthology.org/neurips/2017/hazan2017neurips-learning/}
}