Paper #418

Títol:

Worst-case bounds for the logarithmic loss of predictors

Autors:

Nicolò Cesa Bianchi i Gábor Lugosi

Data:

Octubre 1999

Resum:

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.

Paraules clau:

Universal prediction, universal coding, empirical processes, on-line learning, metric entropy

Codis JEL:

C1, C13

Àrea de Recerca:

Estadística, Econometria i Mètodes Quantitatius

Publicat a:

Machine Learning, 43, 3, (2001), pp. 247-264

Descarregar el paper en format PDF