Page 245 - Understanding Machine Learning

19.6 Exercises 227

To conclude the proof of the lemma, you can rely on the following inequality
(without proving it): For every p ∈ [0,1/2] and k ≥ 10:
8
k

(1− 2 p) e −k p+ (log(2 p)+1) ≤ p.
2
k
19.3 Fix some p, p ∈ [0,1] and y ∈ {0,1}. Show that

P [ y = y ] ≤ P [ y = y ]+ |p − p |.

y∼p y∼p
19.4 Conclude the proof of the theorem according to the following steps:
As in the proof of Theorem 19.3, six some
> 0 and let C 1 ,...,C r be the cover

of the set X using boxes of length
. For each x,x in the same box we have

√ √

x− x ≤ d
. Otherwise, x− x ≤ 2 d. Show that
 

E[ L D ( h S )] ≤ E  P[C i ] 

S S
i:|C i ∩S|<k

√

+ max P h S (x) = y | ∀ j ∈ [k], x− x π j (x) ≤
d . (19.3)

i S,(x,y)

Bound the first summand using Lemma 19.6.

To bound the second summand, let us fix S| x and x such that all the k neighbors

√
of x in S| x areatdistanceof atmost
d from x. W.l.o.g assume that the k NN
1
are x 1 ,...,x k . Denote p i = η(x i )and let p = p i . Use Exercise 19.3 to show

k i
that
E P [h S (x) = y] ≤ E P [h S (x) = y]+|p − η(x)|.
y 1 ,...,y j y∼η(x) y 1 ,...,y j y∼p
W.l.o.g. assume that p ≤ 1/2. Now use Lemma 19.7 to show that

8
P P [h S (x) = y] ≤ 1+ P [1 [p>1/2] = y].
y 1 ,...,y j y∼p k y∼p
Show that
P [1 [p>1/2] = y] = p = min{p,1− p}≤ min{η(x),1− η(x)}+ |p − η(x)|.
y∼p
Combine all the preceding to obtain that the second summand in
Equation (19.3) is bounded by

8 √
1+ L D (h ) + 3c
d.
k
d
Use r = (2/
) to obtain that:

d
8 √ 2(2/
) k
E[L D (h S )] ≤ 1+ L D (h ) + 3c
d + .
S k m
Set
= 2m −1/(d+1) and use
√ √
−1/(d+1) 2k −1/(d+1) −1/(d+1)
6cm d + m ≤ 6c d + k m
e
to conclude the proof.