Sequential randomized prediction of an arbitrary binary sequence is
investigated. No assumption is made on the mechanism of generating
the bit sequence. The goal of the predictor is to minimize its
relative loss, i.e., to make (almost) as few mistakes as the best
``expert'' in a fixed, possibly infinite, set of experts. We point
out a surprising connection between this prediction problem and
empirical process theory. First, in the special case of static
(memoryless) experts, we completely ...
Sequential randomized prediction of an arbitrary binary sequence is
investigated. No assumption is made on the mechanism of generating
the bit sequence. The goal of the predictor is to minimize its
relative loss, i.e., to make (almost) as few mistakes as the best
``expert'' in a fixed, possibly infinite, set of experts. We point
out a surprising connection between this prediction problem and
empirical process theory. First, in the special case of static
(memoryless) experts, we completely characterize the minimax
relative loss in terms of the maximum of an associated Rademacher
process. Then we show general upper and lower bounds on the minimax
relative loss in terms of the geometry of the class of experts. As
main examples, we determine the exact order of magnitude of the
minimax relative loss for the class of autoregressive linear
predictors and for the class of Markov experts.
+