Local rademacher complexities

Peter L. Bartlett; Olivier Bousquet; Shahar Mendelson

doi:10.1214/009053605000000282

Local rademacher complexities

Peter L. Bartlett^*, Olivier Bousquet, Shahar Mendelson

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

535 Citations (Scopus)

Abstract

We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical version of Rademacher averages, in the sense that the Rademacher averages are computed from the data, on a subset of functions with small empirical error. We present some applications to classification and prediction with convex function classes, and with kernel classes in particular.

Original language	English
Pages (from-to)	1497-1537
Number of pages	41
Journal	Annals of Statistics
Volume	33
Issue number	4
DOIs	https://doi.org/10.1214/009053605000000282
Publication status	Published - Aug 2005

Access to Document

10.1214/009053605000000282

Cite this

@article{b1240ced84074e0791fa5d23624049dc,

title = "Local rademacher complexities",

abstract = "We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical version of Rademacher averages, in the sense that the Rademacher averages are computed from the data, on a subset of functions with small empirical error. We present some applications to classification and prediction with convex function classes, and with kernel classes in particular.",

keywords = "Concentration inequalities, Data-dependent complexity, Error bounds, Rademacher averages",

author = "Bartlett, {Peter L.} and Olivier Bousquet and Shahar Mendelson",

year = "2005",

month = aug,

doi = "10.1214/009053605000000282",

language = "English",

volume = "33",

pages = "1497--1537",

journal = "Annals of Statistics",

issn = "0090-5364",

publisher = "Institute of Mathematical Statistics",

number = "4",

}

TY - JOUR

T1 - Local rademacher complexities

AU - Bartlett, Peter L.

AU - Bousquet, Olivier

AU - Mendelson, Shahar

PY - 2005/8

Y1 - 2005/8

N2 - We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical version of Rademacher averages, in the sense that the Rademacher averages are computed from the data, on a subset of functions with small empirical error. We present some applications to classification and prediction with convex function classes, and with kernel classes in particular.

AB - We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical version of Rademacher averages, in the sense that the Rademacher averages are computed from the data, on a subset of functions with small empirical error. We present some applications to classification and prediction with convex function classes, and with kernel classes in particular.

KW - Concentration inequalities

KW - Data-dependent complexity

KW - Error bounds

KW - Rademacher averages

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

U2 - 10.1214/009053605000000282

DO - 10.1214/009053605000000282

M3 - Article

SN - 0090-5364

VL - 33

SP - 1497

EP - 1537

JO - Annals of Statistics

JF - Annals of Statistics

IS - 4

ER -

Local rademacher complexities

Abstract

Access to Document

Other files and links

Fingerprint

Cite this