TY - GEN

T1 - Rademacher complexity bounds for non-i.i.d. processes

AU - Mohri, Mehryar

AU - Rostamizadeh, Afshin

PY - 2009

Y1 - 2009

N2 - This paper presents the first Rademacher complexity-based error bounds for noni. i.d. settings, a generalization of similar existing bounds derived for the i.i.d. case. Our bounds hold in the scenario of dependent samples generated by a stationary β-mixing process, which is commonly adopted in many previous studies of noni. i.d. settings. They benefit fromthe 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 such finite samples and lead to tighter generalization bounds. We also present the first margin bounds for kernel-based classification in this non-i.i.d. setting and briefly study their convergence.

AB - This paper presents the first Rademacher complexity-based error bounds for noni. i.d. settings, a generalization of similar existing bounds derived for the i.i.d. case. Our bounds hold in the scenario of dependent samples generated by a stationary β-mixing process, which is commonly adopted in many previous studies of noni. i.d. settings. They benefit fromthe 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 such finite samples and lead to tighter generalization bounds. We also present the first margin bounds for kernel-based classification in this non-i.i.d. setting and briefly study their convergence.

UR - http://www.scopus.com/inward/record.url?scp=84858764746&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84858764746&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84858764746

SN - 9781605609492

T3 - Advances in Neural Information Processing Systems 21 - Proceedings of the 2008 Conference

SP - 1097

EP - 1104

BT - Advances in Neural Information Processing Systems 21 - Proceedings of the 2008 Conference

T2 - 22nd Annual Conference on Neural Information Processing Systems, NIPS 2008

Y2 - 8 December 2008 through 11 December 2008

ER -