Page 388 - Understanding Machine Learning

Technical Lemmas
370

Lemma A.4. Let X be a random variable and x ∈ R be a scalar and assume that
2

there exists a > 0 and b ≥ e such that for all t ≥ 0 we have P[|X − x | > t] ≤ 2be −t /a 2 .

Then, E[|X − x |] ≤ a(2 + log(b)).

Proof. For all i = 0,1,2,... denote t i = a (i + log(b)). Since t i is monotonically
increasing we have that
∞

E[|X − x |] ≤ a log(b) + t i P[|X − x | > t i−1 ].

i=1
Using the assumption in the lemma we have
∞ ∞ √
log(b)) 2
t i P[|X − x | > t i−1 ] ≤ 2ab (i + log(b))e −(i−1+

i=1 i=1
F
∞ 2
≤ 2ab √ xe −(x−1) dx
1+ log(b)
F
∞
−y 2
= 2ab √ (y + 1)e dy
log(b)
∞ 2
F
≤ 4ab √ ye −y dy
log(b)

2 ∞
= 2ab −e −y √
log(b)
= 2ab/b = 2a.
Combining the preceding inequalities we conclude our proof.

Lemma A.5. Let m,d be two positive integers such that d ≤ m − 2. Then,

d
m em d
≤ .
k d
k=0
Proof. We prove the claim by induction. For d = 1 the left-hand side equals 1 + m
while the right-hand side equals em; hence the claim is true. Assume that the claim
holds for d and let us prove it for d + 1. By the induction assumption we have

d+1
m em m
d
≤ +
k d d + 1
k=0

d
em d m(m − 1)(m − 2)···(m − d)
d
= 1 +
d em (d + 1)d!

d
em d (m − d)
d
≤ 1 + .
d e (d + 1)d!