Exercise 8.7

(a) Assume we have ${\rho }_1<{\rho }_2$, consider the corresponding hypothesis sets $H_{{\rho }_1}$ and $H_{{\rho }_2}$. For a given data set $(x_1,y_1),\dots ,(x_N,y_N)$, for any given dichotomy on the data set, if the dichotomy can be implemented by a hypothesis $h_2\in H_{{\rho }_2}$, then there must be a hypothesis $h_1\in H_{{\rho }_1}$ that can implement the dichotomy as well.

This is because we can choose the $(b_2,w_2)$ from $h_2$, since ${\rho }_2=\frac{1}{\left|w_2\right|}$, if we set $(b_1,w_1)=\frac{{\rho }_2}{{\rho }_1}(b_2,w_2)$ such that $\left|w_1\right|=\frac{1}{{\rho }_1}$, so $h_1=(b_1,w_1)$ belongs to $H_{{\rho }_1}$ and has a margin of ${\rho }_1$.

As the margin of $h_1$ is smaller than the margin of $h_2$ (${\rho }_1<{\rho }_2$), if $h_2$ can implement the dichotomy, $h_1$ certainly can do that too. The reverse is not necessarily true since if we add points (Assuming adding the proper signs on the two sides of $h_1$) that are in the margin of $h_2$ but outside the margin of $h_1$, $h_2$ won’t be able to implement the new dichotomy while $h_1$ can still do.

So we see that $d_{VC}(\rho )$ is non-increasing in $\rho$.

(b) We first prove that for any 3 points in the unit disc, there must be two that are within distance $\sqrt{3}$ of each other. If this is not ture, then there exists 3 points in the unit disc, such that the distances between any two points are larger than $\sqrt{3}$.

The center of the disc can’t be one of such 3 points, because the distance from center to any point is less than or equal to 1. Now we draw lines from the center to 3 points and extend them to meet with the boundary of the disc. We check the lengths of the segments (formed by connecting the 3 points on the circle), they must be all larger than $\sqrt{3}$.

We can compute the angle that each segment corresponds to, e.g. $\cos <!--\; FUNCTION\; APPLICATION\; -->(𝜃)=\frac{a^2+b^2-c^2}{2\mathit{ab}}$, where $a=b=1$ and $c$ is the segment, $𝜃$ is the corresponding angle. We have $\cos <!--\; FUNCTION\; APPLICATION\; -->(𝜃)=1-\frac{c^2}{2}<-0.5$, we conclude that $𝜃>\frac{2\pi }{3}$. This is true for all three angles, so we have a total angle of larger than $3\times \frac{2\pi }{3}=2\pi$, which contradicts.

So for any 3 points in the unit disc, there must be two that are within distance of $\sqrt{3}$ of each other.

Suppose that when $\rho >\frac{\sqrt{3}}{2}$, $d_{VC}(\rho )\ge 3$, that is the $H_{\rho }$ can shatter at least 3 points.

Now consider any 3 points in the unit disc, from what we have proved, there must be two that are within distance of $\sqrt{3}$ of each other. Consider the dichotomy when the two points is one positive, one negative, any hypothesis hyperplane (a line) that can implement this dichotomy needs to cross with the line between the two points. We see that of the two distances from the two points to the hyperplane, there is at least one that is in the margin, i.e. less than $\rho$. The distances are equal when the line is passing through the middle and perpendicular to the line between the two points. And the distances there are both $\frac{\sqrt{3}}{2}$, which is smaller than $\rho$, meaning at least one point will always stay in the margin of any hyperplane that can implement the dichotomy.

This contradicts with the assumption that the hypothesis set $H_{\rho }$ can shatter any 3 points. Thus $d_{VC}(\rho )<3$ when $\rho >\frac{\sqrt{3}}{2}$