Weighted Average Algorithm

Weighted Average Algorithm is an algorithm for prediction with expert advice, one of the exponential weights algorithms. In the simplest case, the algorithm predicts a sequence of numbers {⚠ $ y_n\in[0,1] $} using advice from a finite number {⚠ $K$} of experts. The prediction space is {⚠ $ [0,1] $}. Each expert is initially assigned weight {⚠ $ 1/K $}. Unlike Strong Aggregating Algorithm, the master's prediction is the weighted average of the experts' predictions, and this simplicity is the main advantage of Weighted Average Algorithm. It can be shown, that for the square-loss game (see loss function) the algorithm guarantees the inequality

{⚠ $ L_T \le L_T(k)+2\ln K $}

for all {⚠ $T$} and {⚠ $k$}, where {⚠ $L_T$} is the loss suffered by master over the first {⚠ $T$} trials, and {⚠ $L_T(k)$} is the loss suffered by the {⚠ $k$}th expert over the first {⚠ $T$} trials.

The Weighted Average Algorithm was introduced by Kivinen and Warmuth (1994), in particular for the square-loss game, log-loss game, and game with Hellinger loss. It was generalized for the case where output is multi-dimensional, {⚠ $y_n\in[0,1]^m$}.

The interesting fact about the Weighted Average Algorithm is that the first bound is derived for the case of non-mixable games, and it depends on ⚠ $T$ as ⚠ $\sqrt{T}$. This fact can be a starting point to answer on the Better Loss Bounds for Mixable Games.

Bibliography

• Jyrki Kivinen and Manfred K. Warmuth. Averaging expert predictions. In Paul Fischer and Hans U. Simon, editors, Computational Learning Theory: 4th European Conference, volume 1572 of Lecture Notes in Artificial Intelligence, pp. 153 - 157, Berlin, 1999. Springer.