Separation Curve

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

(1)

where and are positive constants, is Master's loss over the first trials, is the number of experts, and is the loss of expert , . 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 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 and shows that the Aggregating Algorithm achieves (1) whenever is on the separation curve. The open problem is:

What is the separation curve when the number of experts is fixed? What is the corresponding algorithm for Master?

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.