Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification


Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, Benjamin Recht ;
Proceedings of the 31st Conference On Learning Theory, PMLR 75:439-473, 2018.


We prove that the ordinary least-squares (OLS) estimator attains nearly minimax optimal performance for the identification of linear dynamical systems from a single observed trajectory. Our upper bound relies on a generalization of Mendelson’s small-ball method to dependent data, eschewing the use of standard mixing-time arguments. Our lower bounds reveal that these upper bounds match up to logarithmic factors. In particular, we capture the correct signal-to-noise behavior of the problem, showing that \emph{more unstable} linear systems are \emph{easier} to estimate. This behavior is qualitatively different from arguments which rely on mixing-time calculations that suggest that unstable systems are more difficult to estimate. We generalize our technique to provide bounds for a more general class of linear response time-series.

Related Material