Timezone: »

Rademacher Complexity Bounds for Non-I.I.D. Processes
Mehryar Mohri · Afshin Rostamizadeh

Mon Dec 08 08:45 PM -- 12:00 AM (PST) @ None #None

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.

Author Information

Mehryar Mohri (Courant Inst. of Math. Sciences & Google Research)
Afshin Rostamizadeh (Google Research)

More from the Same Authors