Metric entropy in competitive on-line prediction

A typical result of competitive on-line prediction says that, for a giv en benchmark class of prediction strategies, there is a prediction strategy that performs almost as well as the best prediction strategies in the benchmark cla ss. For simplicity, in this paper the performance of a prediction strategy will be measured by the cumulative squared distance between its predictions a nd the true observations, assumed to be real (occasionally complex) numbers . Different methods of competitive on-line predictions (such as Gradient Desce nt, following the perturbed leader, strong and weak aggregating algorithms, d efensive forecasting, etc.) tend to have their narrow "area of expertise": eac h works well for benchmark classes of a specific "size" but is not readily applicable to c lasses of a different size. In this paper we will apply a simple general method based on metric ent ropy to benchmark classes of a wide range of sizes. Typically, this method does not give optimal results, but its results are often not much worse than those given by specialized methods, especially for benchmark classes that are not too massive.