Predictive complexity is a generalization of Kolmogorov complexity
to a wide class of *on-line prediction games*
(including both prediction and decision-making scenarios).
Some of the most popular on-line prediction games are:

- The
*log-loss*game. - It formalizes the processes of probability forecasting and loss-less compression. Predictive complexity for this game is a variant of Kolmogorov complexity (the logarithm of the a priori semimeasure).
- The
*square-loss*game. - This game formalizes statistical regression done in the on-line fashion.
*Cover's*game.- Formalizes the process of investing in a stock market when only long positions are allowed.
- The
*long-short*game. - A version of the previous game when short positions are also allowed.

- The criterion of existence of predictive complexity for binary games: the predictive complexity only exists for mixable games.
- The number of easy-to-predict binary sequences is exponentially small, with a known base of the exponent.

Papers (zipped postscript):

- Probability theory for the Brier game
by Volodya Vovk.
This and next papers introduce predictive complexity.
Published in the ALT 1997 proceedings
and
*Theoretical Computer Science***261**, 57–79, 2001. - Universal portfolio selection by Vovk and Chris Watkins. This and previous papers introduce predictive complexity. Published in the COLT 1998 proceedings, pp 12–13.
- General linear relations
between different types of predictive complexity
by Yura Kalnishkan.
This paper gives a general method for establishing tight linear inequalities
between predictive complexities.
Published in the ALT 1999 proceedings
and
*Theoretical Computer Science***271**, 181–200, 2002. - Loss functions, complexities and the Legendre transformation
by Kalnishkan, Vovk, and Misha Vyugin.
This paper shows how the loss function can be extracted
(up to the parameterization)
from the predictive complexity.
It appears that convex analysis
(via, e.g., the notion of generalized entropy)
plays a fundamental role in the theory of predictive complexity.
Published in the ALT 2001 proceedings
and
*Theoretical Computer Science***313**, 195–207, 2004. - Mixability and the existence of weak complexities by Kalnishkan and Vyugin. By definition, predictive complexity is the best, with accuracy O(1), upper semicomputable superloss process. For some important games predictive complexity in this sense does not exist. This paper shows that for a wide class of games there is "weak predictive complexity", where O(1) is replaced by O(sqrt(n)), n being the length of the data sequence. Published in the COLT 2002 proceedings.
- On the absence of predictive complexity for some games by Kalnishkan and Vyugin. This paper proves the absence of predictive complexity (defined, as usual, to within an additive constant) in the case where the curvature of the loss function vanishes at an interior point. This result is less general than the criterion in [8], but it gives an estimate of the accuracy with which predictive complexity exists. Published in the ALT 2002 proceedings.
- How many strings are easy to predict?
by Kalnishkan, Vovk, and Vyugin.
The result of this paper generalizes the incompressibility property
of Kolmogorov complexity.
Published in the COLT 2003 proceedings
and
*Information and Computation***201**, 55–71, 2005. - A criterion for the existence of predictive complexity
for binary games
by Kalnishkan, Vovk, and Vyugin.
It is well known that there exists a universal (i.e., optimal to within an additive constant if allowed to work infinitely long) algorithm for lossless data compression (Kolmogorov, Levin). The game of lossless compression is an example of an on-line prediction game; for some other on-line prediction games (such as the simple prediction game) a universal algorithm is known not to exist. In this paper we give an analytic characterisation of those binary on-line prediction games for which a universal prediction algorithm exists. Published in the ALT 2004 proceedings.

- Generalized entropy and asymptotic complexities of languages
by Kalnishkan, Vovk, and Vyugin.
In this paper the concept of asymptotic complexity of languages is introduced. This concept formalises the notion of learnability in a particular environment and generalises Lutz and Fortnow's concepts of predictability and dimension. Then asymptotic complexities in different prediction environments are compared by describing the set of all pairs of asymptotic complexities with respect to different environments. A geometric characterisation in terms of generalised entropies is obtained and thus the results of Lutz and Fortnow are generalised. The conference version of this paper is published in the COLT 2007 proceedings.

Talks:

- Talk at the DIMACS Workshop on Complexity and Inference (Piscataway, New Jersey, 5 June 2003); click here.
- Talk at the 18th Annual IEEE Conference on Computational Complexity, Kolmogorov Day (Aarhus, Denmark, 6 July 2003); click here. Some of the results mentioned in the talk are proved in this paper.
- Talk at COLT 2007 (San Diego, California, 14 June 2007): click here. The talk is based on this paper.