Rademacher and Gaussian complexities: Risk bounds and structural results

We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and Gaussian complexities. In a decision theoretic setting, we prove general risk bounds in terms of these complexities. W e consider function classes that can be expressed as combinat...

Full description

Saved in:
Bibliographic Details
Published in:Journal of machine learning research 2003-04, Vol.3 (3), p.463-482
Main Authors: Bartlett, P L, Mendelson, S
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and Gaussian complexities. In a decision theoretic setting, we prove general risk bounds in terms of these complexities. W e consider function classes that can be expressed as combinations of functions from basis classes and show how the Rademacher and Gaussian complexities of such a function class can be bounded in terms of the complexity of the basis classes. We give examples of the application of these techniques in finding data-dependent risk bounds for decision trees, neural networks and support vector machines.
ISSN:1532-4435
DOI:10.1162/153244303321897690