Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems

Abstract

We consider the setting of vector valued non-linear dynamical systems $X_{t+1}=\varphi (A^{\ast }{X}_t)+{\eta }_t$, where ${\eta }_t$ is unbiased noise and $\varphi :\mathbb{R}\to \mathbb{R}$ is a known link function that satisfies certain {\em expansivity property}. The goal is to learn $A^{\ast }$ from a single trajectory $X_1,\cdots ,X_T$ of {\em dependent or correlated} samples. While the problem is well-studied in the linear case, where $\varphi$ is identity, with optimal error rates even for non-mixing systems, existing results in the non-linear case hold only for mixing systems. In this work, we improve existing results for learning nonlinear systems in a number of ways: a) we provide the first offline algorithm that can learn non-linear dynamical systems without the mixing assumption, b) we significantly improve upon the sample complexity of existing results for mixing systems, c) in the much harder one-pass, streaming setting we study a SGD with Reverse Experience Replay ($\mathsf{SGD}-\mathsf{RER}$) method, and demonstrate that for mixing systems, it achieves the same sample complexity as our offline algorithm, d) we justify the expansivity assumption by showing that for the popular ReLU link function -- a non-expansive but easy to learn link function with i.i.d. samples -- any method would require exponentially many samples (with respect to dimension of $X_t$) from the dynamical system. We validate our results via. simulations and demonstrate that a naive application of SGD can be highly sub-optimal. Indeed, our work demonstrates that for correlated data, specialized methods designed for the dependency structure in data can significantly outperform standard SGD based methods.

References in corpus (14)

• Loss minimization and parameter estimation with heavy tails
• On the Convergence Rate of Training Recurrent Neural Networks
• Stable Recurrent Models
• Near optimal finite time identification of arbitrary linear dynamical systems
• Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
• Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems
• Active Learning for Nonlinear System Identification with Guarantees
• Inference of High-dimensional Autoregressive Generalized Linear Models
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems
• Approximation Schemes for ReLU Regression
• Convex Programming for Estimation in Nonlinear Recurrent Models
• Finite-Time Model Inference From A Single Noisy Trajectory
• Streaming Linear System Identification with Reverse Experience Replay
• Improved Prediction and Network Estimation Using the Monotone Single Index Multi-variate Autoregressive Model

Cited by in corpus (1)

• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs