Near optimal finite time identification of arbitrary linear dynamical systems

Abstract

We derive finite time error bounds for estimating general linear time-invariant (LTI) systems from a single observed trajectory using the method of least squares. We provide the first analysis of the general case when eigenvalues of the LTI system are arbitrarily distributed in three regimes: stable, marginally stable, and explosive. Our analysis yields sharp upper bounds for each of these cases separately. We observe that although the underlying process behaves quite differently in each of these three regimes, the systematic analysis of a self--normalized martingale difference term helps bound identification error up to logarithmic factors of the lower bound. On the other hand, we demonstrate that the least squares solution may be statistically inconsistent under certain conditions even when the signal-to-noise ratio is high.

v6 did not have all changes for some reason. Revised to show all changes

Cited by in corpus (41)

• Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories
• Control Barriers in Bayesian Learning of System Dynamics
• Certainty Equivalence is Efficient for Linear Quadratic Control
• Naive Exploration is Optimal for Online LQR
• Learning nonlinear dynamical systems from a single trajectory
• Finite-time Analysis of Approximate Policy Iteration for the Linear Quadratic Regulator
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems
• Black-Box Control for Linear Dynamical Systems
• From self-tuning regulators to reinforcement learning and back again
• Efficient Learning of a Linear Dynamical System with Stability Guarantees
• On-line Non-Convex Constrained Optimization
• Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently
• Rebounding Bandits for Modeling Satiation Effects
• Learning the Dynamics of Autonomous Linear Systems From Multiple Trajectories
• Fairness in Forecasting and Learning Linear Dynamical Systems
• Learning-based attacks in Cyber-Physical Systems: Exploration, Detection, and Control Cost trade-offs
• Convex Programming for Estimation in Nonlinear Recurrent Models
• Sample Complexity of Kalman Filtering for Unknown Systems
• No-Regret Prediction in Marginally Stable Systems
• Fairness in Forecasting of Observations of Linear Dynamical Systems
• Non-Stochastic Control with Bandit Feedback
• Learning Stabilizing Controllers for Unstable Linear Quadratic Regulators from a Single Trajectory
• Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems
• Nonstationary Gauss-Markov Processes: Parameter Estimation and Dispersion
• Finite-Time Model Inference From A Single Noisy Trajectory
• Towards a Dimension-Free Understanding of Adaptive Linear Control
• Task-Optimal Exploration in Linear Dynamical Systems
• On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrix
• SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory
• Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples
• On the Sample Complexity of Decentralized Linear Quadratic Regulator with Partially Nested Information Structure
• Geometric Exploration for Online Control
• System Identification via Meta-Learning in Linear Time-Varying Environments
• Non asymptotic estimation lower bounds for LTI state space models with Cramér-Rao and van Trees
• Learning Unstable Dynamical Systems with Time-Weighted Logarithmic Loss
• Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems
• Sample Complexity of the Robust LQG Regulator with Coprime Factors Uncertainty
• Online Learning of Parameterized Uncertain Dynamical Environments with Finite-sample Guarantees
• Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds
• Topological Linear System Identification via Moderate Deviations Theory
• Sparsity in Partially Controllable Linear Systems