Return to search

Some Properties of Empirical Risk Minimization over Donsker Classes

We study properties of algorithms which minimize (or almost minimize) empirical error over a Donsker class of functions. We show that the L2-diameter of the set of almost-minimizers is converging to zero in probability. Therefore, as the number of samples grows, it is becoming unlikely that adding a point (or a number of points) to the training set will result in a large jump (in L2 distance) to a new hypothesis. We also show that under some conditions the expected errors of the almost-minimizers are becoming close with a rate faster than n^{-1/2}.

Identiferoai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/30545
Date17 May 2005
CreatorsCaponnetto, Andrea, Rakhlin, Alexander
Source SetsM.I.T. Theses and Dissertation
Languageen_US
Detected LanguageEnglish
Format9 p., 7033622 bytes, 434782 bytes, application/postscript, application/pdf
RelationMassachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory

Page generated in 0.0019 seconds