Leading strategies in competitive on-line prediction

Suppose F is a normed function class of prediction strategies (the "benchmar k class"). It is well known that, under some restrictions on F, there exists a "master prediction strategy" (sometimes also called a "universal s trategy") that performs almost as well as the best strategies in F whose norm is not too large (see, e.g., [9, 5]). The "leading prediction strategies" constructed in this paper satisfy a stronger property: the loss of any prediction strategy in F whose norm is not too large exceeds the loss of a leading strategy by the diverge nce between the predictions output by the two prediction strategies. Therefo re, the leading strategy implicitly serves as a standard for prediction strategies F in F whose norm is not too large: such a prediction strategy F suffers a small loss to the degree that its predictions resemble the leading strategy's predict ions, and the only way to compete with the leading strategy is to imitate it. We start the formal exposition with a simple asymptotic result (Prop osition 1 in 2) asserting the existence of leading strategies in the problem of on -line 1 regression with the quadratic loss function for the class of continu ous limited-memory prediction strategies.