Lugosi
Le Jeudi 16 Mars 2000 à 14h30
au LRI,
Salle 101
(Université Pompeu Fabra, Barcelone)
Prediction of individual sequences
Résumé/Abstract :
We investigate sequential prediction of an arbitrary
binary sequence. In this model the sequence is
completely arbitrary, no assumption is made on the
mechanism of generating the bit sequence.
The goal of the predictor is to minimize its relative
loss, that is, to make almost as few mistakes as the
best ``expert'' in a fixed, possibly infinite, set of experts.
After introducing the basics, we point out a
surprising connection between this prediction
problem and empirical process theory.
We show general upper and lower bounds on the minimax
loss in terms of the geometry of the class of experts.
As main examples, we determine the exact order of magnitude
of the minimax regret for the class of autoregressive
linear predictors and for the class of Markov experts.