|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-98-026
On
Prediction of Individual Sequences
Nicolo Cesa-Bianchi
University of Milan
Gabor Lugosi
Pompeu Fabra University
Barcelona
Received:
28-JUL-98
Abstract
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.
Download Compressed Postscript
|