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

By Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, B. Recht. 2018

388 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Control and Systems Engineering, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Control and Systems Engineering

In Statistical Learning Theory

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Recent works in this line of research include (Alaeddini et al., 2018; Arora et al., 2018b; Dean et al., 2017; 2018; Hardt et al., 2018; Hazan et al., 2017; 2018; Marecek & Tchrakian, 2018; Oymak & Ozay, 2018; Simchowitz et al., 2018).”
Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, background): “…Lakshmanan et al., 2015; Hinderer, 2005; Pirotta et al., 2015; 2013), or the linear parametrization of the dynamics, policy, or value function (Abbasi-Yadkori & Szepesvári, 2011; Simchowitz et al., 2018; Dean et al., 2017; Sutton et al., 2012; Tamar et al., 2012), but not much on non-linear models.”
Safely Learning to Control the Constrained Linear Quadratic Regulator (2018, background): “[6] which allows for non-asymptotic guarantees on parameter estimation from a single trajectory of a linear system, Dean et al.”
Non-asymptotic Identification of LTI Systems from a Single Trajectory (2018, result): “from limited data [2], [3], [6], [14], [21], [24].”
Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator (2018, neutral): “Tighter analysis for sample complexity was given in Tu & Recht (2018); Simchowitz et al. (2018).”
Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator (2018, methodology): “To develop the first polynomial-time algorithm that provides high probability guarantees of sub-linear regret, we leverage recent results from the estimation of linear systems [17], robust controller synthesis [14, 19], and coarse-ID control [6].”
Linear Model Regression on Time-series Data: Non-asymptotic Error Bounds and Applications (2018, background): “In this direction, non-asymptotic bounds for finite sample complexity were obtained in [2]–[6] for the linear time-invariant systems.”
Robust Spectral Filtering and Anomaly Detection (2018, methodology): “Several other authors [28, 17, 30] have derived similarly important results at the same time.”