Local Rademacher complexities

• 成果类型: Article
• 署名作者: Bartlett, PL; Bousquet, O; Mendelson, S
• 署名单位: University of California System; University of California Berkeley; University of California System; University of California Berkeley; Max Planck Society; Australian National University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/009053605000000282
• 发表日期: 2005
• 页码: 1497-1537
• 关键词: Concentration Inequalities; MODEL

摘要

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.