Universal linear least squares prediction: Upper and lower bounds

Andrew Carl Singer, Suleyman S. Kozat, Meir Feder

Research output: Contribution to journalLetter

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 2p ln(n)/n.

Original languageEnglish (US)
Pages (from-to)2354-2362
Number of pages9
JournalIEEE Transactions on Information Theory
Volume48
Issue number8
DOIs
StatePublished - Aug 1 2002

Fingerprint

redundancy
Redundancy

Keywords

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

ASJC Scopus subject areas

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

Cite this

Universal linear least squares prediction : Upper and lower bounds. / Singer, Andrew Carl; Kozat, Suleyman S.; Feder, Meir.

In: IEEE Transactions on Information Theory, Vol. 48, No. 8, 01.08.2002, p. 2354-2362.

Research output: Contribution to journalLetter

Singer, Andrew Carl ; Kozat, Suleyman S. ; Feder, Meir. / Universal linear least squares prediction : Upper and lower bounds. In: IEEE Transactions on Information Theory. 2002 ; Vol. 48, No. 8. pp. 2354-2362.
@article{8606110d502b408d9ca9e9f562644563,
title = "Universal linear least squares prediction: Upper and lower bounds",
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 2p ln(n)/n.",
keywords = "Min-max, Prediction, Sequential probability assignment, Universal algorithms",
author = "Singer, {Andrew Carl} and Kozat, {Suleyman S.} and Meir Feder",
year = "2002",
month = "8",
day = "1",
doi = "10.1109/TIT.2002.800489",
language = "English (US)",
volume = "48",
pages = "2354--2362",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "8",

}

TY - JOUR

T1 - Universal linear least squares prediction

T2 - Upper and lower bounds

AU - Singer, Andrew Carl

AU - Kozat, Suleyman S.

AU - Feder, Meir

PY - 2002/8/1

Y1 - 2002/8/1

N2 - 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 2p ln(n)/n.

AB - 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 2p ln(n)/n.

KW - Min-max

KW - Prediction

KW - Sequential probability assignment

KW - Universal algorithms

UR - http://www.scopus.com/inward/record.url?scp=0036672580&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036672580&partnerID=8YFLogxK

U2 - 10.1109/TIT.2002.800489

DO - 10.1109/TIT.2002.800489

M3 - Letter

AN - SCOPUS:0036672580

VL - 48

SP - 2354

EP - 2362

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 8

ER -