Skip to main content
Open Access Publications from the University of California

Local complexities for empirical risk minimization

  • Author(s): Bartlett, Peter L
  • Mendelson, Shahar
  • Philips, Petra
  • et al.

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 xi(n)(r) = E sup {Ef - E(n)f : f is an element of F, Ef = r}. We prove that this is the best estimate one can obtain using "structural results", and that it is possible to estimate the error rate from data. We then prove that the bound on the empirical minimization algorithm can be improved further by a direct analysis, and that the correct error rate is the maximizer of xi'(n)(r) - r, where xi'(n)(r) = E sup {Ef - E(n)f : f is an element of F, Ef = r}.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View