Entropy and the combinatorial dimension

S. Mendelson; R. Vershynin

doi:10.1007/s00222-002-0266-3

Entropy and the combinatorial dimension

S. Mendelson^*, R. Vershynin

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

70 Citations (Scopus)

Abstract

We solve Talagrand's entropy problem: The L₂-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.

Original language	English
Pages (from-to)	37-55
Number of pages	19
Journal	Inventiones Mathematicae
Volume	152
Issue number	1
DOIs	https://doi.org/10.1007/s00222-002-0266-3
Publication status	Published - 2003

Access to Document

10.1007/s00222-002-0266-3

Cite this

@article{f6bbb1f1f3fd4c8aae29f006d01e4b8e,

title = "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.",

author = "S. Mendelson and R. Vershynin",

year = "2003",

doi = "10.1007/s00222-002-0266-3",

language = "English",

volume = "152",

pages = "37--55",

journal = "Inventiones Mathematicae",

issn = "0020-9910",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Entropy and the combinatorial dimension

AU - Mendelson, S.

AU - Vershynin, R.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0037596458&partnerID=8YFLogxK

U2 - 10.1007/s00222-002-0266-3

DO - 10.1007/s00222-002-0266-3

M3 - Article

SN - 0020-9910

VL - 152

SP - 37

EP - 55

JO - Inventiones Mathematicae

JF - Inventiones Mathematicae

IS - 1

ER -

Entropy and the combinatorial dimension

Abstract

Access to Document

Other files and links

Fingerprint

Cite this