# Finite Sample Analysis of Stochastic System Identification

arXiv: https://arxiv.org/abs/1903.09122 · HTML: https://mlsanity.com/paper/1903.09122/

## Key facts

- Cited by 67 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2019.

## Built on by (most cited first, 30 of 67)

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Single Trajectory Nonparametric Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2202.08311/) (2022)
- [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Linear Systems can be Hard to Learn](https://mlsanity.com/paper/2104.01120/) (2021)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Task-Optimal Exploration in Linear Dynamical Systems](https://mlsanity.com/paper/2102.05214/) (2021)
- [Finite Sample Identification of Bilinear Dynamical Systems](https://mlsanity.com/paper/2208.13915/) (2022)
- [Learning to Control Linear Systems can be Hard](https://mlsanity.com/paper/2205.14035/) (2022)
- [Probabilities Are Not Enough: Formal Controller Synthesis for Stochastic Dynamical Models with Epistemic Uncertainty](https://mlsanity.com/paper/2210.05989/) (2022)
- [Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2307.06538/) (2023)
- [Learning from Censored and Dependent Data: The case of Linear Dynamics](https://mlsanity.com/paper/2104.05087/) (2021)
- [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023)
- [Learning the Dynamics of Autonomous Linear Systems From Multiple Trajectories](https://mlsanity.com/paper/2203.12794/) (2022)
- [Learning Dynamical Systems by Leveraging Data from Similar Systems](https://mlsanity.com/paper/2302.04344/) (2023)
- [Efficient learning of hidden state LTI state space models of unknown order](https://mlsanity.com/paper/2202.01625/) (2022)
- [Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems](https://mlsanity.com/paper/2105.07310/) (2021)
- [Deep inference of latent dynamics with spatio-temporal super-resolution using selective backpropagation through time](https://mlsanity.com/paper/2111.00070/) (2021)
- [Stochastic Online Optimization for Cyber-Physical and Robotic Systems](https://mlsanity.com/paper/2404.05318/) (2024)
- [Learning Linear Dynamics from Bilinear Observations](https://mlsanity.com/paper/2409.16499/) (2024)
- [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023)
- [Finite Sample Identification of Partially Observed Bilinear Dynamical Systems](https://mlsanity.com/paper/2501.07652/) (2025)
- [Finite-time System Identification and Adaptive Control in Autoregressive Exogenous Systems](https://mlsanity.com/paper/2108.11959/) (2021)
- [Time varying regression with hidden linear dynamics](https://mlsanity.com/paper/2112.14862/) (2021)
- [Fairness in Forecasting of Observations of Linear Dynamical Systems](https://mlsanity.com/paper/2209.05274/) (2022)
- [Non-Asymptotic Pointwise and Worst-Case Bounds for Classical Spectrum Estimators](https://mlsanity.com/paper/2303.11908/) (2023)
- [PAC-Bayesian bounds for learning LTI-ss systems with input from empirical loss](https://mlsanity.com/paper/2303.16816/) (2023)
- [PAC-Bayes Generalisation Bounds for Dynamical Systems Including Stable RNNs](https://mlsanity.com/paper/2312.09793/) (2023)
- [Optimal Transport-Assisted Risk-Sensitive Q-Learning](https://mlsanity.com/paper/2406.11774/) (2024)
- [Outlier-Robust Linear System Identification Under Heavy-tailed Noise](https://mlsanity.com/paper/2501.00421/) (2024)

## Abstract (arXiv)

In this paper, we analyze the finite sample complexity of stochastic system identification using modern tools from machine learning and statistics. An unknown discrete-time linear system evolves over time under Gaussian noise without external inputs. The objective is to recover the system parameters as well as the Kalman filter gain, given a single trajectory of output measurements over a finite horizon of length N. Based on a subspace identification algorithm and a finite number of N output samples, we provide non-asymptotic high-probability upper bounds for the system parameter estimation errors. Our analysis uses recent results from random matrix theory, self-normalized martingales and SVD robustness, in order to show that with high probability the estimation errors decrease with a rate of 1/√N. Our non-asymptotic bounds not only agree with classical asymptotic results, but are also valid even when the system is marginally stable.