Page 355 - Understanding Machine Learning

27

Covering Numbers

In this chapter we describe another way to measure the complexity of sets, which is
called covering numbers.

27.1 COVERING

Definition 27.1 (Covering). Let A ⊂ R m be a set of vectors. We say that A is r-

covered by a set A , with respect to the Euclidean metric, if for all a ∈ A there exists

a ∈ A with a −a ≤ r. We define by N(r, A) the cardinality of the smallest A that
r-covers A.
m
Example 27.1 (Subspace). Suppose that A ⊂ R ,let c = max a∈A a , and assume
√
d
m
that A lies in a d-dimensional subspace of R . Then, N(r, A) ≤ (2c d/r) .To see
this, let v 1 ,...,v d be an orthonormal basis of the subspace. Then, any a ∈ A can be
d

written as a = α i v i with α ∞ ≤√α 2 = a 2 ≤ c.Let
∈ R and consider the set
i=1
+
d

A = α v i : ∀i,α ∈{−c,−c +
,−c + 2
,...,c} .
i
i
i=1
d

α
Given a ∈ A s.t. a = i=1 i v i with α ∞ ≤ c, there exists a ∈ A such that

2 2 2 2 2
a − a = (α − α i )v i ≤
v i ≤
d.
i
i i
√
Choose
= r/ d;then a − a ≤ r and therefore A is an r-cover of A.Hence,

d
d √
2c 2c d

N(r, A) ≤|A |= = .

r
337