Competitive On-line Prediction

In Competitive On-line Prediction one starts from a benchmark class of prediction strategies, and the goal is to design a prediction algorithm competitive with the best strategies in the benchmark class.

Consider a triple $(\Omega,\Gamma,\lambda)$, called a game of prediction. It consists of $\Omega$, the set of possible outcomes $\omega$, $\Gamma$, the set of possible predictions $\gamma$, and the loss function $\lambda: \Omega \times \Gamma \to \mathbb{R}$. The loss function $\lambda(\omega,\gamma)$ measures the discrepancy between the current prediction and the actual outcome. The game is played in discrete time $t=1,2,\dots$. The cumulative loss $L_T=\sum_{t=1}^T \lambda(\omega_t,\gamma_t)$ is a measure of performance of the predictions $\gamma_t$ on the realized outcomes $\omega_t$. One can consider the performance of the best strategy in the chosen benchmark class and the performance of a prediction algorithm. Theoretical guarantees for the performance of the algorithm are often stated in the form

$$
  L_T^{\text{algorithm}} \le cL_T^{\text{best strategy}} + R(T),
$$

or

$$
  L_T^{\text{algorithm}} \le cL_T^{\text{best strategy}} + R(L_T^{\text{best strategy}}),
$$

where $R(\cdot)$ is the regret term and $c$ does not depend on $T$. However, for "big" benchmark classes such regret terms are impossible, and the perfomance guarantee becomes

$$
  L_T^{\text{algorithm}} \le cL_T^{\text{strategy}} + R(\left\|\text{strategy}\right\|,T),
$$

which is required to hold for all strategies in the benchmark class; the regret term is now allowed to depend on the "compexity" (such as the norm) of the strategy.

Important subareas of competitive on-line prediction are:

The competitive on-line prediction can be applied to

There are many known techniques in competitive on-line prediction, such as:

Some techniques used in competitive on-line prediction are also standard in other areas of learning theory and statistics:

Some open questions: