Entropy and the combinatorial dimension

• 成果类型: Article
• 署名作者: Mendelson, S; Vershynin, R
• 署名单位: Australian National University; University of Alberta
• 刊物名称: INVENTIONES MATHEMATICAE
• ISSN/ISSBN: 0020-9910
• DOI: 10.1007/s00222-002-0266-3
• 发表日期: 2003
• 页码: 37-55
• 关键词: uniform-convergence; LIMIT-THEOREMS

摘要

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.