# The Complexity of Sequential Prediction in Dynamical Systems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 69 references that are in the map.
- First posted on arXiv 9 Feb 2024.

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

- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control](https://mlsanity.com/paper/1611.03537/) (2016)
- [Towards better decoding and language model integration in sequence to sequence models](https://mlsanity.com/paper/1612.02695/) (2016)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Online Linear Quadratic Control](https://mlsanity.com/paper/1806.07104/) (2018)
- [Learning Linear Dynamical Systems via Spectral Filtering](https://mlsanity.com/paper/1711.00946/) (2017)
- [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020)
- [Learning nonlinear dynamical systems from a single trajectory](https://mlsanity.com/paper/2004.14681/) (2020)
- [Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis](https://mlsanity.com/paper/1906.11378/) (2019)
- [Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems](https://mlsanity.com/paper/2002.08538/) (2020)
- [Spectral Filtering for General Linear Dynamical Systems](https://mlsanity.com/paper/1802.03981/) (2018)
- [Online Learning for Time Series Prediction](https://mlsanity.com/paper/1302.6927/) (2013)
- [Learning Graph Cellular Automata](https://mlsanity.com/paper/2110.14237/) (2021)
- [Online Learning of the Kalman Filter with Logarithmic Regret](https://mlsanity.com/paper/2002.05141/) (2020)
- [Multiclass Online Learning and Uniform Convergence](https://mlsanity.com/paper/2303.17716/) (2023)
- [No-Regret Prediction in Marginally Stable Systems](https://mlsanity.com/paper/2002.02064/) (2020)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems](https://mlsanity.com/paper/2105.11558/) (2021)
- [Learning to Forecast Dynamical Systems from Streaming Data](https://mlsanity.com/paper/2109.09703/) (2021)
- [On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in Kalman Filters](https://mlsanity.com/paper/1809.05870/) (2018)
- [Improved rates for prediction and identification of partially observed linear dynamical systems](https://mlsanity.com/paper/2011.10006/) (2020)
- [SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory](https://mlsanity.com/paper/2010.05899/) (2020)
- [Convex Programming for Estimation in Nonlinear Recurrent Models](https://mlsanity.com/paper/1908.09915/) (2019)
- [A Linear Dynamical System Model for Text](https://mlsanity.com/paper/1502.04081/) (2015)
- [Online Learning Robust Control of Nonlinear Dynamical Systems](https://mlsanity.com/paper/2106.04092/) (2021)

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

- [Online Classification with Predictions](https://mlsanity.com/paper/2405.14066/) (2024)

## Abstract (arXiv)

We study the problem of learning to predict the next state of a dynamical system when the underlying evolution function is unknown. Unlike previous work, we place no parametric assumptions on the dynamical system, and study the problem from a learning theory perspective. We define new combinatorial measures and dimensions and show that they quantify the optimal mistake and regret bounds in the realizable and agnostic settings respectively. By doing so, we find that in the realizable setting, the total number of mistakes can grow according to any increasing function of the time horizon T. In contrast, we show that in the agnostic setting under the commonly studied notion of Markovian regret, the only possible rates are Theta(T) and tildeTheta(√T).