A metric notion of dimension and its applications to learning

Let us define the dimension of a metric space as the minimum k>0 such that every ball in the metric space can be covered by 2^k balls of half the radius. This definition has several attractive feature