Entropy and the combinatorial dimension

By Shahar Mendelson, Roman Vershynin. 2002

131 citations recorded by the source corpus.

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

Subfields: Applied Mathematics, Numerical Analysis, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/a84e6bd66c57634a452e6e240bc56f7b602a8dfb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Numerical Analysis

In Statistics and Probability

Citations in the corpus

Sequential complexities and uniform martingale laws of large numbers (2015, background): “For the classical case of a cover based on a set points, the discretization idea appears in [3, 19].”
VC bounds on the cardinality of nearly orthogonal function classes (2010, background): “further wish to understand the relationship between M(ε,d) and n for ﬁxed ε and d. It is well known [18] that when γ = 1 − 2ε = O(1/ √ n), we have M(ε,d) = O(poly(n)). Since in many cases of interest [14] the coordinate dimension n may be replaced by its reﬁnement d VC, it is natural to ask whether ”
A Few Notes on Statistical Learning Theory (2002, background): “One can show ([ 24 ]) that given a measure ¹ and a target T 6∈ nup(G, ¹ ), the 2-loss class L satisfies that Eµf 2 ≤ BEµf for every f ∈ L. The constant B will depend”
Bridging Theory and Algorithm for Domain Adaptation (2019, background): “To answer this we need the notion of fat-shattering dimension (Mendelson & Vershynin, 2003; Rakhlin & Sridharan, 2014).”
On combining machine learning with decision making (2011, background): “sion for f0;1g-valued function classes, -fat shattering dimension for real valued functions, Rademacher complexity, and certain kinds of covering numbers (Vapnik, 1998; Bartlett and Mendelson, 2002; Mendelson and Vershynin, 2003; Zhang, 2002; Shawe-Taylor and Cristianini, 2002; Kolmogorov and Tikhom”
Theory of classification : a survey of some recent advances (2005, background): “A few key references include Vapnik and Chervonenkis [232] [234], Dudley [79] [81] [82], Talagrand [211] [212] [214] [218], Dudley, Giné, and Zinn [84], Alon, Ben-David, Cesa-Bianchi, and Haussler [8], Li, Long, and Srinivasan [138], Mendelson and Vershynin [173].”