Non-linear inequalities between predictive and kolmogorov complexities

Michael V. Vyugin, Vladimir V. V’Yugin

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)


Predictive complexity is a generalization of Kolmogorov complexity. It corresponds to an “optimal” prediction strategy which gives a lower bound to ability of any algorithm to predict elements of a sequence of outcomes. A variety of types of loss functions makes it interesting to study relations between corresponding predictive complexities. Non-linear inequalities (with variable coefficients) between predictive complexity KG(x) of non-logarithmic type and Kolmogorov complexity K(x) (which is close to predictive complexity for logarithmic loss function) are the main subject of consideration in this paper. We deduce from these inequalities an asymptotic relation (formula presented) when n→∞, where a is a constant and l(x) is the length of a sequence x. An analogous asymptotic result holds for relative complexities K(x)/l(x) and KG(x)/l(x). To obtain these inequalities we present estimates of the cardinality of all sequences of given predictive complexity.

Original languageEnglish
Title of host publicationAlgorithmic Learning Theory - 12th International Conference, ALT 2001, Proceedings
EditorsRoni Khardon, Naoki Abe, Thomas Zeugmann
PublisherSpringer Verlag
Number of pages15
ISBN (Print)3540428755, 9783540428756
Publication statusPublished - 2001
Externally publishedYes
Event12th Annual Conference on Algorithmic Learning Theory, ALT 2001 - Washington, United States
Duration: 25 Nov 200128 Nov 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th Annual Conference on Algorithmic Learning Theory, ALT 2001
Country/TerritoryUnited States


Dive into the research topics of 'Non-linear inequalities between predictive and kolmogorov complexities'. Together they form a unique fingerprint.

Cite this