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 ⚠ $\displaystyle{L_T^{\text{algorithm}} \le cL_T^{\text{best strategy}} + R(T),}$⚠ $\displaystyle{ L_T^{\text{algorithm}} \le cL_T^{\text{best strategy}} + R(L_T^{\text{best strategy}}),}$⚠ $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 ⚠ $\displaystyle{ 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 "complexity" (such as the norm) of the strategy.
Important subareas of competitive on-line prediction are:
- Prediction with expert advice, where the benchmark class is formed by free agents called experts.
- Competing with prediction rules, where the benchmark class is the class of all linear functions. This benchmark class often serves as the starting point for competing with wider benchmark classes.
The competitive on-line prediction can be applied, e.g., to:
There are many known techniques in competitive on-line prediction, such as:
- Exponential Weights Algorithms
- Defensive forecasting and shortcut.
- Follow the perturbed leader
- Gradient descent and Exponentiated gradient
Some techniques used in competitive on-line prediction are also standard in other areas of learning theory and statistics: