Asymptotically Optimal Prediction for Time-Varying Data Generating Processes

Jie Ding, Jiawei Zhou, Vahid Tarokh

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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 2019

Bibliographical note

Publisher Copyright:
© 1963-2012 IEEE.

Keywords

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

Fingerprint

Dive into the research topics of 'Asymptotically Optimal Prediction for Time-Varying Data Generating Processes'. Together they form a unique fingerprint.

Cite this