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

Abstract

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.

References in corpus (5)

• Gradient Descent Learns Linear Dynamical Systems
• On the Sample Complexity of the Linear Quadratic Regulator
• Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification
• Spectral Filtering for General Linear Dynamical Systems
• Finite Time Identification in Unstable Linear Systems

Cited by in corpus (24)

• Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees
• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• Efficient Learning of a Linear Dynamical System with Stability Guarantees
• Combining Model-Based and Model-Free Methods for Nonlinear Control: A Provably Convergent Policy Gradient Approach
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• The Nonstochastic Control Problem
• Natural Actor-Critic Converges Globally for Hierarchical Linear Quadratic Regulator
• No-Regret Prediction in Marginally Stable Systems
• Sample Complexity of Kalman Filtering for Unknown Systems
• Fairness in Forecasting of Observations of Linear Dynamical Systems
• Non-Stochastic Control with Bandit Feedback
• PAC-Bayes Generalisation Bounds for Dynamical Systems Including Stable RNNs
• Robust guarantees for learning an autoregressive filter
• Task-Optimal Exploration in Linear Dynamical Systems
• Global Convergence Using Policy Gradient Methods for Model-free Markovian Jump Linear Quadratic Control
• Streaming Linear System Identification with Reverse Experience Replay
• Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples
• System Identification via Meta-Learning in Linear Time-Varying Environments
• Learning from Censored and Dependent Data: The case of Linear Dynamics
• Closed-loop Parameter Identification of Linear Dynamical Systems through the Lens of Feedback Channel Coding Theory
• Linear Dynamics: Clustering without identification
• Using Time-Series Privileged Information for Provably Efficient Learning of Prediction Models