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

• URL: http://arxiv.org/abs/2105.11558v1
• Date: Mon, 24 May 2021 22:14:26 GMT
• Title: Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems
• Authors: Prateek Jain, Suhas S Kowshik, Dheeraj Nagaraj, Praneeth Netrapalli
• Abstract summary: We consider the setting of vector valued non-linear dynamical systems $X_t+1 = phi(A* X_t) + eta_t$, where $eta_t$ is unbiased noise and $phi : mathbbR to mathbbR$ is a known link function that satisfies certain em expansivity property.
• Score: 45.17023170054112
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the setting of vector valued non-linear dynamical systems $X_{t+1} = \phi(A^* X_t) + \eta_t$, where $\eta_t$ is unbiased noise and $\phi : \mathbb{R} \to \mathbb{R}$ is a known link function that satisfies certain {\em expansivity property}. The goal is to learn $A^*$ 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 $\phi$ 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-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.

Related papers

• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  We study the sample complexity of online reinforcement learning for nonlinear dynamical systems with continuous state and action spaces. Our algorithms are likely to be useful in practice, due to their simplicity, the ability to incorporate prior knowledge, and their benign transient behavior.
  arXiv  Detail & Related papers  (2025-01-27T10:01:28Z)
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge [0.704590071265998]
  We study the sample complexity of online Q-learning methods when some prior knowledge about the dynamics is available or can be learned efficiently. We present an optimistic Q-learning algorithm that achieves $tildemathcalO(textPoly(H)sqrtSAT)$ regret under perfect knowledge of $f$.
  arXiv  Detail & Related papers  (2023-12-19T19:53:58Z)
• Sample Efficient Reinforcement Learning in Mixed Systems through Augmented Samples and Its Applications to Queueing Networks [22.20726152012564]
  This paper considers a class of reinforcement learning problems involving systems with two types of states: and pseudo-stochastic. We propose a sample efficient method that accelerates learning by generating augmented data samples.
  arXiv  Detail & Related papers  (2023-05-25T21:29:11Z)
• FeDXL: Provable Federated Learning for Deep X-Risk Optimization [105.17383135458897]
  We tackle a novel federated learning (FL) problem for optimizing a family of X-risks, to which no existing algorithms are applicable. The challenges for designing an FL algorithm for X-risks lie in the non-decomability of the objective over multiple machines and the interdependency between different machines.
  arXiv  Detail & Related papers  (2022-10-26T00:23:36Z)
• Learning Mixtures of Linear Dynamical Systems [94.49754087817931]
  We develop a two-stage meta-algorithm to efficiently recover each ground-truth LDS model up to error $tildeO(sqrtd/T)$. We validate our theoretical studies with numerical experiments, confirming the efficacy of the proposed algorithm.
  arXiv  Detail & Related papers  (2022-01-26T22:26:01Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples. We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
  arXiv  Detail & Related papers  (2020-09-30T19:10:32Z)
• Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
  We introduce algorithms for learning nonlinear dynamical systems of the form $x_t+1=sigma(Thetastarx_t)+varepsilon_t$. We give an algorithm that recovers the weight matrix $Thetastar$ from a single trajectory with optimal sample complexity and linear running time.
  arXiv  Detail & Related papers  (2020-04-30T10:42:48Z)
• Using Deep Learning to Improve Ensemble Smoother: Applications to Subsurface Characterization [2.4373900721120285]
  Ensemble smoother (ES) has been widely used in various research fields. ES$_text(DL)$ is an update scheme for ES in complex data assimilation applications. We show that the DL-based ES method, that is, ES$_text(DL)$, is more general and flexible.
  arXiv  Detail & Related papers  (2020-02-21T02:46:53Z)
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems [34.394552166070746]
  We study gradient based algorithms to learn the system dynamics $theta$ from samples obtained from a single finite trajectory. Unlike existing work, our bounds are noise sensitive which allows for learning ground-truth dynamics with high accuracy and small sample complexity.
  arXiv  Detail & Related papers  (2020-02-20T02:36:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.