Entropy and the Combinatorial Dimension

Abstract

We solve Talagrand's entropy problem: The L2-covering numbers of every uniformly bounded class of functions are exponential in its shattering dimension. This extends Dudley's theorem on classes of {0, l}-valued functions, for which the shattering dimension is the Vapnik-Chervonenkis dimension. In convex geometry, the solution means that the entropy of a convex body K is controlled by the maximal dimension of a cube of a fixed side contained in the coordinate projections of K. This has a number of consequences, including the optimal Elton's Theorem and estimates on the uniform central limit theorem in the real valued case. Show more