Skip navigation
Skip navigation

Local Complexities for Empirical Risk Minimization

Bartlett, Peter; Mendelson, Shahar; Philips, Petra


We present sharp bounds on the risk of the empirical minimization algorithm under mild assumptions on the class. We introduce the notion of isomorphic coordinate projections and show that this leads to a sharper error bound than the best previously known. The quantity which governs this bound on the empirical minimizer is the largest fixed point of the function ζn(r) = Esup{|Ef - Enf |f ε F, Ef = r}. We prove that this is the best estimate one can obtain using "structural results", and that it...[Show more]

CollectionsANU Research Publications
Date published: 2004
Type: Conference paper
Source: Proceedings of the 17th Annual Conference on Learning Theory (COLT 2004)


There are no files associated with this item.

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  23 August 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator