Support Vector Machines (SVMs) are very elegant classical machine learning models before the era of deep learning. I still remember when I came to SVM during my PhD study, I always felt confused but excited as well, since it inspired and drove me to explore more. After several years’ research in classical machine learning and optimization, I decide to write a blog regarding vanilla SVM and its variant.

Binary SVM

We first revisit the standard SVM problem. Let $\lbrace(\mathbf{x}_i,y_i)\rbrace$ be a binary classification dataset with $\mathbf{x}_i\in\mathbb{R}^d$ and $y_i\in\lbrace-1,+1\rbrace$.

Primal Formulation

Classical (L1-) SVM aims to find a linear classifier that maximizes the margin while penalizing hinge-loss errors:

Here, $\mathbf{w}\in\mathbb{R}^d$ is the weight vector, $b\in\mathbb{R}$ is the bias term, $\xi_i$ are slack variables, and $C>0$ is a regularization parameter controlling the trade-off between the margin size and the hinge-loss penalty.

One can see that this is a standard Quadratic Programming (QP) problem, existing solvers are readily applicable such as quadprog in Matlab. However, when the sample/feature size ($n/d$) is large, total variables to be optimized ($d+n+1$) is large, which makes QP not practical.

Dual Formulation

A more often seen perspective to find optimal $\vw$ is from the dual perspective, which says directly optimizing $\vw$ can be difficult, but it can be recovered by another variable and the new variable’s optimization is rather easy or at least easier.

I know many beginners will get lost by the above sentences. For illustration, I have the following examples:

Example 1

Essentially, this is to project $\vy$ into a polyhedron defined by $\am\vx\le\vb$.

Directly solving $\vx$ is not easy and a standard strategy is to introduce the Lagrangian:

where $\lambda$ is a positive vector. Duality theory says since the original objective is convex, while the inequality constraint is affine, therefore strong duality holds. Then it is same as

Apparently, for any $\lambda$, optimal $\vx=\vy-\am^\top\lambda$. It then boils down to solve:

which is same as

The above optimization problem is readily solvable by projected gradient descent where $\lambda$ is itereatedly updated via

After iterations, one can obtain optimal $\lambda$ and by KKT we can recover original optimal $\vx=\vy-\am^\top\lambda$.

Example 2

which is essentially probability simplex projection. We associate a Lagrangian $\lambda$ (scalar here) to the equality constraint:

Given the nonnegative constraint on $\vx$, one can obtain $\vx=\max\lbrace \vy-\lambda,0\rbrace=[\vy-\lambda]_+$. The dual problem becomes:

By taking the derivative w.r.t. $\lambda$ (for equality constraint, there is no constraint on Lagrangian multiplier), we have:

Apparently, function

is monotonically nonincreasing w.r.t. $\lambda$. In fact, one can veify

while

which suggests one can utilize bisection to find the unique root $\lambda$. After that, we can again recover optimal $\vx=\max\lbrace \vy-\lambda,0\rbrace$.

Dual of SVM

Now let’s go back to optimize SVM from the dual perspective, by following the general process of Lagrangian, it turns to optimize:

where $\mathcal{K}(i,j)=y_iy_j\langle \phi(\vx_i),\phi(\vx_j)\rangle$, which is a natural extension to inner product to measure similarity between point $\vx_i$ and $\vx_j$. One can also verify that matrix $\mathcal{K}$ is symmetric PSD.

For convenience, we write the equivalent dual formulation as

while the constraint remains same.

One can verify the above dual problem is another QP, however, now the number of variables to be optimized reduces to $n$, which can be significantly faster than primal QP when $d$ is rather large. This is another reason why dual perspective of SVM is attractive.

Unlike methods whose convergence rates follow directly from standard coordinate-descent or proximal-gradient theory, the rate analysis of SMO is more involved because its updates are determined by a working-set selection strategy and must preserve the dual equality constraint.

In addition, different from the previous two (toy) examples, I found that by simply introducing Lagrangian, it is not straitforward to obtain solution $\alpha^*$.

The above are what inspire me to propose something new I want to share as below.

Dual on Dual

By noticing the convexity of objective in the above, in addition to the fact that constraint is also convex, we use the standard projected-gradient step. At each iteration, the projected-gradient update reduces to the following projection problem:

where

Now it turns to almost same as Example 2 above, and by introducing Lagrangian $\lambda$, one can obtain $\alpha=\min\lbrace C, \max\lbrace \beta-\lambda\vy,0\rbrace\rbrace$. Therefore optimal $\lambda$ should satisfy equality constraint which is

One can see the left handside is monotonically decreasing w.r.t. $\lambda$ for either $y_i=1$ or $y_i=-1$ case, thus it can be solved via bisection efficiently. After obtaining $\lambda^*$, we recover

L2-SVM

Analogously, the L2-SVM problem can be formulated as

Unlike L1-SVM, the nonnegativity constraint on $\xi_i$ can be removed. Indeed, if $\xi_i<0$, then replacing it with $\xi_i=0$ would both reduce the objective value and preserve feasibility of the inequality constraint.

By introducing Lagrange multipliers, the dual problem becomes

By making use of similar trick in L1-SVM section, by introducing Lagrangian in proximal gradient descent step, it boils down to find unique root satisfying:

Of course, here $\beta$ is slightly different from the one in L1-SVM. One can even use Nesterove Acceleration which emperically demonstrates significant faster performance. We summarize the whole process without acceleration as below:

Algorithm: Proposed Method for Solving the Dual Problem of L2-SVM or L1-SVM

Require: Given $C$ and $\lbrace(\mathbf{x}_i,y_i)\rbrace$, formulate $\mathcal{K}$ according to specific kernel and set

for L2-SVM, or

for L1-SVM, and initialize

Ensure: An approximate solution $\boldsymbol{\alpha}$ to the corresponding dual problem.

While not converged:

1. Compute

   \[\boldsymbol{\beta} \gets \boldsymbol{\alpha} - \frac{1}{L} \left( \mathcal{K}\boldsymbol{\alpha} + \frac{\boldsymbol{\alpha}}{C} - \boldsymbol{1} \right)\]

   for L2-SVM, or

   \[\boldsymbol{\beta} \gets \boldsymbol{\alpha} - \frac{1}{L} \left( \mathcal{K}\boldsymbol{\alpha} - \boldsymbol{1} \right)\]

   for L1-SVM.

2. Find $\lambda$ via bisection such that

   \[\sum_{i=1}^n y_i[\beta_i-\lambda y_i]_+ = 0\]

   for L2-SVM, or

   \[\sum_{i=1}^n y_i \min \left\{ C, \max \left\{ \beta_i-\lambda y_i, 0 \right\} \right\} = 0\]

   for L1-SVM.

3. Update

   \[\boldsymbol{\alpha} \gets [\boldsymbol{\beta}-\lambda\boldsymbol{y}]_+\]

   for L2-SVM, or

   \[\boldsymbol{\alpha} \gets \min \left\{ C, \max \left\{ \boldsymbol{\beta}-\lambda\boldsymbol{y}, 0 \right\} \right\}\]

   for L1-SVM.

I plan to add more applications of the proposed idea Dual on Dual to SVMs’ siblings in later seperate blogs.

References

[1] John Platt. “Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines.” MSR-TR-98-14, April 1998.

[2] Amir Beck. “Introduction to nonlinear optimization”.