Solutions to

Understanding Machine Learning

by Shai Shalev-Shwartz and Shai Ben-David

Chapter 2 (A Gentle Start)

Zahra Taheri1
Feb 2020

Exercise 2.1
Let f be the labeling function. We want to show that given a training set S as follows

S = ((xi , f (xi )))m d m

i=1 ⊆ (R × {0, 1}) ,

there exists a polynomial pS such that hS (x) = 1 if and only if pS (x) ≥ 0, where hS : X → Y is the
following predictor:


 yi if ∃i ∈ [m] s. t. x = xi
hS (x) =
 0 otherwise

where [m] = {1, . . . , m} and yi = f (xi ), for all i ∈ [m].

Obviously, we have:

 1 if ∃i ∈ [m] s. t. x = xi and yi = 1
hS (x) =
 0 otherwise

It is easy to see that if yi = 0, for all i ∈ [m], then hS (x) = 0, for all x ∈ X . In this case, if
pS (x) := −1, for all x ∈ X , then the statement is obviously true.
Suppose that there exists an i in [m] such that yi = 1.
1. Let m = 1 and S = ((x1 , 1)). Then hS (x1 ) = 1 and hS (x) = 0, for all x ∈ X \ {x1 }. So we must
have pS (x1 ) ≥ 0 and pS (x) < 0, for all x ∈ X \ {x1 }. Let pS (x) := −∥x − x1 ∥2 . It is easy to see that
pS (x1 ) = 0 and pS (x) < 0, for all x ∈ X \ {x1 }.
2. Let m = 2. Then without loss of generality we may assume that S = ((x1 , 1), (x2 , 0)) or S =
((x1 , 1), (x2 , 1)).

1
[Link]
1
2

(1) If S = ((x1 , 1), (x2 , 0)), then hS (x1 ) = 1 and hS (x) = 0, for all x ∈ X \ {x1 }. So, similar to the
case (1), by defining pS (x) := −∥x − x1 ∥2 , the statement is obviously true.
(2) If S = ((x1 , 1), (x2 , 1)), then hS (x1 ) = hS (x2 ) = 1 and hS (x) = 0, for all x ∈ X \ {x1 , x2 }. So
we must have pS (x1 ) ≥ 0, pS (x2 ) ≥ 0 and pS (x) < 0, for all x ∈ X \ {x1 , x2 }. With a similar
discussion as above, let pS (x) := −(∥x − x1 ∥2 )(∥x − x1 ∥2 ). Then pS (x) is a polynomial such that
pS (x1 ) = pS (x2 ) = 0 and pS (x) < 0, for all x ∈ X \ {x1 , x2 }, and so the statement is obviously
true.

Inductively, we can generalize the obtained polynomials in cases (1) and (2) as follows:

Y
pS (x) := − ∥x − xi ∥2
i∈[m] yi =1

Then pS (x) is a polynomial such that pS (xi ) = 0, for all i ∈ [m] s. t. yi = 1, and pS (x) < 0, for all
x ∈ X \ {xi |i ∈ [m] and yi = 1}, and so the statement is obviously true.

Exercise 2.2
Let H be a class of binary classifiers over a domain X and D be a probability distribution over X . Let
f be the target hypothesis in H. Let S = ((xi , f (xi )))m
i=1 be a training set such that x1 , . . . , xm are
1 Pm
i.i.d with respect to D, denoted by S|X ∼ Dm . Fix some h ∈ H. Since LS (h) = m i=1 1h(xi )̸=f (xi ) , we

have:
m
∗ 1 X
ES|X ∼Dm [LS (h)] = Exi ∼D [1h(xi )̸=f (xi ) ]
m
i=1
m
∗∗ 1 X
= Ex∼D [1h(x)̸=f (x) ]
m
i=1
 
1
= m Px∼D [h(x) ̸= f (x)]
m
= L(D,f ) (h)

* Expectation is linear
** x1 , . . . , xm are i.i.d

Exercise 2.3
Let S = ((xi , yi ))m
i=1 be a training set.

1. Let R(S) be the rectangle returned by A and A(S) : X → Y be the corresponding hypothesis.
Since A returns the rectangle enclosing all positive examples in the training set, A(S)(xi ) = 1, for all
 Solutions to Understanding Machine Learning-Chapter 2 3

i ∈ [m] such that yi = 1. On the other hand, by the realizability assumption, there exists h∗ ∈ Hrec
2

such that LS (h∗ ) = 0, and so h∗ (xi ) = 1, for all i ∈ [m] such that yi = 1. Since A returns the smallest
rectangle enclosing all positive examples, LS (A(S)) = 0 and so A is an ERM.
2. Let D be a probability distribution over X . Also let R∗ = (a∗1 , b∗1 , a∗2 , b∗2 ) be the rectangle that
generates the labels and f be its corresponding hypothesis. Suppose that R1 , . . . , R4 are defined as in
the hint of this exercise.

Figure 1.

By the definitions of R(S) and R∗ we have R(S) ⊆ R∗ . Also we have,

/ S|X and f (x) = 1}) = D(R∗ \ R(S)).

L(D,f ) (A(S)) = D({x ∈ X : A(S)(x) ̸= f (x)}) = D({x ∈ X : x ∈

Since, the probability mass of the rectangle Ri is exactly 4ε , for all i ∈ {1, 2, 3, 4}, if S contains (positive)
examples in all of the rectangles R1 , . . . , R4 , then D(R∗ \R(S)) ≤ 4( 4ε ) = ε. Therefore, L(D,f ) (A(S)) ≤ ε.
Now, we would like to upper bound Dm ({S|X : L(D,f ) (hS ) > ε}). With the discussion above, if S
contains (positive) examples in all of the rectangles R1 , . . . , R4 , then L(D,f ) (A(S)) ≤ ε. Therefore,

4
[
{S|X : L(D,f ) (hS ) > ε} = {S|X : S|X ∩ Ri = ∅}.
i=1

ε
It is easy to see that Dm ({S|X : S|X ∩ Ri = ∅}) = (1 − 4ε )m ≤ e− 4 m , for all i ∈ {1, 2, 3, 4}. With the
ε ε
discussion above and the union bound, Dm ({S|X : L(D,f ) (hS ) > ε}) ≤ 4i=1 e− 4 m = 4e− 4 m . So, the
P

4 log(4/δ)
assumption m ≥ ε completes the proof.
4

3. Similar to the definition of axis aligned rectangles in R2 , given real numbers a1 ≤ b1 , . . . , ad ≤ bd ,

define the classifier h(a1 ,b1 ,...,ad ,bd ) as follows:

 1 if ai ≤ xi ≤ bi , for all i ∈ [d]
h(a1 ,b1 ,...,ad ,bd ) (x1 , . . . , xd ) =
 0 otherwise

Also, the class of all axis aligned rectangles in Rd is defined as follows:

d
Hrec = {h(a1 ,b1 ,...,ad ,bd ) : a1 ≤ b1 , . . . , ad ≤ bd }.

For i ∈ [2d], we define rectangles Ri similar to R1 , . . . , R4 in the latter case, with the probability mass
ε
2d . By generalizing the algorithm A to the case Rd , the proofs of parts (1) and (2) are straightforward
2d log(2d/δ)
(by considering a training set of size ≥ ε ).