mlsanityData to 7 Oct 2026

Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification

arXiv 1802.08334 ↗First posted 22 Feb 2018cs.LG math.OC stat.MLcited by 158

Not on the map. Why?

Abstract (arXiv)

We prove that the ordinary least-squares (OLS) estimator attains nearly minimax optimal performance for the identification of linear dynamical systems from a single observed trajectory. Our upper bound relies on a generalization of Mendelson's small-ball method to dependent data, eschewing the use of standard mixing-time arguments. Our lower bounds reveal that these upper bounds match up to logarithmic factors. In particular, we capture the correct signal-to-noise behavior of the problem, showing that more unstable linear systems are easier to estimate. This behavior is qualitatively different from arguments which rely on mixing-time calculations that suggest that unstable systems are more difficult to estimate. We generalize our technique to provide bounds for a more general class of linear response time-series.

Key facts. Cited by 158 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Feb 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 26; 2022: 29; 2023: 36; 2024: 32; 2025: 15; 2026: 19.

158 papers.

Sort:

By area:

  1. 2023Transformers as Algorithms: Generalization and Stability in In-context Learningcited by 220
  2. 2022Statistical Learning Theory for Control: A Finite Sample Perspectivecited by 52
  3. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  4. 2024From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformerscited by 34
  5. 2022Learning with little mixingcited by 33
  6. 2023Optimistic Active Exploration of Dynamical Systemscited by 32
  7. 2022Single Trajectory Nonparametric Learning of Nonlinear Dynamicscited by 26
  8. 2023A Tutorial on the Non-Asymptotic Theory of System Identificationcited by 26
  9. 2023A New Approach to Learning Linear Dynamical Systemscited by 23
  10. 2022TaSIL: Taylor Series Imitation Learningcited by 21
  11. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 20
  12. 2021Linear Systems can be Hard to Learncited by 20
38 more
  1. 2023Spectral State Space Modelscited by 20
  2. 2021Streaming Linear System Identification with Reverse Experience Replaycited by 17
  3. 2021Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systemscited by 17
  4. 2023Optimal Exploration for Model-Based RL in Nonlinear Systemscited by 17
  5. 2021Joint Learning of Linear Time-Invariant Dynamical Systemscited by 16
  6. 2021Task-Optimal Exploration in Linear Dynamical Systemscited by 15
  7. 2022Learning Mixtures of Linear Dynamical Systemscited by 15
  8. 2022Identifying the Dynamics of a System by Leveraging Data from Similar Systemscited by 15
  9. 2022FedSysID: A Federated Approach to Sample-Efficient System Identificationcited by 15
  10. 2023Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregressioncited by 14
  11. 2021Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Boundscited by 13
  12. 2022Online Weak-form Sparse Identification of Partial Differential Equationscited by 13
  13. 2024On the Performance of Empirical Risk Minimization with Smoothed Datacited by 13
  14. 2022Finite Sample Identification of Bilinear Dynamical Systemscited by 12
  15. 2023Robust Fitted-Q-Evaluation and Iteration under Sequentially Exogenous Unobserved Confounderscited by 12
  16. 2023Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Datacited by 12
  17. 2022Regret Lower Bounds for Learning Linear Quadratic Gaussian Systemscited by 11
  18. 2021Safe Adaptive Learning-based Control for Constrained Linear Quadratic Regulators with Regret Guaranteescited by 10
  19. 2022Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functionscited by 10
  20. 2022Learning to Control Linear Systems can be Hardcited by 10
  21. 2023Learning Personalized Models with Clustered System Identificationcited by 10
  22. 2023Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systemscited by 10
  23. 2024Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Losscited by 10
  24. 2021Learning from Censored and Dependent Data: The case of Linear Dynamicscited by 9
  25. 2023Smoothed Online Learning for Prediction in Piecewise Affine Systemscited by 9
  26. 2023An Interventional Perspective on Identifiability in Gaussian LTI Systems with Independent Component Analysiscited by 9
  27. 2022Learning the Dynamics of Autonomous Linear Systems From Multiple Trajectoriescited by 8
  28. 2023Learning Dynamical Systems by Leveraging Data from Similar Systemscited by 8
  29. 2021On the Sample Complexity of Decentralized Linear Quadratic Regulator with Partially Nested Information Structurecited by 7
  30. 2022Efficient learning of hidden state LTI state space models of unknown ordercited by 7
  31. 2024Generalization bounds for mixing processes via delayed online-to-PAC conversionscited by 7
  32. 2021Regret Analysis of Distributed Online LQR Control for Unknown LTI Systemscited by 6
  33. 2021Using Time-Series Privileged Information for Provably Efficient Learning of Prediction Modelscited by 6
  34. 2021Deep inference of latent dynamics with spatio-temporal super-resolution using selective backpropagation through timecited by 6
  35. 2021Kalman Filtering with Adversarial Corruptionscited by 6
  36. 2023The noise level in linear regression with dependent datacited by 6
  37. 2023Learning the Uncertainty Sets for Control Dynamics via Set Membership: A Non-Asymptotic Analysiscited by 6
  38. 2024Learning Linear Dynamics from Bilinear Observationscited by 6

50 most cited of 158 All 158 (JSON)