Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
[edit]
Proceedings of the 31st Conference On Learning Theory, PMLR 75:439473, 2018.
Abstract
We prove that the ordinary leastsquares (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 smallball method to dependent data, eschewing the use of standard mixingtime arguments. Our lower bounds reveal that these upper bounds match up to logarithmic factors. In particular, we capture the correct signaltonoise 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 mixingtime 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 timeseries.
Related Material


