On the stopping criterion of coordinate descent method

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

Consider the optimization problem $$\min f(\mathbf{x})$$ under the constraints $x_i\in C_i$ for $i=1,2,\ldots,m$ where $\mathbf{x}=(x_1,x_2,\ldots,x_m)$.

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 $y\in C_i$.

My question is, what is the stopping criterion of this algorithm if we want to 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? If it's too general then let's consider in particular the dual of linear SVM problem: $$\min f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^\top K \mathbf{x} - C\mathbf{1}^\top\mathbf{x},\quad \mbox{s.t. } 0\le x_i\le C \quad i=1,\ldots,m$$ where $K$ is a positive semi-definite matrix and $C$ is a positive constant.

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

• For a general $f$, not only that you can't figure the correct stopping criterion, it actually might not converge to the global optimum. What assumptions do you make on $f$? – R B Apr 9 '14 at 13:02
• Hi @RB. Let's consider only the objective function for linear SVM, that I stated above: $$\min f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^\top K \mathbf{x} - C\mathbf{1}^\top\mathbf{x},\quad \mbox{s.t. } 0\le x_i\le C \quad i=1,\ldots,m.$$ – Khue Apr 9 '14 at 14:10
• @elexhobby: Yes, it certainly does. However, my question is when the algorithm should stop to get an $\epsilon$-accurate solution (If we do not know the optimal value of course!) ;) – Khue Apr 9 '14 at 16:55
Here's one possible solution: $$\nabla f(x) = \left[ \frac{\partial f(x)}{\partial x_1} \cdots \frac{\partial f(x)}{\partial x_n}\right]^T$$ The coordinate descent algorithm is exploring all the coordinate axes, so you have an estimate of $\hat{\nabla} f_i(x_k)=\frac{\partial f(x^k)}{\partial x_i}$. In particular, when $\Big| \hat{\nabla} f_i(x_k) \Big| < \epsilon \,\forall i$, then $|\nabla f(x_k)| < n\epsilon$, so setting $\frac{\epsilon}{n}$ as the stopping criterion for the maximum slope along the coordinate axes is a reasonable strategy.