Page 387 - Understanding Machine Learning

Appendix A

Technical Lemmas

Lemma A.1. Let a > 0. Then: x ≥ 2a log(a) ⇒ x ≥ a log(x). It follows that a
necessary condition for the inequality x < a log(x) to hold is that x < 2a log(a).
√
Proof. First note that for a ∈ (0, e] the inequality x ≥ a log(x) holds uncondition-
√
ally and therefore the claim is trivial. From now on, assume that a > e. Consider

the function f (x) = x − a log(x). The derivative is f (x) = 1 − a/x. Thus, for x > a
the derivative is positive and the function increases. In addition,
f (2a log(a)) = 2a log(a) − a log(2a log(a))
= 2a log(a) − a log(a) − a log(2log(a))
= a log(a) − a log(2log(a)).

Since a − 2log(a) > 0for all a > 0, the proof follows.
Lemma A.2. Let a ≥ 1 and b > 0. Then: x ≥ 4a log(2a) + 2b ⇒ x ≥ a log(x) + b.
Proof. It suffices to prove that x ≥ 4a log(2a) + 2b implies that both x ≥ 2a log(x)
and x ≥ 2b. Since we assume a ≥ 1 we clearly have that x ≥ 2b. In addition, since
b > 0 we have that x ≥ 4a log(2a) which using Lemma A.1 implies that x ≥ 2a log(x).
This concludes our proof.

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

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

E[|X − x |] ≤ 4a.
Proof. For all i = 0,1,2,... denote t i = ai.Since t i is monotonically increasing we

have that E[|X − x |] is at most ∞ t
i=1 i P[|X − x | > t i−1 ]. Combining this with the

∞ −(i−1) 2
assumption in the lemma we get that E[|X − x |] ≤ 2a ie . The proof

i=1
now follows from the inequalities
∞ 5 F
−(i−1) 2 −(i−1) 2 ∞ −(x−1) 2 −7
ie ≤ ie + xe dx < 1.8 + 10 < 2.
5
i=1 i=1
369