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
PublisherNeural Information Processing Systems
Pages1097-1104
Number of pages8
ISBN (Print)9781605609492
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
Country/TerritoryCanada
CityVancouver, BC
Period12/8/0812/11/08

ASJC Scopus subject areas

  • Information Systems

Fingerprint

Dive into the research topics of 'Rademacher complexity bounds for non-i.i.d. processes'. Together they form a unique fingerprint.

Cite this