mlsanityData to 14 Oct 2026

Linear Systems can be Hard to Learn

arXiv 2104.01120 ↗First posted 2 Apr 2021eess.SY cs.LG cs.SYcited by 20

Not on the map. Why?

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.

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

23 of 45 references.

References · 23

  1. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  2. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  3. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 159
  4. 2018Learning Without Mixing: Towards A Sharp Analysis of Linear System Identificationcited by 158
  5. 2018A Tour of Reinforcement Learning: The View from Continuous Controlcited by 151
  6. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  7. 2018Near optimal finite time identification of arbitrary linear dynamical systemscited by 89
  8. 2018Non-asymptotic Identification of LTI Systems from a Single Trajectorycited by 78
  9. 2019Finite Sample Analysis of Stochastic System Identificationcited by 67
  10. 2017Finite Time Identification in Unstable Linear Systemscited by 66
  11. 2019Learning Linear Dynamical Systems with Semi-Parametric Least Squarescited by 58
  12. 2020Logarithmic Regret Bound in Partially Observable Linear Dynamical Systemscited by 46
11 more
  1. 2020Black-Box Control for Linear Dynamical Systemscited by 43
  2. 2020Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectoriescited by 38
  3. 2020Active Learning for Identification of Linear Dynamical Systemscited by 33
  4. 2020Online Learning of the Kalman Filter with Logarithmic Regretcited by 21
  5. 2019Sample Complexity Lower Bounds for Linear System Identificationcited by 20
  6. 2019Learning Sparse Dynamical Systems from a Single Sample Trajectorycited by 20
  7. 2019A Tutorial on Concentration Bounds for System Identificationcited by 19
  8. 2018On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in Kalman Filterscited by 16
  9. 2020SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memorycited by 11
  10. 2019Non-asymptotic Closed-Loop System Identification using Autoregressive Processes and Hankel Model Reductioncited by 9
  11. 2019Data-Driven Minimum-Energy Controls for Linear Systemscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 6; 2023: 6; 2024: 3; 2025: 2; 2026: 1.

20 papers.

Sort:

  1. 2022Statistical Learning Theory for Control: A Finite Sample Perspectivecited by 53
  2. 2022Learning with little mixingcited by 33
  3. 2023A Tutorial on the Non-Asymptotic Theory of System Identificationcited by 26
  4. 2022FedSysID: A Federated Approach to Sample-Efficient System Identificationcited by 17
  5. 2022Regret Lower Bounds for Learning Linear Quadratic Gaussian Systemscited by 11
  6. 2022Learning to Control Linear Systems can be Hardcited by 11
  7. 2022How are policy gradient methods affected by the limits of control?cited by 10
  8. 2021Sparsity in Partially Controllable Linear Systemscited by 9
  9. 2023Maximum diffusion reinforcement learningcited by 9
  10. 2024Sample Complexity Bounds for Linear System Identification from a Finite Setcited by 3
  11. 2021Adversarially Robust Stability Certificates can be Sample-Efficientcited by 2
  12. 2024Learning to Stabilize Unknown LTI Systems on a Single Trajectory under Stochastic Noisecited by 2
8 more
  1. 2023Learning and Concentration for High Dimensional Linear Gaussians: an Invariant Subspace Approachcited by 1
  2. 2023From Spectral Theorem to Statistical Independence with Application to System Identificationcited by 1
  3. 2023On the Hardness of Learning to Stabilize Linear Systemscited by 1
  4. 2025High Effort, Low Gain: Fundamental Limits of Active Learning for Linear Dynamical Systemscited by 1
  5. 2023Spectral Statistics of the Sample Covariance Matrix for High Dimensional Linear Gaussianscited by 0
  6. 2024Non-Asymptotic Bounds for Closed-Loop Identification of Sub-Exponentially Growing Nonlinear Stochastic Systemscited by 0
  7. 2025Boosting-Enabled Robust System Identification of Partially Observed LTI Systems Under Heavy-Tailed Noisecited by 0
  8. 2026M-CaStLe: Uncovering Local Causal Structures in Multivariate Space-Time Gridded Datacited by 0