We investigate on-line prediction of individual sequences. Given a class
of predictors, the goal is to predict as well as the best predictor in
the class, where the loss is measured by the self information
(logarithmic) loss function. The excess loss (regret) is closely related
to the redundancy of the associated lossless universal code. Using
Shtarkov's theorem and tools from empirical process theory, we prove a
general upper bound on the best possible (minimax) regret. The bound
depends ...
We investigate on-line prediction of individual sequences. Given a class
of predictors, the goal is to predict as well as the best predictor in
the class, where the loss is measured by the self information
(logarithmic) loss function. The excess loss (regret) is closely related
to the redundancy of the associated lossless universal code. Using
Shtarkov's theorem and tools from empirical process theory, we prove a
general upper bound on the best possible (minimax) regret. The bound
depends on certain metric properties of the class of predictors. We
apply the bound to both parametric and nonparametric classes of
predictors. Finally, we point out a suboptimal behavior of the popular
Bayesian weighted average algorithm.
+