Generalization bounds for time series prediction with non-stationary processes

Vitaly Kuznetsov, Mehryar Mohri

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 averagepath generalization with non-stationary β-mixing processes and pathdependent 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.

Original languageEnglish (US)
Title of host publicationAlgorithmic Learning Theory - 25th International Conference, ALT 2014, Proceedings
EditorsPeter Auer, Alexander Clark, Thomas Zeugmann, Sandra Zilles
PublisherSpringer Verlag
Number of pages15
ISBN (Electronic)9783319116617
StatePublished - 2014
Event25th International Conference on Algorithmic Learning Theory, ALT 2014 - Bled, Slovenia
Duration: Oct 8 2014Oct 10 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other25th International Conference on Algorithmic Learning Theory, ALT 2014


  • Fast rates
  • Generalization bounds
  • Local Rademacher complexity
  • Mixing
  • Stationary processes
  • Time series

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Generalization bounds for time series prediction with non-stationary processes'. Together they form a unique fingerprint.

Cite this