Stability Bound for Stationary Phi-mixing and Beta-mixing Processes

Details Stability Bound for Stationary Phi-mixing and Beta-mixing Processes Stability Bound for Stationary Phi-mixing and Beta-mixing Processes

2008-11-11

arxiv.org/abs/0811.1629v1

Computer Science

Learning

23 pages, 1 figure, submitted to JMLR

Scientific paper

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 phi-mixing or beta-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 phi-mixing and beta-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 phi-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.

Affiliated with

Also associated with

No associations

Rating

Stability Bound for Stationary Phi-mixing and Beta-mixing Processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Stability Bound for Stationary Phi-mixing and Beta-mixing Processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stability Bound for Stationary Phi-mixing and Beta-mixing Processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-543178