Metric entropy in competitive on-line prediction

Abstract

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.

41 pages

References in corpus (3)

• On-line regression competitive with reproducing kernel Hilbert spaces
• Competing with Markov prediction strategies
• Leading strategies in competitive on-line prediction

Cited by in corpus (7)

• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• A Chaining Algorithm for Online Nonparametric Regression
• Online Nonparametric Regression with General Loss Functions
• Efficient online learning with kernels for adversarial large scale problems
• Aggregating Algorithm competing with Banach lattices
• Supermartingales in Prediction with Expert Advice
• Locally-Adaptive Nonparametric Online Learning