Competing With Prediction Rules
Competing with prediction rules is a subfield of competitive on-line prediction in which the strategies in the benchmark class are functions of a "signal", a hint output by Reality at the beginning of each step (in typical machine-learning applications, this might be the object to be labelled). The basic protocol is:
Players: Forecaster, Reality
Reality's signal is chosen from some signal space . Forecaster's goal is to compete with all functions that belong to a benchmark class ; more formally, the strategies in the benchmark class are . An important special case is online linear regression, in which is the class of all linear functions on . In this paper, generalized linear regression is considered. More generally, can be allowed to range over various function classes, such as Banach or Hilbert spaces.
An important open problem in this area is Competing with Besov spaces.