Universal Context Tree PTH-Order Least Squares Prediction

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 first-order 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 pges1, that asymptotically performs as well as the best piecewise linear p ^th-order model.