Covering number

Not to be confused with Winding number or degree of a continuous mapping, sometimes called "covering number" or "engulfing number".

In mathematics, a covering number is the number of balls of a given size needed to completely cover a given space, with possible overlaps between the balls. The covering number quantifies the size of a set and can be applied to general metric spaces. Two related concepts are the packing number, the number of disjoint balls that fit in a space, and the metric entropy, the number of points that fit in a space when constrained to lie at some fixed minimum distance apart.

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:

$K\subseteq \bigcup _{x\in C}{B}_r(x)$.

In other words, for every $y\in K$ there exists $x\in C$ such that $d(x,y)\le 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^{\text{ext}}(K)$, is the minimum cardinality of any external covering of K. The internal covering number, denoted $N_r^{\text{int}}(K)$, is the minimum cardinality of any internal covering. A subset P of K is a packing if $P\subseteq K$ and the set $\{B_r(x){\}}_{x\in P}$ is pairwise disjoint. The packing number of K, denoted $N_r^{\text{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^{\text{met}}(K)$, is the maximum cardinality of any r-separated subset of K.

Examples

1. The metric space is the real line $\mathbb{ℝ}$. $K\subset \mathbb{ℝ}$ is a set of real numbers whose absolute value is at most $k$. Then, there is an external covering of $\lceil \frac{2k}{r}\rceil$ intervals of length $r$, covering the interval $[-k,k]$. Hence:

   $N_r^{\text{ext}}(K)\le \frac{2k}{r}$

2. The metric space is the Euclidean space ${\mathbb{ℝ}}^m$ with the Euclidean metric. $K\subset {\mathbb{ℝ}}^m$ is a set of vectors whose length (norm) is at most $k$. If $K$ lies in a d-dimensional subspace of ${\mathbb{ℝ}}^m$, then:
   $N_r^{\text{ext}}(K)\le {\left(\frac{2k\sqrt{d}}{r}\right)}^d$.
3. The metric space is the space of real-valued functions, with the l-infinity metric. The covering number $N_r^{\text{int}}(K)$ is the smallest number $k$ such that, there exist $h_1,\dots ,h_k\in K$ such that, for all $h\in K$ there exists $i\in \{1,\dots ,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 $\mathrm{\infty }$-dimensional. However, when $K$ is a compact set, every covering of it has a finite sub-covering, so $N_r^{\text{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.

   $N_{2r}^{\text{met}}(K)\le N_r^{\text{pack}}(K)\le N_r^{\text{ext}}(K)\le N_r^{\text{int}}(K)\le N_r^{\text{met}}(K)$

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, ${\mathbb{ℝ}}^m$:

3. If all vectors in $K$ are translated by a constant vector $k_0\in {\mathbb{ℝ}}^m$, then the covering number does not change.
4. If all vectors in $K$ are multiplied by a scalar $k\in \mathbb{ℝ}$, then:

   for all $r$: $N_{|k|\cdot r}^{\text{ext}}(k\cdot K)=N_r^{\text{ext}}(K)$

5. If all vectors in $K$ are operated by a Lipschitz function $\varphi$ with Lipschitz constant $k$, then:
   for all $r$: $N_{|k|\cdot r}^{\text{ext}}(\varphi \circ K)\le N_r^{\text{ext}}(K)$

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:

$\mathrm{Prob}\left[\underset{h\in K}{\sup }\right|\text{GeneralizationError}(h)-\text{EmpiricalError}(h)|\ge ϵ]\le N_r^{\text{int}}(K)2\exp \frac{-m{ϵ}^2}{2M^4}$

where $r=\frac{ϵ}{8M}$ and $m$ is the number of samples.

See also

• Polygon covering
• Kissing number