The Complexity of Sequential Prediction in Dynamical Systems
- Resource Type
- Working Paper
- Authors
- Raman, Vinod; Subedi, Unique; Tewari, Ambuj
- Source
- Subject
- Computer Science - Machine Learning
Statistics - Machine Learning
- Language
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 setting respectively.
Comment: 35 pages