zbMATH — the first resource for mathematics

On sequences with non-learnable subsequences. (English) Zbl 1142.68410
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 302-313 (2008).
Summary: The remarkable results of Foster and Vohra was a starting point for a series of papers which show that any sequence of outcomes can be learned (with no prior knowledge) using some universal randomized forecasting algorithm and forecast-dependent checking rules. We show that for the class of all computationally efficient outcome-forecast-based checking rules, this property is violated. Moreover, we present a probabilistic algorithm generating with probability close to one a sequence with a subsequence which simultaneously miscalibrates all partially weakly computable randomized forecasting algorithms.
According to the Dawid’s prequential framework we consider partial recursive randomized algorithms.
For the entire collection see [Zbl 1136.68005].

68Q32 Computational learning theory
PDF BibTeX Cite
Full Text: DOI