Asymptotically Optimal Prediction for Time-Varying Data Generating Processes

Jie Ding, Jiawei Zhou, Vahid Tarokh

Research output: Contribution to journalArticle

Abstract

We develop a methodology (referred to as kinetic prediction) for predicting time series undergoing unknown changes in their data generating distributions. Based on Kolmogorov-Tikhomirov's {\varepsilon } -entropy, we propose a concept called {\varepsilon } -predictability that quantifies the size of a model class (which can be parametric or nonparametric) and the maximal number of abrupt structural changes that guarantee the achievability of asymptotically optimal prediction. Moreover, for parametric distribution families, we extend the aforementioned kinetic prediction with discretized function spaces to its counterpart with continuous function spaces, and propose a sequential Monte Carlo-based implementation. We also extend our methodology for predicting smoothly varying data generating distributions. Under reasonable assumptions, we prove that the average predictive performance converges almost surely to the oracle bound, which corresponds to the case that the data generating distributions are known in advance. The results also shed some light on the so called 'prediction-inference dilemma.' Various examples and numerical results are provided to demonstrate the wide applicability of our methodology.

Original languageEnglish (US)
Article number8543249
Pages (from-to)3034-3067
Number of pages34
JournalIEEE Transactions on Information Theory
Volume65
Issue number5
DOIs
StatePublished - May 1 2019

Fingerprint

methodology
Kinetics
entropy
structural change
time series
Time series
guarantee
Entropy
time
performance

Keywords

  • Change points
  • Kolmogorov-Tikhomirov ϵ-entropy
  • kinetic prediction
  • online tracking
  • optimal prediction
  • sequential Monte-Carlo
  • smooth variations
  • time series

Cite this

Asymptotically Optimal Prediction for Time-Varying Data Generating Processes. / Ding, Jie; Zhou, Jiawei; Tarokh, Vahid.

In: IEEE Transactions on Information Theory, Vol. 65, No. 5, 8543249, 01.05.2019, p. 3034-3067.

Research output: Contribution to journalArticle

@article{555312f707fc4fe39f03a3d46180d38a,
title = "Asymptotically Optimal Prediction for Time-Varying Data Generating Processes",
abstract = "We develop a methodology (referred to as kinetic prediction) for predicting time series undergoing unknown changes in their data generating distributions. Based on Kolmogorov-Tikhomirov's {\varepsilon } -entropy, we propose a concept called {\varepsilon } -predictability that quantifies the size of a model class (which can be parametric or nonparametric) and the maximal number of abrupt structural changes that guarantee the achievability of asymptotically optimal prediction. Moreover, for parametric distribution families, we extend the aforementioned kinetic prediction with discretized function spaces to its counterpart with continuous function spaces, and propose a sequential Monte Carlo-based implementation. We also extend our methodology for predicting smoothly varying data generating distributions. Under reasonable assumptions, we prove that the average predictive performance converges almost surely to the oracle bound, which corresponds to the case that the data generating distributions are known in advance. The results also shed some light on the so called 'prediction-inference dilemma.' Various examples and numerical results are provided to demonstrate the wide applicability of our methodology.",
keywords = "Change points, Kolmogorov-Tikhomirov ϵ-entropy, kinetic prediction, online tracking, optimal prediction, sequential Monte-Carlo, smooth variations, time series",
author = "Jie Ding and Jiawei Zhou and Vahid Tarokh",
year = "2019",
month = "5",
day = "1",
doi = "10.1109/TIT.2018.2882819",
language = "English (US)",
volume = "65",
pages = "3034--3067",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "IEEE",
number = "5",

}

TY - JOUR

T1 - Asymptotically Optimal Prediction for Time-Varying Data Generating Processes

AU - Ding, Jie

AU - Zhou, Jiawei

AU - Tarokh, Vahid

PY - 2019/5/1

Y1 - 2019/5/1

N2 - We develop a methodology (referred to as kinetic prediction) for predicting time series undergoing unknown changes in their data generating distributions. Based on Kolmogorov-Tikhomirov's {\varepsilon } -entropy, we propose a concept called {\varepsilon } -predictability that quantifies the size of a model class (which can be parametric or nonparametric) and the maximal number of abrupt structural changes that guarantee the achievability of asymptotically optimal prediction. Moreover, for parametric distribution families, we extend the aforementioned kinetic prediction with discretized function spaces to its counterpart with continuous function spaces, and propose a sequential Monte Carlo-based implementation. We also extend our methodology for predicting smoothly varying data generating distributions. Under reasonable assumptions, we prove that the average predictive performance converges almost surely to the oracle bound, which corresponds to the case that the data generating distributions are known in advance. The results also shed some light on the so called 'prediction-inference dilemma.' Various examples and numerical results are provided to demonstrate the wide applicability of our methodology.

AB - We develop a methodology (referred to as kinetic prediction) for predicting time series undergoing unknown changes in their data generating distributions. Based on Kolmogorov-Tikhomirov's {\varepsilon } -entropy, we propose a concept called {\varepsilon } -predictability that quantifies the size of a model class (which can be parametric or nonparametric) and the maximal number of abrupt structural changes that guarantee the achievability of asymptotically optimal prediction. Moreover, for parametric distribution families, we extend the aforementioned kinetic prediction with discretized function spaces to its counterpart with continuous function spaces, and propose a sequential Monte Carlo-based implementation. We also extend our methodology for predicting smoothly varying data generating distributions. Under reasonable assumptions, we prove that the average predictive performance converges almost surely to the oracle bound, which corresponds to the case that the data generating distributions are known in advance. The results also shed some light on the so called 'prediction-inference dilemma.' Various examples and numerical results are provided to demonstrate the wide applicability of our methodology.

KW - Change points

KW - Kolmogorov-Tikhomirov ϵ-entropy

KW - kinetic prediction

KW - online tracking

KW - optimal prediction

KW - sequential Monte-Carlo

KW - smooth variations

KW - time series

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

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

U2 - 10.1109/TIT.2018.2882819

DO - 10.1109/TIT.2018.2882819

M3 - Article

AN - SCOPUS:85057205101

VL - 65

SP - 3034

EP - 3067

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 5

M1 - 8543249

ER -