2006/09/09 by Vladimir Vovk, Vovk, Vladimir · 1 citation
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #cs.LG
paper · pdf · doi:10.48550/arxiv.cs/0609045
41 pages
arxiv created 2006/09/09 · arxiv updated 2009/12/01
Competitive on-line prediction (also known as universal prediction of individual sequences) is a strand of learning theory avoiding making any stochastic assumptions about the way the observations are generated. The predictor's goal is to compete with a benchmark class of prediction rules, which is often a proper Banach function space. Metric entropy provides a unifying framework for competitive on-line prediction: the numerous known upper bounds on the metric entropy of various compact sets in function spaces readily imply bounds on the performance of on-line prediction strategies. This paper discusses strengths and limitations of the direct approach to competitive on-line prediction via metric entropy, including comparisons to other approaches.