Why bother with the dual problem when fitting SVM?

Question

Given the data points $x_1, \ldots, x_n \in \mathbb{R}^d$ and labels $y_1, \ldots, y_n \in \left \{-1, 1 \right\}$, the hard margin SVM primal problem is

$$ \text{minimize}_{w, w_0} \quad \frac{1}{2} w^T w $$ $$ \text{s.t.} \quad \forall i: y_i (w^T x_i + w_0) \ge 1$$

which is a quadratic program with $d+1$ variables to be optimized for and $i$ constraints. The dual

$$ \text{maximize}_{\alpha} \quad \sum_{i=1}^{n}{\alpha_i} - \frac{1}{2}\sum_{i=1}^{n}{\sum_{j=1}^{n}{y_i y_j \alpha_i \alpha_j x_i^T x_j}}$$ $$ \text{s.t.} \quad \forall i: \alpha_i \ge 0 \land \sum_{i=1}^{n}{y_i \alpha_i} = 0$$ is a quadratic program with $n + 1$ variables to be optimized for and $n$ inequality and $n$ equality constraints.

When implementing a hard margin SVM, why would I solve the dual problem instead of the primal problem? The primal problem looks more 'intuitive' to me, and I don't need to concern myself with the duality gap, the Kuhn-Tucker condition etc.

It would make sense to me to solve the dual problem if $d \gg n$, but I suspect there are better reasons. Is this the case?

Answer 1

Based on the lecture notes referenced in @user765195's answer (thanks!), the most apparent reasons seem to be:

Solving the primal problem, we obtain the optimal $w$, but know nothing about the $\alpha_i$. In order to classify a query point $x$ we need to explicitly compute the scalar product $w^Tx$, which may be expensive if $d$ is large.

Solving the dual problem, we obtain the $\alpha_i$ (where $\alpha_i = 0$ for all but a few points - the support vectors). In order to classify a query point $x$, we calculate

$$ w^Tx + w_0 = \left(\sum_{i=1}^{n}{\alpha_i y_i x_i} \right)^T x + w_0 = \sum_{i=1}^{n}{\alpha_i y_i \langle x_i, x \rangle} + w_0 $$

This term is very efficiently calculated if there are only few support vectors. Further, since we now have a scalar product only involving data vectors, we may apply the kernel trick.

Answer 2

Read the second paragraph in page 13 and the discussion proceeding it in these notes:

Tengyu Ma and Andrew Ng. Part V: Kernel Methods. CS229 Lecture Notes. 2020 October 7.

Answer 3

Here's one reason why the dual formulation is attractive from a numerical optimization point of view. You can find the details in the following paper:

Hsieh, C.-J., Chang, K.-W., Lin, C.-J., Keerthi, S. S., and Sundararajan, S., “A Dual coordinate descent method forlarge-scale linear SVM”, Proceedings of the 25th International Conference on Machine Learning, Helsinki, 2008.

The dual formulation involves a single affine equality constraint and n bound constraints.

1. The affine equality constraint can be "eliminated" from the dual formulation.

This can be done by simply looking at your data in $R^{d+1}$ via the embedding of $R^d$ in $R^{d+1}$ resuling from adding a single "$1$" coordinate to each data point, i.e. $R^d \to R^{d+1}: (a_1,..., a_d) \mapsto (a_1, ..., a_d, 1)$.

Doing this for all points in the training set recasts the linear separability problem in $R^{d+1}$ and eliminates the constant term $w_0$ from your classifier, which in turn eliminates the affine equality constraint from the dual.

2. By point 1, the dual can be easily cast as a convex quadratic optimization problem whose constraints are only bound constraints.

3. The dual problem can now be solved efficiently, i.e. via a dual coordinate descent algorithm that yields an epsilon-optimal solution in $O(\log(\frac{1}{\varepsilon}))$.

This is done by noting that fixing all alphas except one yields a closed-form solution. You can then cycle through all alphas one by one (e.g. choosing one at random, fixing all other alphas, calculating the closed form solution). One can show that you'll thus obtain a near-optimal solution "rather quickly" (see Theorem 1 in the aforementioned paper).

There are many other reasons why the dual problem is attractive from an optimization point of view, some of which exploit the fact that it has only one affine equality constraint (the remaing constraints are all bound constraints) while others exploit the observation that at the solution of the dual problem "often most alphas" are zero (non-zero alphas corresponding to support vectors).

You can get a good overview of numerical optimization considerations for SVMs from Stephen Wright's presentation at the Computational Learning Workshop (2009).

P.S.: I'm new here. Apologies for not being good at using mathematical notation on this website.

Answer 4

In my opinion, the prediction time argument (that predictions from the dual solution are faster than from the primal solution) is nonsense. A comparison makes only sense if you use a linear kernel in the first place, because otherwise you cannot make predictions with the primal (or at least it is not clear to me how that would work). But if you have a linear kernel, then computing the kernel is the dot product and is strictly slower for the dual than for the primal, because you need to compute it for at least 2 (and typically much more points). It would then be much faster to rely on the simply dot product $\mathbf w^Tx$. In fact, if you have a linear kernel, you would just compute $\mathbf w$ explicitly and use it for predictions, just as you would do with the primal solution.

The two true arguments are:

1. The kernel trick can be applied (already mentioned by others)

2. The optimization process is much more straight forward for the dual problem and can be easily done with gradient descent

I will shed some light on the second point, since little has been said about that.

The main problem with the primal problem is that it cannot be easily optimized using standard gradient descent in spite of its convexity. You can easily detect this if you try to implement a solution to both problems (primal and dual) with a gradient-descent approach. Btw. the dual you formulated also has an issued, but this can be resolved as said below.

There are in fact three annoying things about optimizing the primal, at least when trying to solve it using gradient descent:

1. there is no trivial valid initial solution. In fact, already an initial solution must be a perfect separator. You can find one with the perceptron algorithm. In the dual, you can initialize all the $\alpha_i := 0$, which is also common practice. It is noteworthy that this corresponds to setting $w = 0$, which is not a feasible solution to the primal. However, in the dual this is not a problem, because only the optimal solution needs to be feasible in the primal.

2. the standard gradient update rule $\mathbf w' \leftarrow \mathbf w + \eta \nabla$ does not make a lot of sense and will not help you to converge to the optimum even though the problem is convex. The issue is that the gradient $\nabla$ is $\mathbf w$ itself, so you would in fact only shorten or stretch $\mathbf w$ but not change its orientation. But the latter is typically necessary unless your initial solution already had the correct slope.

3. the threshold $w_0$ does not occur in the objective function and its gradient is 0, but it should be updated in accordance with changes in $\mathbf w$.

Putting all this together, my personal reason to not optimize the primal is that, even though it is convex, there is no straight forward way of doing this with gradient descent. Note that this issue is not prevalent in the soft margin classifier, because here you can initialize $\mathbf w = 0$ and also have more sensible gradient steps. The problem is simply that it is annoying to deal with the linear constraints.

The dual problem as posed by you also is annoying when being solved with GD, because you still have the balance constraint $\sum y_i\alpha_i = 0$. You can get rid of that when adding the $\mathbf 1$ column to the data and treating it as part of $\mathbf w$. If you do that, you do not have the condition on optimality anymore for the Lagrangian, and optimization can be easily and efficiently done with simple batch gradient descent.