Timezone: »

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

Mon Dec 08 08:45 PM -- 12:00 AM (PST) @
in Posters »

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.

[ PDF] 

Author Information

Mehryar Mohri (Google Research & Courant Institute of Mathematical Sciences)
Afshin Rostamizadeh (Google Research)

More from the Same Authors