Abstract

We consider the problem of sequential prediction of arbitrary real-valued sequences with side information. We first construct a universal algorithm that asymptotically achieves the performance of the best side-information dependent constant predictor, uniformly for all data and side-information sequences. We then extend these results to linear predictors of some fixed order. We derive matching upper and lower bounds, and show that the algorithms are not only universal but they are also optimal such that no sequential algorithm can give better performance for all sequences.

Original languageEnglish (US)
JournalICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume5
StatePublished - Sep 27 2004
EventProceedings - IEEE International Conference on Acoustics, Speech, and Signal Processing - Montreal, Que, Canada
Duration: May 17 2004May 21 2004

Fingerprint

predictions

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Cite this

@article{7d53d4b6cce14efd8aa1714128751d69,
title = "Min-max optimal universal prediction with side information",
abstract = "We consider the problem of sequential prediction of arbitrary real-valued sequences with side information. We first construct a universal algorithm that asymptotically achieves the performance of the best side-information dependent constant predictor, uniformly for all data and side-information sequences. We then extend these results to linear predictors of some fixed order. We derive matching upper and lower bounds, and show that the algorithms are not only universal but they are also optimal such that no sequential algorithm can give better performance for all sequences.",
author = "Kozat, {Suleyman S.} and Singer, {Andrew Carl}",
year = "2004",
month = "9",
day = "27",
language = "English (US)",
volume = "5",
journal = "Proceedings - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing",
issn = "0736-7791",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Min-max optimal universal prediction with side information

AU - Kozat, Suleyman S.

AU - Singer, Andrew Carl

PY - 2004/9/27

Y1 - 2004/9/27

N2 - We consider the problem of sequential prediction of arbitrary real-valued sequences with side information. We first construct a universal algorithm that asymptotically achieves the performance of the best side-information dependent constant predictor, uniformly for all data and side-information sequences. We then extend these results to linear predictors of some fixed order. We derive matching upper and lower bounds, and show that the algorithms are not only universal but they are also optimal such that no sequential algorithm can give better performance for all sequences.

AB - We consider the problem of sequential prediction of arbitrary real-valued sequences with side information. We first construct a universal algorithm that asymptotically achieves the performance of the best side-information dependent constant predictor, uniformly for all data and side-information sequences. We then extend these results to linear predictors of some fixed order. We derive matching upper and lower bounds, and show that the algorithms are not only universal but they are also optimal such that no sequential algorithm can give better performance for all sequences.

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

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

M3 - Conference article

AN - SCOPUS:4544382459

VL - 5

JO - Proceedings - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing

JF - Proceedings - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing

SN - 0736-7791

ER -