Worst-case bounds for the redundancy of sequential lossless codes and for the logarithmic loss of predictors
Nicolò Cesa‐Bianchi, Gábor Lugosi · 2002
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 (1987) 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 and is applicable to both parametric and nonparametric classes of predictors.