2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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$? $\endgroup$
    – R B
    Apr 9, 2014 at 13:02
  • $\begingroup$ 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.$$ $\endgroup$
    – f10w
    Apr 9, 2014 at 14:10
  • $\begingroup$ In that case, you have a convex function, and there is only one local=global minima, so coordinate descent should converge. $\endgroup$
    – elexhobby
    Apr 9, 2014 at 16:00
  • $\begingroup$ @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!) ;) $\endgroup$
    – f10w
    Apr 9, 2014 at 16:55
  • 2
    $\begingroup$ Crossposted on Cross Validated: stats.stackexchange.com/questions/92996/… $\endgroup$ Apr 9, 2014 at 20:28

1 Answer 1

2
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.