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
Protocol:

Initialize $L_0:=0$

FOR $t=1,2,\dots$

Reality announces $x_t \in X$

Forecaster announces $\gamma_t \in \Gamma$

Reality announces $y_t \in Y$

Update cumulative loss $L_t=L_{t-1} + \lambda(y_t,\gamma_t)$

END

Reality's signal $x_t$ is chosen from some signal space $X$ . Forecaster's goal is to compete with all functions $f: X \to \Gamma$ that belong to a benchmark class $\mathcal{F}$ ; more formally, the strategies in the benchmark class are $\gamma_t:=f(x_t)$ . An important special case is online linear regression, in which $\mathcal{F}$ is the class of all linear functions on $X$ . More generally, $f$ 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.