On the stopping criterion of coordinate descent method for linear SVM with $\ell_1$-regularization

Question

I am trying to implement the coordinate descent method to solve the dual of linear SVM problem, but blocked at the stopping criterion.

The dual of linear SVM problem is: $$\min f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^\top K \mathbf{x} - \mathbf{1}^\top\mathbf{x},\quad \mbox{s.t. } 0\le x_i\le C \quad i=1,\ldots,m$$ where $C$ is a positive constant and the matrix $K$ has the elements $K_{ij}=y_iy_jx_i^\top x_j$ where $y_i\in\{-1,1\}$ are the labels and $x_i\in\mathbb{R}^n$ are the data.

At iteration $k$ we perform $m$ inner iterations where the $i$-th inner iteration updates $x_i$ by solving: $$x_i^{k+1} = \arg\min_{y} f(x_1^{k+1},x_2^{k+1},\ldots,x_{i-1}^{k+1},y,x_{i+1}^{k},\ldots,x_{m}^{k})$$ under the constraint $0\le y\le C$.

My question is, what is the stopping criterion of this algorithm if we want to

1. Obtain an $\epsilon$-accurate solution $\mathbf{x}$, i.e. $f(\mathbf{x}) - f(\mathbf{x}^*) \le \epsilon$ where $\mathbf{x}^*$ is the true optimal solution? For the moment I take $f(\mathbf{x}^k) - f(\mathbf{x}^{k+1})<\epsilon$ but $f(\mathbf{x}^k) - f(\mathbf{x}^{k+1})$ is only the lower bound of $f(\mathbf{x}^k) - f(\mathbf{x}^*)$.
2. Obtain an $\epsilon$-accurate duality gap? Update: for this problem, strong duality holds, thus an $\epsilon$-accurate solution yields an $\epsilon$-accurate duality gap.

Thank you in advance.

Answer 1

There are alternative ways to check for optimality of the solution which are derived from the strong duality property. It is described in great detail in the paper Support Vector Machine Solvers.

Concretely, libsvm uses the following step criterion, $$ \text{max}_{up} y_{i}g_{i} - \text{min}_{down} y_{i}g_{i} \le \epsilon $$ where $g_{i} = 1-y_{i}x_{i}K_{ij}$ and $up$ and $down$ are defined as $$ up = \left\{ i | y_{i}x_{i} < C \text{ if } y_{i} = 1 \text{ or } < 0 \text{ if } y_{i} = -1 \right\} $$ $$ down = \left\{ i | y_{i}x_{i} > 0 \text{ if } y_{i} = 1 \text{ or } > -C \text{ if } y_{i} = -1 \right\} $$

The paper provides a description of common techniques together with some implementation issues. I guess you will find it very helpful.

Answer 2

I think you never really know the true optimal solution, only that with respect to your training data. The metrics given are then actually relatively easy to calculate:

1. Keep a cache of the loss (for an SVM, $\max(1-y_i <w \cdot x_i>_\mathcal{H},0)$ for all $i$) on your training data and average this loss, this gives you an estimate of the current $\epsilon$-accuracy.
2. Have you read "An introduction to support vector machines and other kenrel-based learning methods" by Cristianini and Shawe-Taylor? It contains a lot of interesting information with respect to optimization and tricks like monitoring the duality gap. Should you still want to calculate this explicitly, it suffices to monitor the difference between the primal and the Lagrangian (both of which are easy to calculate on the training data as in point $1$).