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 language | English (US) |
---|---|
Article number | 8543249 |
Pages (from-to) | 3034-3067 |
Number of pages | 34 |
Journal | IEEE Transactions on Information Theory |
Volume | 65 |
Issue number | 5 |
DOIs | |
State | Published - 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