2.4 Non-concentric circles. Let X = R2 and consider the set of concepts of the form c = fx 2 R2 : jjx ???? x0jj  rg for some point x0 2 R2 and real number r. Gertrude, an aspiring machine learning researcher, attempts to show that this class of concepts may be (; )-PAC-learned with sample complexity m 

(3=) log(3=), but she is having trouble with her proof. Her idea is that the learning algorithm would select the smallest circle consistent with the training data. She has drawn three regions r1; r2; r3 around the edge of concept

c, with each region having probability =3 (see gure 2.5(a)). She wants to argue that if the generalization error is greater than or equal to , then one of these regions must have been missed by the training data, and hence this event will occur with probability at most . Can you tell Gertrude if her approach works? (Hint: You may wish to use gure 2.5

(b) in your solution).