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...
| Main Authors: | , |
|---|---|
| Language: | en_US |
| Published: |
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/30545 |
| Summary: | 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}. |
|---|