mlsanityData to 14 Oct 2026

The Complexity of Sequential Prediction in Dynamical Systems

arXiv 2402.06614 ↗First posted 9 Feb 2024cs.LG stat.MLcited by 1

Not on the map. Why?

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).

Key facts. Cited by 1 paper 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

28 of 69 references.

References · 28

  1. 2014Sequence to Sequence Learning with Neural Networkscited by 2,986
  2. 2016Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive controlcited by 140
  3. 2016Towards better decoding and language model integration in sequence to sequence modelscited by 100
  4. 2019Online Control with Adversarial Disturbancescited by 92
  5. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 90
  6. 2022A Characterization of Multiclass Learnabilitycited by 67
  7. 2014Optimal Learners for Multiclass Problemscited by 65
  8. 2018Online Linear Quadratic Controlcited by 56
  9. 2017Learning Linear Dynamical Systems via Spectral Filteringcited by 46
  10. 2020Logarithmic Regret Bound in Partially Observable Linear Dynamical Systemscited by 46
  11. 2020Learning nonlinear dynamical systems from a single trajectorycited by 46
  12. 2019Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysiscited by 40
16 more
  1. 2020Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systemscited by 39
  2. 2018Spectral Filtering for General Linear Dynamical Systemscited by 37
  3. 2013Online Learning for Time Series Predictioncited by 33
  4. 2021Learning Graph Cellular Automatacited by 33
  5. 2020Online Learning of the Kalman Filter with Logarithmic Regretcited by 21
  6. 2023Multiclass Online Learning and Uniform Convergencecited by 19
  7. 2020No-Regret Prediction in Marginally Stable Systemscited by 18
  8. 2021Streaming Linear System Identification with Reverse Experience Replaycited by 17
  9. 2021Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systemscited by 17
  10. 2021Learning to Forecast Dynamical Systems from Streaming Datacited by 17
  11. 2018On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in Kalman Filterscited by 16
  12. 2020Improved rates for prediction and identification of partially observed linear dynamical systemscited by 12
  13. 2020SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memorycited by 11
  14. 2019Convex Programming for Estimation in Nonlinear Recurrent Modelscited by 7
  15. 2015A Linear Dynamical System Model for Textcited by 6
  16. 2021Online Learning Robust Control of Nonlinear Dynamical Systemscited by 2

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Online Classification with Predictionscited by 5