# Prove sum of slacks in SVM is an upper bound on the number of misclassified examples

How can we Prove that the sum of slacks $\sum \xi_n$ from the objective function of the SVM formulation with soft margin is an upper bound on the number of misclassified training examples?

Some references: https://www.cs.colostate.edu/~asa/pdfs/howto.pdf

My current knowledge: Optimization problem is
minimize w,b
1/2 $||w||^2$ + C $\sum \xi_i$

subject to $y_i (w^T x_i +b) \ge 1 - \xi_i, \xi_i \ge 0$

But it uses the problem taken for granted, I am looking how can we actually solve this.

• Do you understand why $\xi_i > 1$ if and only if the $i^{th}$ training example is misclassified? – jbowman Nov 27 '17 at 1:25
• @jbowman I know if an example is misclassified, then the slack variable $\xi_i$ is positive and we want to minimize total sum of slacks in SVM. – astro123 Nov 27 '17 at 1:28
• It's not just positive, it's > 1. The slack variables are always nonnegative. – jbowman Nov 27 '17 at 1:32

First, let's consider the case $y_i = 1$. In order to be classified correctly, $w^Tx_i + b > 0$, therefore $0 <y_i(w^Tx_i + b)$. In order for this number to be $\geq 1 - \xi_i$, $0 \leq \xi_i < 1$, with $\xi_i = 0$ when $y_i(w^Tx_i + b) \geq 1$.
Now let's assume the same classification occurred, so that $w^Tx_i + b > 0$, but incorrectly, i.e., $y_i = -1$. As $y_i < 0$, it must be that $y_i(w^Tx_i + b) < 0$. In order for this number to be $\geq 1 - \xi_i$, it must be that $\xi_i > 1$.
A similar logic can be worked through for the case where $w^Tx_i + b < 0$. In both cases, misclassification implies that $\xi > 1$.
Since $\xi_i > 1$ for all misclassified cases, it follows that $\Sigma_{i \in \text{misclassified}}\xi_i > \Sigma_{i \in \text{misclassified}}1$, which latter evidently equals the number of misclassified cases.
Since $\xi_i \geq 0$ for all correctly classified cases, it follows that $\Sigma_{i \in \text{correct}}\xi_i \geq 0$.