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
PB - Neural Information Processing Systems
T2 - 22nd Annual Conference on Neural Information Processing Systems, NIPS 2008
Y2 - 8 December 2008 through 11 December 2008
ER -