# Linear Systems can be Hard to Learn arXiv: https://arxiv.org/abs/2104.01120 ยท HTML: https://mlsanity.com/paper/2104.01120/ ## Key facts - Cited by 20 papers in the map (data through 14 Oct 2026). - Builds on 23 of its 45 references that are in the map. - First posted on arXiv 2 Apr 2021. ## Builds on (most cited first, 23 of 23) - [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016) - [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017) - [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017) - [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018) - [A Tour of Reinforcement Learning: The View from Continuous Control](https://mlsanity.com/paper/1806.09460/) (2018) - [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019) - [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018) - [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018) - [Finite Sample Analysis of Stochastic System Identification](https://mlsanity.com/paper/1903.09122/) (2019) - [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017) - [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019) - [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020) - [Black-Box Control for Linear Dynamical Systems](https://mlsanity.com/paper/2007.06650/) (2020) - [Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories](https://mlsanity.com/paper/2009.00739/) (2020) - [Active Learning for Identification of Linear Dynamical Systems](https://mlsanity.com/paper/2002.00495/) (2020) - [Online Learning of the Kalman Filter with Logarithmic Regret](https://mlsanity.com/paper/2002.05141/) (2020) - [Sample Complexity Lower Bounds for Linear System Identification](https://mlsanity.com/paper/1903.10343/) (2019) - [Learning Sparse Dynamical Systems from a Single Sample Trajectory](https://mlsanity.com/paper/1904.09396/) (2019) - [A Tutorial on Concentration Bounds for System Identification](https://mlsanity.com/paper/1906.11395/) (2019) - [On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in Kalman Filters](https://mlsanity.com/paper/1809.05870/) (2018) - [SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory](https://mlsanity.com/paper/2010.05899/) (2020) - [Non-asymptotic Closed-Loop System Identification using Autoregressive Processes and Hankel Model Reduction](https://mlsanity.com/paper/1909.02192/) (2019) - [Data-Driven Minimum-Energy Controls for Linear Systems](https://mlsanity.com/paper/1902.02228/) (2019) ## Built on by (most cited first, 20 of 20) - [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) - [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023) - [FedSysID: A Federated Approach to Sample-Efficient System Identification](https://mlsanity.com/paper/2211.14393/) (2022) - [Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems](https://mlsanity.com/paper/2201.01680/) (2022) - [Learning to Control Linear Systems can be Hard](https://mlsanity.com/paper/2205.14035/) (2022) - [How are policy gradient methods affected by the limits of control?](https://mlsanity.com/paper/2206.06863/) (2022) - [Sparsity in Partially Controllable Linear Systems](https://mlsanity.com/paper/2110.06150/) (2021) - [Maximum diffusion reinforcement learning](https://mlsanity.com/paper/2309.15293/) (2023) - [Sample Complexity Bounds for Linear System Identification from a Finite Set](https://mlsanity.com/paper/2409.11141/) (2024) - [Adversarially Robust Stability Certificates can be Sample-Efficient](https://mlsanity.com/paper/2112.10690/) (2021) - [Learning to Stabilize Unknown LTI Systems on a Single Trajectory under Stochastic Noise](https://mlsanity.com/paper/2406.00234/) (2024) - [Learning and Concentration for High Dimensional Linear Gaussians: an Invariant Subspace Approach](https://mlsanity.com/paper/2304.01708/) (2023) - [From Spectral Theorem to Statistical Independence with Application to System Identification](https://mlsanity.com/paper/2310.10523/) (2023) - [On the Hardness of Learning to Stabilize Linear Systems](https://mlsanity.com/paper/2311.11151/) (2023) - [High Effort, Low Gain: Fundamental Limits of Active Learning for Linear Dynamical Systems](https://mlsanity.com/paper/2509.11907/) (2025) - [Spectral Statistics of the Sample Covariance Matrix for High Dimensional Linear Gaussians](https://mlsanity.com/paper/2312.05794/) (2023) - [Non-Asymptotic Bounds for Closed-Loop Identification of Sub-Exponentially Growing Nonlinear Stochastic Systems](https://mlsanity.com/paper/2412.04157/) (2024) - [Boosting-Enabled Robust System Identification of Partially Observed LTI Systems Under Heavy-Tailed Noise](https://mlsanity.com/paper/2504.18444/) (2025) - [M-CaStLe: Uncovering Local Causal Structures in Multivariate Space-Time Gridded Data](https://mlsanity.com/paper/2605.00398/) (2026) ## Abstract (arXiv) 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.