Title: Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification,
Abstract: 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 more unstable linear
systems are 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.