|
NeuroCOLT
Technical Report NC-TR-99-058
Worst-case
Bounds for the Logarithmic Loss of Predictors
Nicolo
Cesa-Bianchi
Gabor Lugosi
Keywords:
universal prediction; universal coding; empirical processes; on-line
learning; metric entropy
Received: 31 August, 1999
Abstract
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.
Download Compressed Postscript
|