2005/08/16 by Peter L. Bartlett, Olivier Bousquet, Shahar Mendelson · 2 citations
Mathematics · #math.ST #stat.TH #msc:62G08 #msc:68Q32
paper · pdf · doi:10.1214/009053605000000282
published as Annals of Statistics 2005, Vol. 33, No. 4, 1497-1537 · Published at http://dx.doi.org/10.1214/009053605000000282 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
arxiv created 2005/08/16 · arxiv updated 2009/12/01
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.