Hedge Bound

This question is about Freund and Schapire's Hedge framework (see the article about the Hedge Algorithm). Suppose the number of experts is $K$.

It is known that the strong aggregating algorithm is not optimal for some games of prediction (see the article on separation curve), but it might well be optimal for the Hedge framework. It is known that the Hedge Algorithm is not optimal for the Hedge framework (since its bound can be improved by the strong aggregating algorithm).

The question is only open for a finite number of experts. When $K\to\infty$, even the Hedge Algorithm is optimal.

The question has been considered in Abernethy et al. (2008). Is this an answer on this question?


  • Jacob Abernethy, Manfred Warmuth and Joel Yellin. Optimal Strategies for Random Walks. In: Proceedings of COLT, 2008.