Suboptimal measures of predictive complexity for absolute loss function

V. V. V'yugin

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

The problem of existence of predictive complexity for the absolute loss game is studied. Predictive complexity is a generalization of Kolmogorov complexity which bounds the ability of any algorithm to predict elements of a sequence of outcomes. For perfectly mixable loss functions (logarithmic and squared difference are among them) predictive complexity is defined like Kolmogorov complexity to within an additive constant. The absolute loss function is not perfectly mixable, and the question of existence of the corresponding predictive complexity, which is defined to within an additive constant, is open. We prove that in the case of the absolute loss game the predictive complexity can be defined to within an additive term O(√n), where n is the length of a sequence of outcomes. We prove also that in some restricted settings this bound cannot be improved.

Original languageEnglish
Pages (from-to)146-157
Number of pages12
JournalInformation and Computation
Volume175
Issue number2
DOIs
Publication statusPublished - 15 Jun 2002
Externally publishedYes

Fingerprint

Dive into the research topics of 'Suboptimal measures of predictive complexity for absolute loss function'. Together they form a unique fingerprint.

Cite this