Rademacher Complexity Bounds for Non-I.I.D. Processes

This paper presents the first data-dependent generalization bounds for non-i. i. d. settings based on the notion of Rademacher complexity. Our bounds extend to the non-i. i. d. case existing Rademacher complexity bounds derived for the i. i. d. setting. These bounds provide a strict generalization of the ones found in the i. i. d. case, and can also be used within the standard i. i. d. scenario. They apply to the standard scenario of beta-mixing stationary sequences examined in many previous studies of non-i. i. d. settings and benefit form the crucial advantages of Rademacher complexity over other measures of the complexity of hypothesis classes. In particular, they are data-dependent and measure the complexity of a class of hypotheses based on the training sample. The empirical Rademacher complexity can be estimated from finite samples and lead to tighter bounds.

Authors

• Mehryar Mohri
• Afshin Rostamizadeh

Keywords

No keywords are indexed for this paper.