Worst-case bounds for the logarithmic loss of predictors
AbstractWe 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 InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Department of Economics and Business, Universitat Pompeu Fabra in its series Economics Working Papers with number 418.
Date of creation: Oct 1999
Date of revision:
Contact details of provider:
Web page: http://www.econ.upf.edu/
Universal prediction; universal coding; empirical processes; on-line learning; metric entropy;
Find related papers by JEL classification:
- C1 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods and Methodology: General
- C13 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods and Methodology: General - - - Estimation: General
This paper has been announced in the following NEP Reports:
- NEP-ALL-2000-03-06 (All new papers)
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Alessio Sancetta, 2010. "Bootstrap model selection for possibly dependent and heterogeneous data," Annals of the Institute of Statistical Mathematics, Springer, Springer, vol. 62(3), pages 515-546, June.
If references are entirely missing, you can add them using this form.