Time series prediction and online learning

We present a series of theoretical and algorithmic results for time series prediction leveraging recent advances in the statistical learning analysis of this problem and on-line learning. We prove the first generalization bounds for a hypothesis derived by online-to-batch conversion of the sequence of hypotheses output by an online algorithm, in the general setting of a non-stationary non-mixing stochastic process. Our learning guarantees hold for adapted sequences of hypotheses both for convex and non-convex losses. We further give generalization bounds for sequences of hypotheses that may not be adapted but that admit a stability property. Our learning bounds are given in terms of a discrepancy measure, which we show can be accurately estimated from data under a mild assumption. Our theory enables us to devise a principled solution for the notoriously difficult problem of model section in the time series scenario. It also helps us devise new ensemble methods with favorable theoretical guarantees for forecasting non-stationary time series.