Understanding Machine Learning: From Theory to Algorithms

420 Technical Lemmas

Proof For alli= 0, 1 , 2 ,...denoteti=a(i+

√

log(b)). Sincetiis monotonically

increasing we have that

E[|X−x′|]≤a

√

log(b) +

∑∞

i=1

tiP[|X−x′|> ti− 1 ].

Using the assumption in the lemma we have

∑∞

i=1

tiP[|X−x′|> ti− 1 ]≤ 2 ab

∑∞

i=1

(i+

√

log(b))e−(i−1+

√

log(b))^2

≤ 2 ab

∫∞

1+

√

log(b)

xe−(x−1)

2

dx

= 2ab

∫∞

√

log(b)

(y+ 1)e−y

2

dy

≤ 4 ab

∫∞

√

log(b)

ye−y

2

dy

= 2ab

[

−e−y

2 ]∞

√

log(b)

= 2ab/b= 2a.

Combining the preceding inequalities we conclude our proof.

lemmaA.5 Letm,dbe two positive integers such thatd≤m− 2. Then,

∑d

k=0

(

m

k

)

≤

(em

d

)d

.

Proof We prove the claim by induction. Ford= 1 the left-hand side equals

1 +mwhile the right-hand side equalsem; hence the claim is true. Assume that

the claim holds fordand let us prove it ford+ 1. By the induction assumption

we have

∑d+1

k=0

(

m

k

)

≤

(em

d

)d

+

(

m

d+ 1

)

=

(em

d

)d(

1 +

(

d

em

)d

m(m−1)(m−2)···(m−d)

(d+ 1)d!

)

≤

(em

d

)d(

1 +

(

d

e

)d

(m−d)

(d+ 1)d!

)

.