Separation Curve

The usual goal in prediction with expert advice is to prove inequalities of the type

⚠ $L_T \le c L_T(i) + a \ln n \qquad\qquad$ (1)

where ⚠ $c$ and ⚠ $a$ are positive constants, ⚠ $L_T$ is Master's loss over the first ⚠ $T$ trials, ⚠ $n$ is the number of experts, and ⚠ $L_T(i)$ is the loss of expert ⚠ $i$, ⚠ $i=1,\ldots,n$. It is usually possible to improve one of the constants by making the other constant worse. The winning set for Master is the set of all pairs ⚠ $(c,a)$ for which Master can enforce (1) no matter what the experts' predictions are. The separation curve is the boundary of the winning set. Vovk (1998) finds the separation curve for ⚠ $n\to\infty$ and shows that the Aggregating Algorithm achieves (1) whenever ⚠ $(c,a)$ is on the separation curve. The open problem is:

It is known that:

• The separation curve for a fixed number of experts is different from the separation curve for a large number of experts. This was shown by Cesa-Bianchi et al. (1996); see also Vovk 1998, Section 8.
• The Aggregating Algorithm (and even the Weighted Majority Algorithm) is not optimal for a fixed number of experts. This was shown by Littlestone and Long (1993 - 1994); see also Vovk 1998, Section 8.

Bibliography

• Nicolo Cesa-Bianchi, Yoav Freund, David P. Helmbold, and Manfred K. Warmuth. On-line prediction and conversion strategies. Machine Learning 25:71 - 110, 1996.
• Vladimir Vovk. A game of prediction with expert advice. Journal of Computer and System Sciences 56:153 - 173, 1998.