(a) Determine the VC dimension of the set of all balls in R2. (b) Use Lemma 9.5 to derive an upper bound for the VC dimension of the set of all balls in Rd. Let A be a class of sets A ⊆ Rd. Show for...

(a) Determine the VC dimension of the set of all balls in R2.

(b) Use Lemma 9.5 to derive an upper bound for the VC dimension of the set of all balls in Rd.

Let A be a class of sets A ⊆ Rd. Show for any p ≥ 1, any z1,...,zn ∈ Rd, and any 0

                            Np (, {IA : A ∈ A} , zn 1 ) ≤ s (A, {z1,...,zn}) .

             Hint: Use  1 n n i=1 |g1(zi) − g2(zi)| p 1/p ≤ max i=1,...,n |g1(zi) − g2(zi)|.