### Abstract

We consider the problem of sequential linear prediction of real-valued sequences under the square-error loss function. For this problem, a prediction algorithm has been demonstrated [1]-[3] whose accumulated squared prediction error, for every bounded sequence, is asymptotically as small as the best fixed linear predictor for that sequence, taken from the class of all linear predictors of a given order p. The redundancy, or excess prediction error above that of the best predictor for that sequence, is upper-bounded by A ^{2} p ln(n)/n, where n is the data length and the sequence is assumed to be bounded by some A. In this correspondence, we provide an alternative proof of this result by connecting it with universal probability assignment. We then show that this predictor is optimal in a min-max sense, by deriving a corresponding lower bound, such that no sequential predictor can ever do better than a redundancy of A ^{2}p ln(n)/n.

Original language | English (US) |
---|---|

Pages (from-to) | 2354-2362 |

Number of pages | 9 |

Journal | IEEE Transactions on Information Theory |

Volume | 48 |

Issue number | 8 |

DOIs | |

State | Published - Aug 1 2002 |

### Keywords

- Min-max
- Prediction
- Sequential probability assignment
- Universal algorithms

### ASJC Scopus subject areas

- Information Systems
- Computer Science Applications
- Library and Information Sciences

## Fingerprint Dive into the research topics of 'Universal linear least squares prediction: Upper and lower bounds'. Together they form a unique fingerprint.

## Cite this

*IEEE Transactions on Information Theory*,

*48*(8), 2354-2362. https://doi.org/10.1109/TIT.2002.800489