Rademacher averages and phase transitions in Glivenko-Cantelli classes

The best known estimates on the covering numbers of a class when considered as a subset of L/sub p/ spaces are proved and the fat-shattering dimension of the convex hull of a given class is estimated.

Abstract

We introduce a new parameter which may replace the fat-shattering dimension. Using this parameter we are able to provide improved complexity estimates for the agnostic learning problem with respect to any L/sub p/ norm. Moreover, we show that if fat/sub /spl epsi//(F) = O(/spl epsi//sup -p/) then F displays a clear phase transition which occurs at p=2. The phase transition appears in the sample complexity estimates, covering numbers estimates, and in the growth rate of the Rademacher averages associated with the class. As a part of our discussion, we prove the best known estimates on the covering numbers of a class when considered as a subset of L/sub p/ spaces. We also estimate the fat-shattering dimension of the convex hull of a given class. Both these estimates are given in terms of the fat-shattering dimension of the original class.