Derandomizing stochastic prediction strategies

Abstract

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'.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 99 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.