Covering number

Definition

Let (M, d) be a metric space, let K be a subset of M, and let r be a positive real number. Let B_r(x) denote the ball of radius r centered at x. A subset C of M is an r-external covering of K if:

In other words, for every y ∈ K there exists x ∈ C such that d ( x , y ) ≤ r .

If furthermore C is a subset of K, then it is an r-internal covering.

The external covering number of K, denoted N r ext ( K ) , is the minimum cardinality of any external covering of K. The internal covering number, denoted N r int ( K ) , is the minimum cardinality of any internal covering.

A subset P of K is a packing if P ⊆ K and the set { B r ( x ) } x ∈ P is pairwise disjoint. The packing number of K, denoted N r pack ( K ) , is the maximum cardinality of any packing of K.

A subset S of K is r-separated if each pair of points x and y in S satisfies d(x, y) ≥ r. The metric entropy of K, denoted N r met ( K ) , is the maximum cardinality of any r-separated subset of K.

Examples

1. The metric space is the real line R . K ⊂ R is a set of real numbers whose absolute value is at most k . Then, there is an external covering of ⌈ 2 k / r ⌉ intervals of length r , covering the interval [ k , − k ] . Hence:

2. The metric space is the Euclidean space R m with the Euclidean metric. K ⊂ R m is a set of vectors whose length (norm) is at most k . If K lies in a d-dimensional subspace of R m , then:

3. The metric space is the space of real-valued functions, with the l-infinity metric. The covering number N r int ( K ) is the smallest number k such that, there exist h 1 , … , h k ∈ K such that, for all h ∈ K there exists i ∈ { 1 , … , k } such that the supremum distance between h and h i is at most r . The above bound is not relevant since the space is ∞ -dimensional. However, when K is a compact set, every covering of it has a finite sub-covering, so N r int ( K ) is finite.

Properties

1. The internal and external covering numbers, the packing number, and the metric entropy are all closely related. The following chain of inequalities holds for any subset K of a metric space and any positive real number r.

2. Each function except the internal covering number is non-increasing in r and non-decreasing in K. The internal covering number is monotone in r but not necessarily in K.

The following properties relate to covering numbers in the standard Euclidean space R m :

3. If all vectors in K are translated by a constant vector k 0 ∈ R m , then the covering number does not change.

4. If all vectors in K are multiplied by a scalar k ∈ R , then:

5. If all vectors in K are operated by a Lipschitz function ϕ with Lipschitz constant k , then:

Application to machine learning

Let K be a space of real-valued functions, with the l-infinity metric (see example 3 above). Suppose all functions in K are bounded by a real constant M . Then, the covering number can be used to bound the generalization error of learning functions from K , relative to the squared loss: