On prediction of individual sequences

• 成果类型: Article
• 署名作者: Cesa-Bianchi, N; Lugosi, G
• 署名单位: University of Milan; Pompeu Fabra University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• 发表日期: 1999
• 页码: 1865-1895
• 关键词: universal prediction; expert advice

摘要

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 (or regret), that; is, 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) expert, we completely characterize the minim ax regret in terms of the maximum of an associated Rademacher process. Then we show general upper and lower bounds on the minimax regret 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.