<p>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| &lt; \epsilon \,\forall i$, then $|\nabla f(x_k)| &lt; n\epsilon$, so setting $\frac{\epsilon}{n}$ as the stopping criterion for the maximum slope along the coordinate axes is a reasonable strategy.</p>

<p>(This gives you guarantees about the gradient and not the actual decrease, but I believe it can be modified because your function is a convex quadratic, not sure how off the top of my head)</p>

CC BY-SA 3.0
2014-04-09T19:26:09.783Z
2014-04-09T19:26:09.783Z
elexhobby
<p>I am trying to implement the coordinate descent method to solve the dual of linear SVM problem, but blocked at the stopping criterion.</p>

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

<p>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$.</p>

<p>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.</p>

<p>For the moment I take $f(\mathbf{x}^k) - f(\mathbf{x}^{k+1})&lt;\epsilon$ but $f(\mathbf{x}^k) - f(\mathbf{x}^{k+1})$ is only the lower bound of $f(\mathbf{x}^k) - f(\mathbf{x}^*)$.</p>

<p>Thank you in advance.</p>

CC BY-SA 3.0
2014-04-09T13:02:48.947Z
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
CC BY-SA 3.0
2014-04-09T14:10:12.080Z
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.$$
f10w
CC BY-SA 3.0
2014-04-09T16:00:21.560Z
In that case, you have a convex function, and there is only one local=global minima, so coordinate descent should converge.
elexhobby
CC BY-SA 3.0
2014-04-09T16:55:02.990Z
@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!) ;)
f10w
CC BY-SA 3.0
2014-04-09T20:28:10.673Z
Crossposted on [stats.se]: http://stats.stackexchange.com/questions/92996/on-the-stopping-criterion-of-coordinate-descent-method-for-linear-svm-with-ell
Suresh Venkat
<optimization><convex-optimization><primal-dual><svm>
On the stopping criterion of coordinate descent method
f10w
# On the stopping criterion of coordinate descent method

(Asked by: username_0 on 2014-04-08)

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
\begin{equation}
\min f(\mathbf{x})
\end{equation}
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}^\*)$.

Thank you in advance.

**Tags:** optimization, convex-optimization, primal-dual, svm
> **Comments:**
> **username_1**: 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$?  
> **username_0**: 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.$$  
> **username_2**: In that case, you have a convex function, and there is only one local=global minima, so coordinate descent should converge.  
> **username_0**: @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!) ;)  
> **username_3**: Crossposted on [stats.se]: http://stats.stackexchange.com/questions/92996/on-the-stopping-criterion-of-coordinate-descent-method-for-linear-svm-with-ell  

---

## 1 answers

### Answer by username_2 on 2014-04-09. Score: 2

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.

(This gives you guarantees about the gradient and not the actual decrease, but I believe it can be modified because your function is a convex quadratic, not sure how off the top of my head)


---

