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 whose accumulated squared prediction error, for every bounded sequenee, 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 A2p ln(n)/n, where n is the data length and the sequence is assumed to be bounded by some A. In this paper, we 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 A2p ln(n)/n.

Original languageEnglish (US)
Number of pages1
JournalIEEE International Symposium on Information Theory - Proceedings
StatePublished - Sep 12 2002
Event2002 IEEE International Symposium on Information Theory - Lausanne, Switzerland
Duration: Jun 30 2002Jul 5 2002

Fingerprint

Predictors
Lower bound
Prediction
Redundancy
Prediction Error
Linear Prediction
Error function
Loss Function
Min-max
Excess

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Cite this

A lower bound on the performance of sequential prediction. / Kozat, Suleyman S.; Singer, Andrew Carl.

In: IEEE International Symposium on Information Theory - Proceedings, 12.09.2002.

Research output: Contribution to journalConference article

@article{74821f6b131149139817878390819e9b,
title = "A lower bound on the performance of sequential prediction",
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 whose accumulated squared prediction error, for every bounded sequenee, 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 A2p ln(n)/n, where n is the data length and the sequence is assumed to be bounded by some A. In this paper, we 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 A2p ln(n)/n.",
author = "Kozat, {Suleyman S.} and Singer, {Andrew Carl}",
year = "2002",
month = "9",
day = "12",
language = "English (US)",
journal = "IEEE International Symposium on Information Theory - Proceedings",
issn = "2157-8095",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - A lower bound on the performance of sequential prediction

AU - Kozat, Suleyman S.

AU - Singer, Andrew Carl

PY - 2002/9/12

Y1 - 2002/9/12

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 whose accumulated squared prediction error, for every bounded sequenee, 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 A2p ln(n)/n, where n is the data length and the sequence is assumed to be bounded by some A. In this paper, we 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 A2p 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 whose accumulated squared prediction error, for every bounded sequenee, 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 A2p ln(n)/n, where n is the data length and the sequence is assumed to be bounded by some A. In this paper, we 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 A2p ln(n)/n.

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

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

M3 - Conference article

AN - SCOPUS:0036350890

JO - IEEE International Symposium on Information Theory - Proceedings

JF - IEEE International Symposium on Information Theory - Proceedings

SN - 2157-8095

ER -