The covering number of a uniformly bounded set of functions is exponential in its shattering dimension

Analysis 1 Minute

You need to know: Probabilty measure \mu on set \Omega, norm L_2(\mu) for functions on \Omega.

Background: Let \Omega be a set, and let \mu be a probability measure on \Omega. Let B_1 be the set of all functions f:\Omega \to [-1,1], and let A be any subset of B_1. Denote N(A,t,\mu) the covering number of A, that is, the minimal number of functions whose linear combination can approximate any function in A within an error t in the L_2(\mu) norm.

We say that a subset \sigma of \Omega is t-shattered by A if there exists a function h on \sigma such that, given any decomposition \sigma=\sigma_1 \cup \sigma_2 with \sigma_1 \cap \sigma_2 = \emptyset, one can find a function f \in A with f(x) \leq h(x) if x \in \sigma_1 but f(x) \geq h(x) + t if x \in \sigma_2. The shattering (or combinatorial) dimension vc(A,t) of A is the maximal cardinality of a set t-shattered by A.

The Theorem: On 10th December 2001, Shahar Mendelson and Roman Vershynin submitted to Inventiones Mathematicae a paper in which they proved that N(A, t,\mu) \leq \left(\frac{2}{t}\right)^{K \cdot vc(A,ct)}, \, 0<t<1, where K and c are positive absolute constants.

Short context: It is well-known that the covering numbers of a set are exponential in its linear algebraic dimension. The Theorem extends this result to shattering dimension, solving so-called Talagrand’s entropy problem. This result is especially useful because shattering dimension never exceeds linear algebraic dimension, and is often much smaller than it.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment