Asymptotically Optimal Prediction for Time-Varying Data Generating Processes

Jie Ding, Jiawei Zhou, Vahid Tarokh

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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
Issue number5
StatePublished - May 2019

Bibliographical note

Funding Information:
Manuscript received November 28, 2017; revised October 31, 2018; accepted November 4, 2018. Date of publication November 22, 2018; date of current version April 19, 2019. This work was supported by the Defense Advanced Research Projects Agency (DARPA) under Grant N66001-15-C-4028, Grant W911NF-16-1-0561, and Grant W911NF-18-1-0134. This paper was presented at the 2017 GlobalSIP Conference. J. Ding is with the School of Statistics, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: J. Zhou is with the John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138 USA (e-mail: V. Tarokh is with the Department of Electrical and Computer Engineering, Duke University, Durham, NC 27708 USA (e-mail: Communicated by I. Kontoyiannis, Associate Editor at Large. Color versions of one or more of the figures in this paper are available online at Digital Object Identifier 10.1109/TIT.2018.2882819


  • 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