# Finite-time Identification of Stable Linear Systems: Optimality of the Least-Squares Estimator

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2020.

## Built on by (most cited first, 26 of 26)

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Learning with little mixing](https://mlsanity.com/paper/2206.08269/) (2022)
- [Single Trajectory Nonparametric Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2202.08311/) (2022)
- [Multi-Task Imitation Learning for Linear Dynamical Systems](https://mlsanity.com/paper/2212.00186/) (2022)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [FedSysID: A Federated Approach to Sample-Efficient System Identification](https://mlsanity.com/paper/2211.14393/) (2022)
- [Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data](https://mlsanity.com/paper/2308.04428/) (2023)
- [Finite Sample Identification of Bilinear Dynamical Systems](https://mlsanity.com/paper/2208.13915/) (2022)
- [Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems](https://mlsanity.com/paper/2201.01680/) (2022)
- [Nonasymptotic Regret Analysis of Adaptive Linear Quadratic Control with Model Misspecification](https://mlsanity.com/paper/2401.00073/) (2023)
- [Learning Linear Dynamics from Bilinear Observations](https://mlsanity.com/paper/2409.16499/) (2024)
- [Learning linear dynamical systems under convex constraints](https://mlsanity.com/paper/2303.15121/) (2023)
- [Finite Sample Identification of Partially Observed Bilinear Dynamical Systems](https://mlsanity.com/paper/2501.07652/) (2025)
- [Finite-sample analysis of identification of switched linear systems with arbitrary or restricted switching](https://mlsanity.com/paper/2203.09862/) (2022)
- [Distributed Online System Identification for LTI Systems Using Reverse Experience Replay](https://mlsanity.com/paper/2207.01062/) (2022)
- [FLEX: an Adaptive Exploration Algorithm for Nonlinear Systems](https://mlsanity.com/paper/2304.13426/) (2023)
- [Exact Recovery for System Identification with More Corrupt Data than Clean Data](https://mlsanity.com/paper/2305.10506/) (2023)
- [Online greedy identification of linear dynamical systems](https://mlsanity.com/paper/2204.06375/) (2022)
- [SAMoSSA: Multivariate Singular Spectrum Analysis with Stochastic Autoregressive Noise](https://mlsanity.com/paper/2305.16491/) (2023)
- [Federated Nonlinear System Identification](https://mlsanity.com/paper/2508.15025/) (2025)
- [Joint Learning of Linear Dynamical Systems under Smoothness Constraints](https://mlsanity.com/paper/2406.01094/) (2024)
- [Symmetric Linear Dynamical Systems are Learnable from Few Observations](https://mlsanity.com/paper/2512.05337/) (2025)
- [Optimal Centered Active Excitation in Linear System Identification](https://mlsanity.com/paper/2604.05518/) (2026)
- [CLT-Optimal Parameter Error Bounds for Linear System Identification](https://mlsanity.com/paper/2604.21270/) (2026)
- [A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems](https://mlsanity.com/paper/2607.02050/) (2026)
- [Learning Fractional-Order Dynamics from a Single Trajectory](https://mlsanity.com/paper/2609.18127/) (2026)

## Abstract (arXiv)

We present a new finite-time analysis of the estimation error of the Ordinary Least Squares (OLS) estimator for stable linear time-invariant systems. We characterize the number of observed samples (the length of the observed trajectory) sufficient for the OLS estimator to be (varepsilon,δ)-PAC, i.e., to yield an estimation error less than varepsilon with probability at least 1-δ. We show that this number matches existing sample complexity lower bounds [1,2] up to universal multiplicative factors (independent of (varepsilon,δ) and of the system). This paper hence establishes the optimality of the OLS estimator for stable systems, a result conjectured in [1]. Our analysis of the performance of the OLS estimator is simpler, sharper, and easier to interpret than existing analyses. It relies on new concentration results for the covariates matrix.