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

Abstract

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