Learning Linear Dynamical Systems with Semi-Parametric Least Squares
Max Simchowitz Department of Electrical Engineering and Computer Sciences, UC Berkeley, Berkeley CA.Denotes equal contribution. Ross Boczar Benjamin Recht
Abstract
We analyze a simple prefiltered variation of the least squares estimator for the problem of estimation with biased, semi-parametric noise, an error model studied more broadly in causal statistics and active learning. We prove an oracle inequality which demonstrates that this procedure provably mitigates the variance introduced by long-term dependencies. We then demonstrate that prefiltered least squares yields, to our knowledge, the first algorithm that provably estimates the parameters of partially-observed linear systems that attains rates which do not not incur a worst-case dependence on the rate at which these dependencies decay. The algorithm is provably consistent even for systems which satisfy the weaker marginal stability condition obeyed by many classical models based on Newtonian mechanics. In this context, our semi-parametric framework yields guarantees for both stochastic and worst-case noise.
中文速览
预测带有偏差的半参数噪声（semi-parametric noise）时，普通最小二乘法会因系统长期依赖关系而产生方差爆炸，对于那些满足"边际稳定"（marginal stability，即谱半径等于1）而非严格稳定条件的线性系统（比如牛顿力学中的振子、积分器），现有方法要么不一致、要么估计速率随稳定性裕量的缩小急剧恶化。本文提出一种"预滤波最小二乘"（Prefiltered Least Squares，PF-LS）方法：先用历史输出学习一个线性滤波器来粗略预测当前观测，再对残差做最小二乘回归，从而压制长期依赖带来的噪声幅度。理论上，作者证明了一个oracle不等式，表明PF-LS的估计误差不再受稳定性衰减速率的最坏情形支配，并给出了首个在边际稳定部分可观线性系统上可证一致收敛、且收敛速率与稳定性裂口无关的算法，同时对随机噪声和对抗噪声均有保证。这一结果意味着工程中大量基于牛顿力学建模的实际系统，终于有了理论上可靠且不过度悲观的辨识方法。
原文 arXiv:1902.00768;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1902.00768v1