Universal Learning of Nonlinear Dynamics

We study the fundamental problem of one-step prediction of a marginally stable unknown nonlinear dynamical system. We describe an algorithm for this problem, based on the technique of spectral filtering, which learns a mapping from past observations to the next based on a spectral representation of the system. Using techniques from online convex optimization, we prove vanishing prediction error for any nonexpansive nonlinear dynamical system with finitely many marginally stable modes, with rates governed by a novel quantitative control-theoretic notion of learnability. The main technical component of our method is a new spectral filtering algorithm for linear dynamical systems, which incorporates past observations and applies to general noisy and marginally stable systems. This generalizes the original spectral filtering algorithm to both asymmetric dynamics as well as incorporating noise correction, and is of independent interest.

Many real-world systems, such as weather, robots, physical simulations, and biological processes, evolve according to complicated hidden dynamics. We often do not need to recover the true hidden state or the exact equations of motion; we only need to predict what will be observed next. This paper develops a provable method for doing exactly that. The proposed algorithm, Observation Spectral Filtering, learns directly from past observations and avoids explicitly identifying the underlying nonlinear system. Instead, it competes with the best high-dimensional linear “observer” that could explain the observed sequence. This turns a difficult nonlinear system-identification problem into a more tractable online prediction problem. The main guarantee shows that certain bounded, nonexpansive nonlinear dynamical systems can be predicted with vanishing error, with rates governed by a control-theoretic quantity $Q_\star$ measuring how hard the system is to observe through a well-conditioned linear approximation. When $Q_\star$ is small, the algorithm learns efficiently without dependence on the hidden dimension of the approximating linear system. Experiments on nonlinear systems such as the Lorenz system/double pendulum support the theory, showing that spectral filtering over observations or nonlinear lifted features can outperform direct linear-system learning and classical eDMD-style baselines. Overall, the paper argues that prediction can be much easier than identifying the true dynamics, and that tools from control theory can guide the design of efficient learning algorithms for nonlinear time series.