The metric entropy is equivalent to the combinatorial dimension under minimal regularity

Analysis 2 Minutes

You need to know: Logarithm, supremum.

Background: Let \Omega be a set, {\cal A} be the set of all functions f:\Omega \to {\mathbb R}, and let A be any subset of {\cal A}. For k points x_1, x_2, \dots, x_k \in \Omega and two functions f and g in {\cal A}, define d_{x_1,\dots x_k}(f,g)=\sqrt{\frac{1}{k}\sum\limits_{i=1}^k(f(x_i)-g(x_i))^2}. For any t>0, let N_{x_1,\dots x_k}(A,t) be the maximal n for which there exists functions f_1,f_2,\dots f_n \in A such that d_{x_1,\dots x_k}(f_i,f_j) \geq t for all i \neq j. The quantity D(A,t) := \log\left( \sup\limits_{k} \sup\limits_{x_1,\dots x_k} N_{x_1,\dots x_k}(A,t)\right) is called the Koltchinskii–Pollard entropy, or just metric entropy of A.

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 combinatorial dimension v(A,t) of A is the maximal cardinality of a set t-shattered by A.

The Theorem: On 26th January 2004, Mark Rudelson and Roman Vershynin submitted to the Annals of Mathematics a paper in which they proved that if there exists b>1 such that v(A,bt) \leq \frac{1}{2}v(A,t), \, \forall t>0, then inequalities c \cdot v(A, 2t) \leq D(A, t) \leq C \cdot v(A, ct) hold for all t > 0, where c > 0 is an absolute constant, and C depends only on b.

Short context: The condition v(A,bt) \leq \frac{1}{2}v(A,t), \, \forall t>0 in the Theorem is known as the minimal regularity condition, and it is known that the conclusion of the Theorem does not hold without it. The Theorem shows that, under this condition, two ways of measuring “how large the set of functions is” are equivalent, up to the constant factors.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 6.6 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment