Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
Max Simchowitz Department of Electrical Engineering and Computer Science, UC Berkeley, Berkeley CA. Horia Mania Stephen Tu Michael I. Jordan Department of Statistics, UC Berkeley, Berkeley CA. Benjamin Recht
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.
中文速览
普通最小二乘（OLS）估计线性动力系统参数时，到底需要多少数据才够、估计精度受什么决定，这个问题长期缺乏精确的非渐近分析。本文证明了OLS估计器在从单条轨迹识别线性动力系统参数这一任务上，能够达到近似极小化极大最优（minimax optimal）的统计性能，关键工具是将Mendelson小球方法（small-ball method）推广到相依数据，从而完全绕开了传统的混合时间（mixing-time）论证。研究发现，估计误差的快慢由有限时间可控性Gramian矩阵的最小特征值决定，且更"不稳定"的系统因信噪比更高反而更容易被估计——这与混合时间方法得出的"不稳定系统更难估计"的结论截然相反，也更符合直觉。上下界的推导表明两者仅相差对数因子，从而给出了迄今最紧的样本复杂度刻画，对依赖数据驱动的鲁棒控制设计具有直接的实用价值。
原文 arXiv:1802.08334;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1802.08334v4