Universal context tree P^TH-order least squares prediction

Abstract

We examine the sequential prediction of individual sequences under the square error loss using a competitive algorithm framework. Previous work has described a first-order algorithm that competes against a doubly exponential number of piecewise linear models. Using context trees, this firstorder algorithm achieves the performance of the best piecewise linear first-order model that can choose its prediction parameters observing the entire sequence in advance, uniformly, for any individual sequence, with a complexity only linear in the depth of the context tree. In this paper, we extend these results to a sequential predictor of order p > 1, that asymptotically performs as well as the best piecewise linear pth-order model. © 2006 IEEE.