 |
Universität Augsburg
|
|
|
Universität Augsburg
|
|
Jago Silberbauer
Ludwig-Maximilians-Universität München
spricht am
Mittwoch, 22. April 2026
um
10:30 Uhr
im
Raum 2004 (L1)
über das Thema:
| Abstract: |
| A common intuition is that increasing the order of a Markov chain (i.e. its memory) should eventually yield universal approximation property on finite state spaces. In this talk, we show that the reality is more subtle. We consider a finite concept class and study the expected Bayes risk when concepts are drawn uniformly at random and predictions are restricted to higher-order Markov models. Our main result identifies a dichotomy governed by the size of the testing regime as w tends to infinity. When concepts are evaluated against exponentially many queries, the expected Bayes risk remains bounded away from zero even as the order gets large, revealing an intrinsic limitation of higher-order Markov models. In contrast, under more moderate testing regimes, the Bayes risk vanishes in the limit, establishing that higher-order Markov chains do achieve universal approximation in this setting. This dichotomy shows that the expressive power of Markov models depends critically on how we probe them: what looks like a universal approximator under coarse evaluation can fail dramatically under finer evaluation. |
| Hierzu ergeht herzliche Einladung. |
| Prof. Dr. Markus Heydenreich |