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

arXiv: https://arxiv.org/abs/2105.11558 · HTML: https://mlsanity.com/paper/2105.11558/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 52 references that are in the map.
- First posted on arXiv 24 May 2021.

## Builds on (most cited first, 21 of 21)

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Active Learning for Nonlinear System Identification with Guarantees](https://mlsanity.com/paper/2006.10277/) (2020)
- [Stable Recurrent Models](https://mlsanity.com/paper/1805.10369/) (2018)
- [SGD without Replacement: Sharper Rates for General Smooth Convex Functions](https://mlsanity.com/paper/1903.01463/) (2019)
- [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Learning nonlinear dynamical systems from a single trajectory](https://mlsanity.com/paper/2004.14681/) (2020)
- [Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems](https://mlsanity.com/paper/2002.08538/) (2020)
- [Approximation Schemes for ReLU Regression](https://mlsanity.com/paper/2005.12844/) (2020)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Stochastic Gradient Descent Learns State Equations with Nonlinear Activations](https://mlsanity.com/paper/1809.03019/) (2018)
- [Reverse Experience Replay](https://mlsanity.com/paper/1910.08780/) (2019)
- [Convex Programming for Estimation in Nonlinear Recurrent Models](https://mlsanity.com/paper/1908.09915/) (2019)
- [Inference of High-dimensional Autoregressive Generalized Linear Models](https://mlsanity.com/paper/1605.02693/) (2016)
- [A Robotic Model of Hippocampal Reverse Replay for Reinforcement Learning](https://mlsanity.com/paper/2102.11914/) (2021)
- [Finite-Time Model Inference From A Single Noisy Trajectory](https://mlsanity.com/paper/2010.06616/) (2020)

## Built on by (most cited first, 17 of 17)

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Learning with little mixing](https://mlsanity.com/paper/2206.08269/) (2022)
- [Single Trajectory Nonparametric Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2202.08311/) (2022)
- [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data](https://mlsanity.com/paper/2308.04428/) (2023)
- [Finite Sample Identification of Bilinear Dynamical Systems](https://mlsanity.com/paper/2208.13915/) (2022)
- [Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss](https://mlsanity.com/paper/2402.05928/) (2024)
- [The noise level in linear regression with dependent data](https://mlsanity.com/paper/2305.11165/) (2023)
- [Learning Linear Dynamics from Bilinear Observations](https://mlsanity.com/paper/2409.16499/) (2024)
- [Finite Sample Identification of Partially Observed Bilinear Dynamical Systems](https://mlsanity.com/paper/2501.07652/) (2025)
- [Modeling Latent Non-Linear Dynamical System over Time Series](https://mlsanity.com/paper/2412.08114/) (2024)
- [Distributed Online System Identification for LTI Systems Using Reverse Experience Replay](https://mlsanity.com/paper/2207.01062/) (2022)
- [Rate-Optimal Non-Asymptotics for the Quadratic Prediction Error Method](https://mlsanity.com/paper/2404.07937/) (2024)
- [Regret Analysis of Distributed Online Control for LTI Systems with Adversarial Disturbances](https://mlsanity.com/paper/2310.03206/) (2023)
- [The Complexity of Sequential Prediction in Dynamical Systems](https://mlsanity.com/paper/2402.06614/) (2024)
- [Efficient Continual Finite-Sum Minimization](https://mlsanity.com/paper/2406.04731/) (2024)

## Abstract (arXiv)

We consider the setting of vector valued non-linear dynamical systems Xt+1 = φ(A^* Xt) + ηt, where ηt is unbiased noise and φ : ℝ → ℝ is a known link function that satisfies certain em expansivity property. The goal is to learn A^* from a single trajectory X1,cdots,XT of em dependent or correlated samples. While the problem is well-studied in the linear case, where φ 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 (mathsfSGD-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 Xt) 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.