4
$\begingroup$

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)$.


[Addendum - edited]

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\}$ ?

$\endgroup$

1 Answer 1

2
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.