We derive an extension of McDiarmid’s inequality for functions f with bounded differences on a high probability set Y (instead of almost surely). The behavior of f outside Y may be arbitrary. The proof is short and elementary, and relies on an extension argument similar to Kirszbraun’s theorem [4].
While McDiarmid's inequality sometimes gives loose concentration bounds, its strength lies in its applicability (see @cite_7 for an extensive survey): sets @math may be completely arbitrary, and, even when @math is involved, it is usually easy to check that the bounded differences assumption holds. Two notable applications of McDiarmid's inequality are combinatorics and learning theory. Two representative results are the concentration of the chromatic number of Erd o s-R 'enyi graphs @cite_2 , and the fact that stable algorithms have good generalization performance @cite_11 . Namely, if the output of a learning algorithm does not vary too much when a training example is modified, then it performs well on an unseen, randomly selected, example.
@cite_11 @cite_7 @cite_2
2110630246 2082249316
We present a novel way of obtaining PAC-style bounds on the generalization error of learning algorithms, explicitly using their stability properties. A stable learner is one for which the learned solution does not change much with small changes in the training set. The bounds we obtain do not depend on any measure of the complexity of the hypothesis space (e.g. VC dimension) but rather depend on how the learning algorithm searches this space, and can thus be applied even when the VC dimension is infinite. We demonstrate that regularization networks possess the required stability property and apply our method to obtain new bounds on their generalization performance. For a fixed probabilityp, 0<p<1, almost every random graphGn,p has chromatic number @math ,