7

In Hastie's Elements of Statistical Learning the dual problem is put as

$$ \begin{align} \text{arg min}_\alpha \quad &\ \frac{1}{2}\alpha^\top Q\, \alpha_i- \sum_i \alpha_i\\ \text{subject to}\quad &\ \forall i:0\le\alpha_i\le C\\ &\ \sum_i y_i \alpha_i = 0 \end{align} $$

I implemented a dual coordinate descent method based on Hsieh et al.'s A Dual Coordinate Descent Method for Large-scale Linear SVM but they state that the dual problem is

$$ \begin{align} \text{arg min}_\alpha \quad &\ \frac{1}{2}\alpha^\top Q\, \alpha_i- \sum_i \alpha_i\\ \text{subject to}\quad &\ \forall i:0\le\alpha_i\le C \end{align} $$

In other words, they dropped the second constraint. I ran the implementation and indeed the constraint is not met after the algorithm finishes. Note that LIBLINEAR uses the same approach with the constraint $\sum_i y_i \alpha_i = 0$ dropped.

It doesn't seem legit to me to simply drop constraints, so why are some authors doing it?

appletree
  • 167
  • 4
  • First notice that the constraint in the first formulation comes from setting the derivative w.r.t $\beta_0$ to zero (I'm using Hastie's book notation). Now see Eq. (3) in the paper that you cite. – echzhen Oct 23 '17 at 12:26
  • So to answer shortly, the matrix $Q$ in the first formulation is different from the matrix $Q$ in the second formulation. Actually $Q_2 = Q_1 + yy^{\top}$, where $y = (y_1, \ldots, y_l)^{\top}$. – echzhen Oct 23 '17 at 12:38
  • Not sure whether I understand. The literal formulation in Hastie (p.420, Eq 12.13) is $L_D = \sum_i \alpha_i - 1/2 \sum_i\sum_{i'} \alpha_i \alpha_{i'} y_i y_{i'} x_i x_{i'}^\top$, so in my first equation $Q_{ij} = y_i y_j x_i^\top x_j$, which is identical to the formulation in the Hsieh paper. – appletree Oct 23 '17 at 15:36
  • OK I seem to have missed this post dealing with the same question: https://stats.stackexchange.com/questions/246404/linear-constraint-in-svm-optimization?rq=1 – appletree Oct 23 '17 at 15:46

0 Answers0