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

Mehryar Mohri, Afshin Rostamizadeh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 21 - Proceedings of the 2008 Conference
Pages1097-1104
Number of pages8
StatePublished - 2009
Event22nd Annual Conference on Neural Information Processing Systems, NIPS 2008 - Vancouver, BC, Canada
Duration: Dec 8 2008Dec 11 2008

Publication series

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

Other

Other22nd Annual Conference on Neural Information Processing Systems, NIPS 2008
CountryCanada
CityVancouver, BC
Period12/8/0812/11/08

ASJC Scopus subject areas

  • Information Systems

Cite this