Local Rademacher complexities

Peter L. Bartlett, Olivier Bousquet, Shahar Mendelson

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…