The Complexity of Sequential Prediction in Dynamical Systems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912409758728192 |
|---|---|
| author | Raman, Vinod Subedi, Unique Tewari, Ambuj |
| author_facet | Raman, Vinod Subedi, Unique Tewari, Ambuj |
| contents | 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 \emph{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 $Θ(T)$ and $\tildeΘ(\sqrt{T})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_06614 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Complexity of Sequential Prediction in Dynamical Systems Raman, Vinod Subedi, Unique Tewari, Ambuj Machine Learning 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 \emph{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 $Θ(T)$ and $\tildeΘ(\sqrt{T})$. |
| title | The Complexity of Sequential Prediction in Dynamical Systems |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2402.06614 |