Universal piecewise linear regression of individual sequences: Lower bound

Georg C. Zeitler, Andrew Carl Singer, Suleyman S. Kozat

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider universal piecewise linear regression of real valued bounded sequences under the squared loss function. In this setting, we present a lower bound on the regret of a universal sequential piecewise linear regressor compared to the best piecewise linear regressor that has access to the entire sequence in advance. This lower bound is tight in that it achieves the corresponding upper bound, suggesting a minmax optimality of the sequential regressor, for every individual bounded sequence.

Original languageEnglish (US)
Title of host publication2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07
DOIs
StatePublished - Aug 6 2007
Event2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07 - Honolulu, HI, United States
Duration: Apr 15 2007Apr 20 2007

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume3
ISSN (Print)1520-6149

Other

Other2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07
CountryUnited States
CityHonolulu, HI
Period4/15/074/20/07

Fingerprint

Linear regression

Keywords

  • Minimax methods
  • Piecewise linear approximation
  • Prediction methods
  • Regression
  • Universal

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Cite this

Zeitler, G. C., Singer, A. C., & Kozat, S. S. (2007). Universal piecewise linear regression of individual sequences: Lower bound. In 2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07 [4217841] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 3). https://doi.org/10.1109/ICASSP.2007.366811

Universal piecewise linear regression of individual sequences : Lower bound. / Zeitler, Georg C.; Singer, Andrew Carl; Kozat, Suleyman S.

2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07. 2007. 4217841 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 3).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Zeitler, GC, Singer, AC & Kozat, SS 2007, Universal piecewise linear regression of individual sequences: Lower bound. in 2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07., 4217841, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, vol. 3, 2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07, Honolulu, HI, United States, 4/15/07. https://doi.org/10.1109/ICASSP.2007.366811
Zeitler GC, Singer AC, Kozat SS. Universal piecewise linear regression of individual sequences: Lower bound. In 2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07. 2007. 4217841. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2007.366811
Zeitler, Georg C. ; Singer, Andrew Carl ; Kozat, Suleyman S. / Universal piecewise linear regression of individual sequences : Lower bound. 2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07. 2007. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).
@inproceedings{35683c54e20b44a6af4ef632898760e6,
title = "Universal piecewise linear regression of individual sequences: Lower bound",
abstract = "We consider universal piecewise linear regression of real valued bounded sequences under the squared loss function. In this setting, we present a lower bound on the regret of a universal sequential piecewise linear regressor compared to the best piecewise linear regressor that has access to the entire sequence in advance. This lower bound is tight in that it achieves the corresponding upper bound, suggesting a minmax optimality of the sequential regressor, for every individual bounded sequence.",
keywords = "Minimax methods, Piecewise linear approximation, Prediction methods, Regression, Universal",
author = "Zeitler, {Georg C.} and Singer, {Andrew Carl} and Kozat, {Suleyman S.}",
year = "2007",
month = "8",
day = "6",
doi = "10.1109/ICASSP.2007.366811",
language = "English (US)",
isbn = "1424407281",
series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",
booktitle = "2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07",

}

TY - GEN

T1 - Universal piecewise linear regression of individual sequences

T2 - Lower bound

AU - Zeitler, Georg C.

AU - Singer, Andrew Carl

AU - Kozat, Suleyman S.

PY - 2007/8/6

Y1 - 2007/8/6

N2 - We consider universal piecewise linear regression of real valued bounded sequences under the squared loss function. In this setting, we present a lower bound on the regret of a universal sequential piecewise linear regressor compared to the best piecewise linear regressor that has access to the entire sequence in advance. This lower bound is tight in that it achieves the corresponding upper bound, suggesting a minmax optimality of the sequential regressor, for every individual bounded sequence.

AB - We consider universal piecewise linear regression of real valued bounded sequences under the squared loss function. In this setting, we present a lower bound on the regret of a universal sequential piecewise linear regressor compared to the best piecewise linear regressor that has access to the entire sequence in advance. This lower bound is tight in that it achieves the corresponding upper bound, suggesting a minmax optimality of the sequential regressor, for every individual bounded sequence.

KW - Minimax methods

KW - Piecewise linear approximation

KW - Prediction methods

KW - Regression

KW - Universal

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

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

U2 - 10.1109/ICASSP.2007.366811

DO - 10.1109/ICASSP.2007.366811

M3 - Conference contribution

AN - SCOPUS:34547526314

SN - 1424407281

SN - 9781424407286

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

BT - 2007 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '07

ER -