Learning nonlinear dynamical systems from a single trajectory

Abstract

We introduce algorithms for learning nonlinear dynamical systems of the form $x_{t+1}=\sigma ({\Theta }^{\star }{x}_t)+{\epsilon }_t$, where ${\Theta }^{\star }$ is a weight matrix, $\sigma$ is a nonlinear link function, and ${\epsilon }_t$ is a mean-zero noise process. We give an algorithm that recovers the weight matrix ${\Theta }^{\star }$ from a single trajectory with optimal sample complexity and linear running time. The algorithm succeeds under weaker statistical assumptions than in previous work, and in particular i) does not require a bound on the spectral norm of the weight matrix ${\Theta }^{\star }$ (rather, it depends on a generalization of the spectral radius) and ii) enjoys guarantees for non-strictly-increasing link functions such as the ReLU. Our analysis has two key components: i) we give a general recipe whereby global stability for nonlinear dynamical systems can be used to certify that the state-vector covariance is well-conditioned, and ii) using these tools, we extend well-known algorithms for efficiently learning generalized linear models to the dependent setting.

To appear at L4DC 2020

References in corpus (8)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Near optimal finite time identification of arbitrary linear dynamical systems
• Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
• Naive Exploration is Optimal for Online LQR
• Learning with Square Loss: Localization through Offset Rademacher Complexity
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems
• Convex Programming for Estimation in Nonlinear Recurrent Models

Cited by in corpus (10)

• Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction
• Active Learning for Nonlinear System Identification with Guarantees
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems
• Safe Adaptive Learning-based Control for Constrained Linear Quadratic Regulators with Regret Guarantees
• Majorizing Measures, Sequential Complexities, and Online Learning
• PAC-Bayes Generalisation Bounds for Dynamical Systems Including Stable RNNs
• Streaming Linear System Identification with Reverse Experience Replay
• Finite-Time Model Inference From A Single Noisy Trajectory
• Exact Asymptotics for Linear Quadratic Adaptive Control
• Modeling Latent Non-Linear Dynamical System over Time Series