---
abstract: 'We introduce algorithms for learning nonlinear dynamical systems of the form $x_{t+1}=\sigma({\Theta^{\star}}{}x_t)+\veps_t$, where ${\Theta^{\star}}$ is a weight matrix, $\sigma$ is a nonlinear link function, and $\veps_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.' 
author:
- |
    [Dylan J. FosterAlexander RakhlinTuhin Sarkar]{}\
    [Massachusetts Institute of Technology]{}\
    `{dylanf,rakhlin,tsarkar}@mit.edu`
bibliography:
- 'refs.bib'
title: Learning nonlinear dynamical systems from a single trajectory
---

Introduction {#sec:intro}
============

Related work {#sec:related_work}
------------

Stability, Lower Isometry, and Recovery {#sec:stability}
=======================================

\[sec:known\_link\]

Algorithms for generalized linear dynamical systems {#sec:learning}
===================================================

Discussion
==========

We have shown that the exponential stability, in conjunction with Lyapunov arguments, offers a simple approach to establishing isometry guarantees for data generated by nonlinear dynamical systems, and we have provided efficient algorithms for learning and parameter recovery in generalized linear systems.  We hope that the analysis techniques introduced here will find use beyond the generalized linear setting, as well as for end-to-end control. 

Going forward, it will be interesting to draw further connections and build stronger bridges between Lyapunov theory and empirical process theory for dependent data.  For example, what properties of data generated by dynamical systems can we use Lyapunov functions to certify, going beyond lower and upper isometry? 

Lastly, we remark on an extension to the non–autonomous setting.  Consider a non–autonomous system of the form $x_{i+1} = \sigma(\Theta
        \cdot x_i + B \cdot u_i) + \veps_i$, where $\{u_i\}_{i=1}^n$ are control inputs.  This setting reduces to the autonomous case via the expression $$\begin{bmatrix}
    x_{i+1}\\
    u_{i+1}
    \end{bmatrix} = \sigma \prn*{\begin{bmatrix}\Theta & B \\
        0 & 0
        \end{bmatrix}   \begin{bmatrix}
        x_{i}\\
        u_{i}
        \end{bmatrix}} +    \begin{bmatrix}
            \veps_{i}\\
            u_{i+1}
        \end{bmatrix},$$ and our techniques can consequently be applied as long as the control inputs have persistent excitation. 

Acknowledgements {#acknowledgements .unnumbered}
----------------

We thank Adam Klivans, Alexandre Megretski, and Karthik Sridharan for helpful discussions.  We acknowledge the support of ONR award \#N00014-20-1-2336 and NSF TRIPODS award \#1740751. 

Basic technical results {#app:basic_technical_results}
=======================

Proofs from  {#app:intro_proofs}
============

Proofs from  {#app:section2_proof}
============

Proofs from  {#proofs-from}
============

For the remainder of the appendix we make use of the filtration $$\cG_i \ldef{} \sigma(\veps_0,x_1,\veps_1,\ldots,x_{i-1},\veps_{i-1},x_i).\label{eq:filtration}$$

Proof of  {#app:known_link}
---------

 {#app:learn_relu}
