To access the full text documents, please follow this link:

On prediction of individual sequences
Cesa Bianchi, Nicolo; Lugosi, Gábor
Universitat Pompeu Fabra. Departament d'Economia i Empresa
Sequential randomized prediction of an arbitrary binary sequence isinvestigated. 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 minimaxrelative 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.
Statistics, Econometrics and Quantitative Methods
universal prediction
prediction with experts
absolute loss
empirical processes
covering numbers
finite-state machines
L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons
Working Paper

Show full item record