Abstract. This paper presents the first generalization bounds for time series prediction with a non-stationary mixing stochastic process. We prove Rademacher complexity learning bounds for both average-path generalization with non-stationary β-mixing processes and path-dependent generalization with non-stationary φ-mixing processes. Our guarantees are expressed in terms of β-or φ-mixing coefficients and a natural measure of discrepancy between training and target distributions. They admit as special cases previous Rademacher complexity bounds for non-i.i.d. stationary distributions, for independent but not identically distributed random variables, or for the i.i.d. case. We show that, using a new sub-sample selection technique we introduce, our bounds can be tightened under the natural assumption of convergent stochastic processes. We also prove that fast learning rates can be achieved by extending existing local Rademacher complexity analysis to non-i.i.d. setting.
Finally, recent work by Kuznetsov and Mohri REF examines both average-path generalization and path-dependent generalization for certain types of non-stationary mixing processes and derives Rademacher complexity bounds.
Generalization Bounds for Time Series Prediction with Non-stationary Processes
ALT
Mathematics Computer Science