Exercise 8.14

If we remove a data point $(x_n,y_n)$ with ${\alpha }_n^{\text{∗}}=0$, suppose the previous optimal solution is ${\alpha }^{\text{∗}}$.

(a)

Since ${\alpha }^{\text{∗}}$ is the optimal solution for the previous dual problem, It satisfies the constraints in (8.21). i.e. ${\alpha }_i\ge 0$ for $i=1,\dots ,N$. And

${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=1}^N{y}_i{\alpha }_i={\sum }_{i\ne n}^N{y}_i{\alpha }_i=0$ since ${\alpha }_n^{\text{∗}}=0$. The second part is exactly the new constraint for the problem with $(x_n,y_n)$ removed.

So the solution ${\alpha }^{\text{∗}}$ (after removing ${\alpha }_n^{\text{∗}}$) is feasible for the new dual problem.

(b)

If there’s another feasible solution (${\alpha }^{\prime }$) for the new dual and it has a lower objective value than ${\alpha }^{\text{∗}}$. We construct a new solution for previous dual problem by adding ${\alpha }_n^{\text{∗}}=0$ into ${\alpha }^{\prime }$, i.e. ${\alpha }^c$. It’s clear that ${\alpha }^c$ is a feasible solution for the previous dual problem.

From (8.21), the objective value of ${\alpha }^c$ for previous dual problem is thus:

$$\begin{array}{llll}\hfill V({\alpha }^c)& =\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{y}_i{y}_j{\alpha }_i^c{\alpha }_j^c{x}_i^T{x}_j-\sum _{i=1}^N{\alpha }_i^c& \hfill & \\ \hfill & =\frac{1}{2}\sum _{i\ne n}^N\sum _{j\ne n}^N{y}_i{y}_j{\alpha }_i^c{\alpha }_j^c{x}_i^T{x}_j-\sum _{i\ne n}^N{\alpha }_i^c& \hfill & \\ \hfill & <\frac{1}{2}\sum _{i\ne n}^N\sum _{j\ne n}^N{y}_i{y}_j{\alpha }_i^{\text{∗}}{\alpha }_j^{\text{∗}}{x}_i^T{x}_j-\sum _{i\ne n}^N{\alpha }_i^{\text{∗}}& \hfill & \\ \hfill & =V({\alpha }^{\text{∗}})& \hfill & \\ \hfill & & \hfill \end{array}$$

This contradicts the fact that ${\alpha }^{\text{∗}}$ is the optimal solution for the previous problem. So we conclude there’s no other feasible solution for the new dual problem that has a lower objective value than ${\alpha }^{\text{∗}}$.

(c)

Hence we showed that ${\alpha }^{\text{∗}}$ (minus ${\alpha }_n^{\text{∗}}$) is optimal for the new dual problem.

(d)

Since $w^{\text{∗}}={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=1}^N{y}_i{\alpha }_i^{\text{∗}}{x}_i={\sum }_{i\ne n}^N{y}_i{\alpha }_i^{\text{∗}}{x}_i$. $w^{\text{∗}}$ is the same as previous problem. Also $b^{\text{∗}}$ is computed using a point where ${\alpha }_s^{\text{∗}}>0$, it’s not affected by ${\alpha }_n^{\text{∗}}$ as well. So we conclude that the optimal hyperplane doesn’t change.

(e)

As the final hypothesis is not changed when we throw out any data point with ${\alpha }_n^{\text{∗}}=0$, after we throw out all such points, we are left with data points that have ${\alpha }_n^{\text{∗}}>0$, thus we shows that $E_{\mathit{CV}}=\frac{1}{N}{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{n=1}^N{e}_n\le \frac{\text{number of }{\alpha }_n^{\text{∗}}>0}{N}$.