梯度下降学习线性动态系统

我们证明了随机梯度下降有效收敛到一个未知线性时不变动态系统的最大似然目标的全局优化器，该系统由一系列噪声观测生成。尽管目标函数是非凸的，但在强而自然的假设下，我们提供了多项式运行时间和样本复杂度界限。线性系统的识别已经研究了几十年，但据我们所知，这些是我们所考虑问题的首个多项式保证。