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

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.

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