Learning nonlinear dynamical systems from a single trajectory

Dylan Foster, Tuhin Sarkar, Alexander Rakhlin
Proceedings of the 2nd Conference on Learning for Dynamics and Control, PMLR 120:851-861, 2020.

Abstract

We introduce algorithms for learning nonlinear dynamical systems of theform $x_{t+1}=\sigma(\Theta{}x_t)+\varepsilon_t$, where $\Theta$ is a weightmatrix, $\sigma$ is a nonlinear monotonic link function, and$\varepsilon_t$ is a mean-zero noise process. When the link function is known, wegive an algorithm that recovers the weight matrix $\Theta$ from a single trajectorywith optimal sample complexity and linear running time. The algorithmsucceeds under weaker statistical assumptions than in previous work, and inparticular i) does not require a bound on the spectral norm of the weightmatrix $\Theta$ (rather, it depends on a generalization of thespectral radius) and ii) works when the link function is the ReLU. Our analysis has three keycomponents: i) We show how \emph{sequential Rademacher complexities} can beused to provide generalization guarantees for general dynamicalsystems, ii) we give a general recipe whereby global stability fornonlinear dynamical systems can be used to certify that the state-vector covariance is well-conditioned, and iii) using these tools, we extend well-known algorithms for efficiently learning generalized linear models to the dependent setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v120-foster20a, title = {Learning nonlinear dynamical systems from a single trajectory}, author = {Foster, Dylan and Sarkar, Tuhin and Rakhlin, Alexander}, booktitle = {Proceedings of the 2nd Conference on Learning for Dynamics and Control}, pages = {851--861}, year = {2020}, editor = {Bayen, Alexandre M. and Jadbabaie, Ali and Pappas, George and Parrilo, Pablo A. and Recht, Benjamin and Tomlin, Claire and Zeilinger, Melanie}, volume = {120}, series = {Proceedings of Machine Learning Research}, month = {10--11 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v120/foster20a/foster20a.pdf}, url = {https://proceedings.mlr.press/v120/foster20a.html}, abstract = {We introduce algorithms for learning nonlinear dynamical systems of theform $x_{t+1}=\sigma(\Theta{}x_t)+\varepsilon_t$, where $\Theta$ is a weightmatrix, $\sigma$ is a nonlinear monotonic link function, and$\varepsilon_t$ is a mean-zero noise process. When the link function is known, wegive an algorithm that recovers the weight matrix $\Theta$ from a single trajectorywith optimal sample complexity and linear running time. The algorithmsucceeds under weaker statistical assumptions than in previous work, and inparticular i) does not require a bound on the spectral norm of the weightmatrix $\Theta$ (rather, it depends on a generalization of thespectral radius) and ii) works when the link function is the ReLU. Our analysis has three keycomponents: i) We show how \emph{sequential Rademacher complexities} can beused to provide generalization guarantees for general dynamicalsystems, ii) we give a general recipe whereby global stability fornonlinear dynamical systems can be used to certify that the state-vector covariance is well-conditioned, and iii) using these tools, we extend well-known algorithms for efficiently learning generalized linear models to the dependent setting.} }
Endnote
%0 Conference Paper %T Learning nonlinear dynamical systems from a single trajectory %A Dylan Foster %A Tuhin Sarkar %A Alexander Rakhlin %B Proceedings of the 2nd Conference on Learning for Dynamics and Control %C Proceedings of Machine Learning Research %D 2020 %E Alexandre M. Bayen %E Ali Jadbabaie %E George Pappas %E Pablo A. Parrilo %E Benjamin Recht %E Claire Tomlin %E Melanie Zeilinger %F pmlr-v120-foster20a %I PMLR %P 851--861 %U https://proceedings.mlr.press/v120/foster20a.html %V 120 %X We introduce algorithms for learning nonlinear dynamical systems of theform $x_{t+1}=\sigma(\Theta{}x_t)+\varepsilon_t$, where $\Theta$ is a weightmatrix, $\sigma$ is a nonlinear monotonic link function, and$\varepsilon_t$ is a mean-zero noise process. When the link function is known, wegive an algorithm that recovers the weight matrix $\Theta$ from a single trajectorywith optimal sample complexity and linear running time. The algorithmsucceeds under weaker statistical assumptions than in previous work, and inparticular i) does not require a bound on the spectral norm of the weightmatrix $\Theta$ (rather, it depends on a generalization of thespectral radius) and ii) works when the link function is the ReLU. Our analysis has three keycomponents: i) We show how \emph{sequential Rademacher complexities} can beused to provide generalization guarantees for general dynamicalsystems, ii) we give a general recipe whereby global stability fornonlinear dynamical systems can be used to certify that the state-vector covariance is well-conditioned, and iii) using these tools, we extend well-known algorithms for efficiently learning generalized linear models to the dependent setting.
APA
Foster, D., Sarkar, T. & Rakhlin, A.. (2020). Learning nonlinear dynamical systems from a single trajectory. Proceedings of the 2nd Conference on Learning for Dynamics and Control, in Proceedings of Machine Learning Research 120:851-861 Available from https://proceedings.mlr.press/v120/foster20a.html.

Related Material