Abstract. We consider algorithms for combining advice from a set of experts. In each trial, the algorithm receives the predictions of the experts and produces its own prediction. A loss function is applied to measure the discrepancy between the predictions and actual observations. The algorithm keeps a weight for each expert. At each trial the weights are rst used to help produce the prediction and then updated according to the observed outcome. Our starting point is Vovk's Aggregating Algorithm, in which the weights have a simple form: the weight of an expert decreases exponentially as a function of the loss incurred by the expert. The prediction of the Aggregating Algorithm is typically a nonlinear function of the weights and the experts' predictions. We analyze here a simpli ed algorithm in which the weights are as in the original Aggregating Algorithm, but the prediction is simply the weighted average of the experts' predictions. We show that for a large class of loss functions, even with the simpli ed prediction rule the additional loss of the algorithm over the loss of the best expert is at most c ln n, where n is the number of experts and c a constant that depends on the loss function. Thus, the bound is of the same form as the known bounds for the Aggregating Algorithm, although the constants here are not quite as good. We use relative entropy to rewrite the bounds in a stronger form and to motivate the update.
Variants of the aggregating algorithm have been studied for classically mixable losses, with a trade-off between tightness of the bound (in a constant factor) and the computational complexity REF .
Averaging Expert Predictions
EuroCOLT
Computer Science