arXiv:math/0203275 Abstract

arXiv:math/0203275 [math.FA]Abstract References Reviews Resources

Entropy and the Combinatorial Dimension

Published 2002-03-26, updated 2002-09-25Version 3

We solve Talagrand's entropy problem: the L_2-covering numbers of every uniformly bounded class of functions are exponential in its shattering dimension. This extends Dudley's theorem on classes of {0,1}-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.

Comments: A final version of the paper (Inventiones Math., to appear) Only two applications added: one to Asymptotic Geometry (the optimal Elton Theorem) and the other to empirical processes (the uniform central limit theorem)

DOI: 10.1007/s00222-002-0266-3

Categories: math.FA

Keywords: combinatorial dimension, uniform central limit theorem, talagrands entropy problem, shattering dimension, extends dudleys theorem

Tags: journal article

Related articles: Most relevant | Search more

arXiv:math/0404192 [math.FA] (Published 2004-04-08)

Combinatorics of random processes and sections of convex bodies

Mark Rudelson, Roman Vershynin

arXiv:math/0404193 [math.FA] (Published 2004-04-08)

Random processes via the combinatorial dimension: introductory notes

Mark Rudelson, Roman Vershynin

arXiv:math/0201048 [math.FA] (Published 2002-01-07)