Linear Systems can be Hard to Learn
Linear Systems can be Hard to Learn
复制标题
线性系统可能很难学
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
George Pappas
中科院分区：
文献类型：
--
作者：
Anastasios Tsiamis;George Pappas
在本文中，我们调查时，系统识别统计上容易或困难，在有限样本制度。统计上容易学习的线性系统类具有与系统维数成多项式的样本复杂度。在有限样本制度福尔斯的大多数先前的研究属于这一类，集中在系统，直接激发的过程噪声。统计学上难以学习的线性系统类具有最坏情况下的样本复杂度，该复杂度至少与系统维度成指数关系，无论识别算法如何。使用极大极小理论的工具，我们表明，类的线性系统可以很难学习。这样的类别包括例如在状态之间具有弱耦合的欠驱动或欠激励系统。在将一些系统分类为容易或难以学习之后，一个自然的问题出现了，即什么系统属性从根本上影响系统可识别性的硬度。朝着这个方向，我们描述了线性系统的可控性指标如何影响识别的样本复杂性。更具体地说，我们证明了鲁棒可控线性系统的样本复杂性的可控性指数的指数函数的上界。这意味着，识别是容易的线性系统类的可控性指标小，潜在的困难，如果可控性指标是大的。我们的分析是基于最近的统计工具，有限样本分析系统识别以及一个新的下限，涉及可控性指数与最小奇异值的可控性Gramian。
In this paper, we investigate when system identification is statistically easy or hard, in the finite sample regime. Statistically easy to learn linear system classes have sample complexity that is polynomial with the system dimension. Most prior research in the finite sample regime falls in this category, focusing on systems that are directly excited by process noise. Statistically hard to learn linear system classes have worst-case sample complexity that is at least exponential with the system dimension, regardless of the identification algorithm. Using tools from minimax theory, we show that classes of linear systems can be hard to learn. Such classes include, for example, under-actuated or under-excited systems with weak coupling among the states. Having classified some systems as easy or hard to learn, a natural question arises as to what system properties fundamentally affect the hardness of system identifiability. Towards this direction, we characterize how the controllability index of linear systems affects the sample complexity of identification. More specifically, we show that the sample complexity of robustly controllable linear systems is upper bounded by an exponential function of the controllability index. This implies that identification is easy for classes of linear systems with small controllability index and potentially hard if the controllability index is large. Our analysis is based on recent statistical tools for finite sample analysis of system identification as well as a novel lower bound that relates controllability index with the least singular value of the controllability Gramian.
DOI：
10.1109/cdc42340.2020.9304468
发表时间：
2019-09
期刊：
2020 59th IEEE Conference on Decision and Control (CDC)
影响因子：
--
作者：
Bruce Lee;Andrew G. Lamperski
通讯作者：
Bruce Lee;Andrew G. Lamperski
SLIP：利用长期记忆学习在未知动态系统中进行预测
DOI：
--
发表时间：
2020
期刊：
Canada
影响因子：
--
作者：
Rashidiejad, Paria;Jiao, Jiantao;Russell, Stuart
通讯作者：
Russell, Stuart