## Stability Properties of Empirical Risk Minimization over Donsker Classes

** Andrea Caponnetto, Alexander Rakhlin**; 7(91):2565−2583, 2006.

### Abstract

We study some stability properties of algorithms which minimize
(or almost-minimize) empirical error over Donsker classes of
functions. We show that, as the number *n* of samples grows, the
*L*_{2}-diameter of the set of almost-minimizers of empirical error
with tolerance *ξ*(*n*)=*o*(*n*^{-1/2})
converges to zero in
probability. Hence, even in the case of multiple minimizers of
expected error, as *n* increases it becomes less and less likely that
adding a sample (or a number of samples) to the training set will
result in a large jump to a new hypothesis. Moreover, under some
assumptions on the entropy of the class, along with an assumption
of Komlos-Major-Tusnady type, we derive a power rate of decay for
the diameter of almost-minimizers. This rate, through an
application of a uniform ratio limit inequality, is shown to
govern the closeness of the expected errors of the
almost-minimizers. In fact, under the above assumptions, the
expected errors of almost-minimizers become closer with a rate strictly
faster than *n*^{-1/2}.

© JMLR 2006. (edit, beta) |