Stability Bounds for Stationary φ-mixing and β-mixing Processes

By Mehryar Mohri, Afshin Rostamizadeh. 2008

166 citations recorded by the source corpus.

Most generalization bounds in learning theory are based on some measure of the complexity of the hypothesis class used, independently of any algorithm. In contrast, the notion of algorithmic stability can be used to derive tight generalization bounds that are tailored to specific learning algorithms by exploiting their particular properties. However, as in much of learning theory, existing stability analyses and bounds apply only in the scenario where the samples are independently and identically distributed. In many machine learning applications, however, this assumption does not hold. The observations received by the learning algorithm often have some inherent temporal dependence. This paper studies the scenario where the observations are drawn from a stationary φ-mixing or β-mixing sequence, a widely adopted assumption in the study of non-i.i.d. processes that implies a dependence between observations weakening over time. We prove novel and distinct stability-based generalization bounds for stationary φ-mixing and β-mixing sequences. These bounds strictly generalize the bounds given in the i.i.d. case and apply to all stable learning algorithms, thereby extending the use of stability-bounds to non-i.i.d. scenarios. We also illustrate the application of our φ-mixing generalization bounds to general classes of learning algorithms, including Support Vector Regression, Kernel Ridge Regression, and Support Vector Machines, and many other kernel regularization-based and relative entropy-based regularization algorithms. These novel bounds can thus be viewed as the first theoretical basis for the use of these algorithms in non-i.i.d. scenarios.

Subfields: Control and Systems Engineering, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Control and Systems Engineering

In Statistics and Probability

Citations in the corpus

Security analysis of online centroid anomaly detection (2010, background): “data (Steinwart et al., 2009; Mohri and Rostamizadeh, 2010) or differing training and test distributions (Sugiyama et al.”
Time series prediction and online learning (2016, background): “In Section 3.3, we show that, under a mild assumption, the discrepancy term can be accurately estimated from data.”
Collective Stability in Structured Prediction: Generalization from One Example (2013, background): “Like (Mohri & Rostamizadeh, 2010, Theorem 8), Theorem 1 achieves a slight improvement over the original by using a general form of McDiarmid’s inequality instead of Azuma’s inequality.”
Stability and Generalization in Structured Prediction (2016, methodology): “Similarly, Mohri and Rostamizadeh (2009, 2010) derived risk bounds for φ-mixing and β-mixing temporal data, using an “independent blocking” technique due to Yu (1994).”
ETSformer: Exponential Smoothing Transformers for Time-series Forecasting (2022, background): “(1) Firstly, time-series data is usually assumed to be generated by a conditional distribution over past observations, with the dependence between observations weakening over time [17, 23].”
Regularization in reinforcement learning (2011, background): “Mohri and Rostamizadeh [2010] consider a stability-based analysis.”
Transfer Learning via Learning to Transfer (2018, methodology): “By generalizing S to be meta-samples S and h S to be L2T L ( S ) , we apply Corollary 21 in (Mohri & Rostamizadeh, 2010) to give the generalization bound of our algorithm L ( S ) in Theorem 2.”
Iterative Value-Aware Model Learning (2018, background): “One can then provide statistical guarantees for learning algorithms under various mixing conditions [Yu, 1994, Meir, 2000, Steinwart and Christmann, 2009, Mohri and Rostamizadeh, 2009, 2010, Farahmand and Szepesvári, 2012].”
PAC-Bayesian Collective Stability (2014, methodology): “For φ-mixing and β-mixing temporal data, Mohri and Rostamizadeh (2009, 2010) derived risk bounds using an independent blocking technique, due to Yu (1994), though the hypotheses they consider predict each time step independently.”