Derandomizing stochastic prediction strategies
Vladimir Vovk · 1997
We give a new interpretation of the games of prediction with expert advice.Instead of a pool of experts we consider only one Ystochsstic predictor" and notice that if the stochastic predictor's total loss is at most L with probability at least p then the learner's loss can be bounded by CL + a In f for the usual constants c and a.This interpretation is used to revamp known results and obtain new results on tracking the best expert.It is also applied to merging overconfident experts and to fitting polynomials to data. AGGREGATING ALGORITHMOur learning protocol is as follows.The learner interacts with the stochastic predictor and the nature in the following way.At each trial t, t = 1,2,. ..:l The stochastic predictor makes a random prediction ('t in a fixed prediction space I'.