Tracking the best regressor
Mark Herbster, Manfred K. Warmuth · 1998
In most of the on-line learning research the total on-line loss of the algorithm is compared to the total loss of the best off-line predictor u from a comparison class of predictors.We call such bounds static bounds.The interesting feature of these bounds is that they hold for an arbitrary sequence of examples.Recently some work has been done where the comparison vector ut at each trial t is allowed to change with time, and the total online loss of the algorithm is compared to the sum of the losses of ut at each trial plus the total "cost" for shifting to successive comparison vectors.This is to model situations in which the examples change over time and different predictors from the comparison class are best for different segments of the sequence of examples.We call such bounds shifting bounds.Shifting bounds still hold for arbitrary sequences of examples and also for arbitrary partitions.The algorithm does not know the offline partition and the sequence of predictors that its performance is compared against.Naturally shifting bounds are much harder to prove.The only known bounds are for the case when the comparison class consists of a finite sets of experts or boolean disjunctions.In this paper we develop the methodology for lifting known static bounds to the shifting case.In particular we obtain bounds when the comparison class consists of linear neurons (linear combinations of experts).Our essential technique consists of the following.At the end of each trial we project the hypothesis of the static algorithm into a suitably chosen convex region.This keeps the hypothesis of the algorithm well-behaved and the static bounds can be converted to shifting bounds so that the cost for shifting remains reasonable.