Some Properties of Empirical Risk Minimization Over Donsker Classes

: We study properties of algorithms which minimize (or almost-minimise) 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 pi(exp -1/2).