Entropy, dimension and the Elton-Pajor Theorem

Abstract

The Vapnik-Chervonenkis dimension of a set K in R^n is the maximal dimension of the coordinate cube of a given size, which can be found in coordinate projections of K. We show that the VC dimension of a convex body governs its entropy. This has a number of consequences, including the optimal Elton's theorem and a uniform central limit theorem in the real valued case.

References in corpus (1)

• Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions

Cited by in corpus (2)

• Random processes via the combinatorial dimension: introductory notes
• Integer cells in convex sets