# SVM optimality criterion in Bottou, Lin (2006)

My question relates to an alternative optimality criterion for an SVM dual solution derived in Bottou, Lin (2006) in pages 8 and 9.

Let:

• $\alpha^* = (\alpha_1^*,\dots,\alpha_n^*)$ be a dual solution to the SVM. Recall that any solution $\alpha^*$ must satisfy: $\forall i \in \{1,...,n\}, 0 \leq \alpha_i^* \leq C$;
• $g_i^*$ the derivative of the dual objective function $\mathcal{D}$ with respect to $\alpha_i^*$;
• $B_i$ equal to $C \times 1_{\{y_i=1\}}$ and $A_i$ equal to $-C \times 1_{\{y_i=-1\}}$ such that $\forall i \in \{1,...,n\},\; y_i\alpha_i \in [A_i,B_i]$ $-$ i.e. $[A_i,B_i]$ might be equal to $[0,C]$ or $[-C,0]$;
• $I_{up} = \{i:y_i\alpha_i < B_i\}$ $-$ i.e. $\alpha_i < C$ or $\alpha_i < 0$;
• $I_{down} = \{j:y_j\alpha_j > A_j\}$ $-$ i.e. $\alpha_j > 0$ or $\alpha_j > -C$.

Then Bottou and Lin's necessary and sufficient optimality criterion $-$ let call it $\mathcal{O}_{SVM}(\alpha^*)$ $-$ is:

$$\exists \: \rho \in \mathbb{R} : \max_{i \, \in \, I_{up}} y_ig_i^* \leq \rho \leq \min_{j \, \in \, I_{down}} y_jg_j^*$$

I understand how $\alpha^*$ being a solution implies $\mathcal{O}_{SVM}(\alpha^*)$ $-$ it is shown in the paper $-$ however I am not sure how $\mathcal{O}_{SVM}(\alpha^*)$ implies $\alpha^*$ is a solution.

Does anybody know a reference where the reciprocal is proved? If not, could someone shed more light on this? As noted, details can be found in the above link in pages 8 and 9; the criterion corresponds to equation $(1.11)$.

My issue relates primarily to $\varepsilon$ $-$ see paper: the inequality $\mathcal{D}(\alpha^{\varepsilon}) \leq \mathcal{D}(\alpha^*)$ should hold for all $\alpha^{\varepsilon}$ for $\alpha^*$ to be an optimum, however $\varepsilon$ should be sufficiently small for $\alpha^{\varepsilon}$ to satisfy its constraints, hence the inequality does not hold for all $\alpha^{\varepsilon}$, does it? Except if we are implicitly restricting ourselves to the feasible region by considering only the following set of epsilons: $S_{\varepsilon} = \{\varepsilon:\forall i \in \{1,\dots,n\}, \alpha^{\varepsilon} = (\alpha_1^{\varepsilon},\dots,\alpha_n^{\varepsilon}), 0\leq\alpha_i^{\varepsilon}\leq C\}$ ?

If we can find $\mathbf{\alpha^*}$ and $(\mathbf{w^*}, b^*, \mathbf{\xi^*})$ such that the optimality criterion holds:

$$\exists \: \rho \in \mathbb{R} : \max_{i \, \in \, I_{up}} y_ig_i^* \leq \rho \leq \min_{j \, \in \, I_{down}} y_jg_j^*$$ with $I_{up} = \{i \; | \; y_i\alpha_i < B_i\}$ and $I_{down} = \{j \; | \; y_j \alpha_j > A_j \}$

then we have:

$$\exists \: \rho \in \mathbb{R} \; \forall k, \left\{ \begin{array} \\ \text{if} \;\; g_k^* \; > \; y_k \rho \;\;\; \text{then} \;\;\; \alpha_k^* = C \\ \text{if} \;\; g_k^* \; < \; y_k \rho \;\;\; \text{then} \;\;\; \alpha_k^* = 0 \end{array} \right\}$$

Using this we can prove that (PROOF 1 at the end): $$C \xi_k^* - \alpha_k^* g_k^* = -y_k\alpha_k^*\rho$$

And since we know that

$$\mathcal{P}(\mathbf{w}^*, b^*, \mathbf{\xi}^*) - \mathcal{D}(\mathbf{\alpha}^*) = \sum_{k=1}^{n} (C \xi_k^* - \alpha_k^* g_k^*)$$

we get:

$$\begin{split} \mathcal{P}(\mathbf{w}^*, b^*, \mathbf{\xi}^*) - \mathcal{D}(\mathbf{\alpha}^*) & = \sum_{k=1}^n (-y_k \alpha_k^* \rho) \\ & = -\rho \sum_{i=1}^n y_i \alpha_i^* \\ & = -\rho·0 \\ & = 0 \end{split}$$

According to the $\textit{strong duality}$, if we can find $\mathbf{\alpha^*}$ and $(\mathbf{w^*}, b^*, \mathbf{\xi^*})$ such that $\mathcal{D}(\mathbf{\alpha^*}) = \mathcal{P}(\mathbf{w^*}, b^*, \mathbf{\xi^*})$, then $(\mathbf{w^*}, b^*, \mathbf{\xi^*})$ and $\mathbf{\alpha^*}$ are solutions of the primal and dual problems.

PROOF 1:

Either $g_k^* > y_k \rho \;\;$ or $\;\;g_k^* < y_k \rho$, we prove that in both cases: $\;\;C \xi_k^* - \alpha_k^* g_k^* = - y_k \alpha_k^* \rho$.

If $g_k^* > y_k \rho$:

$C = \alpha_k^* \;\;\;$ and $\;\;\; \xi_k^* = max\{0, g_k^* - y_k \rho\} = g_k^* - y_k \rho$

Thus

\begin{align} C \xi_k^* - \alpha_k^* g_k^* & = C \;\; max\{0, g_k^* - y_k \rho\} - \alpha_k^* g_k^* \\ & = \alpha_k^* \; (g_k^* - y_k \rho) - \alpha_k^* g_k^* \\ & = - y_k \alpha_k^* \rho \end{align}

If $g_k^* < y_k \rho$:

$\alpha_k^* = 0 \;\;\;$ and $\;\;\; \xi_k^* = max\{0, g_k^* - y_k \rho\} = 0$

Thus

$$C \xi_k^* - \alpha_k^* g_k^* = - y_k \alpha_k^* \rho = 0$$