研究如何用最少数据精准识别线性系统，发现输入信号设计决定效率上限。
High Effort, Low Gain: Fundamental Limits of Active Learning for Linear Dynamical Systems
- 提出针对有限假设类的持久激励条件，指导最优输入设计。
- 上下界均显示样本复杂度与系统可辨识性参数呈相同依赖关系。
- 设计了可自适应优化输入的主动学习算法，实测有效。
本文研究在有限假设类下识别未知线性动态系统的样本复杂度问题，重点分析激励输入对识别精度的影响。通过建立样本复杂度下界，揭示了输入选择对学习效率的根本制约，并据此提出适用于该场景的持久激励（PE）条件。该条件比无限假设类情形更宽松，支持对不同激励输入的模块化分析。基于此条件，进一步建立了样本复杂度上界，且上下界对关键参数具有相同的依赖结构。最后，利用这些理论洞察设计了一种主动学习算法，可逐轮优化激励输入以逼近当前系统估计，同时提供严格的样本复杂度保证。实验验证了所提方法的有效性。
原文摘要 · Abstract (English)
In this work, we consider the problem of identifying an unknown linear dynamical system given a finite hypothesis class. In particular, we analyze the effect of the excitation input on the sample complexity of identifying the true system with high probability. To this end, we present sample complexity lower bounds that capture the choice of the selected excitation input. The sample complexity lower bound gives rise to a system theoretic condition to determine the potential benefit of experiment design. Informed by the analysis of the sample complexity lower bound, we propose a persistent excitation (PE) condition tailored to the considered setting, which we then use to establish sample complexity upper bounds. Notably, the PE condition is weaker than in the case of an infinite hypothesis class and allows analyzing different excitation inputs modularly. Crucially, the lower and upper bounds share the same dependency on key problem parameters. Finally, we leverage these insights to propose an active learning algorithm that sequentially excites the system optimally with respect to the current estimate, and provide sample complexity guarantees for the presented algorithm. Concluding simulations showcase the effectiveness of the proposed algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。