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:
⚠ $L_0:=0$
⚠ $t=1,2,\dots$
:
⚠ $x_t \in X$
⚠ $\gamma_t \in \Gamma$
⚠ $y_t \in Y$
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$
. In this paper, generalized linear regression is considered. 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.