22
$\begingroup$

I was wondering what the different use cases are for the two algorithms, Coordinate Descent and Gradient Descent.

I know that coordinate descent has problems with non-smooth functions but it is used in popular algorithms like SVM and LASSO.

Gradient descent however is I think used more widely, especially with the resurgence of ANNs, and for many other machine learning tasks.

My question is: What type of problems fit one but not the other, and in that respect what makes coordinate descent fitting for SVMs and LASSO, but gradient descent fitting for ANNs?

How should one choose between the two when choosing an optimization algorithm?

$\endgroup$
7
$\begingroup$

I think it usually is a matter of how simple/easy it is to work out the gradient of the smooth part of the function and/or the proximal operator of the penalty.

Sometimes, it is a lot more simple to find an exact solution of the problem in the case with one single variable (or a block or variables), than it is to work it out for all variables simultaneously. Othertimes it is just too expensive to compute the gradient compared to the individual derivatives. Also, the convergence of coordinate descent is the same as for ista, $1/k^2$, where $k$ is the number of iterations, but it may sometimes perform better compared to both ISTA and FISTA, see e.g. http://statweb.stanford.edu/~tibs/comparison.txt.

Such things will influence the choice of coordinate descent vs. ISTA/FISTA, for instance.

$\endgroup$
  • $\begingroup$ So which are the cases where coordinate descent (CD) will be faster? Are there some specific types of functions on which CD will be a better candidate? $\endgroup$ – Bar Apr 15 '15 at 9:18
  • $\begingroup$ I can't say that a specific class of functions will be faster with CD than with other methods, such as e.g. FISTA. As far as I know this depends heavily on your function, and how expensive it is to evaluate the gradient and things like that. From my experience, CD is faster than FISTA on the lasso problem when there are few variables in the model (don't remember, but less than some thousands). Note that I am only comparing CD to ISTA and FISTA here, other algorithms (such as Newton or Pseudo-Newton) will likely be way faster; but this depends entirely on the problem at hand. $\endgroup$ – Tommy L Apr 15 '15 at 10:21
  • $\begingroup$ How come CD is faster than GD? It seems counter logic. $\endgroup$ – Royi Jun 30 '16 at 11:49
2
$\begingroup$

Coordinate descent updates one parameter at a time, while gradient descent attempts to update all parameters at once.

It's hard to specify exactly when one algorithm will do better than the other. For example, I was very shocked to learn that coordinate descent was state of the art for LASSO. And I was not the only one; see slide 17.

With that said, there are some features that can make a problem more amendable to coordinate descent:

(1) Fast conditional updates. If, for some reason, the problem allows one to individually optimize parameters very quickly, coordinate descent can make use of this. For example, one may be able to update certain parameters using only a subset of the data, greatly reducing computational cost of these updates. Another case is if there is a closed form solution for an individual parameter, conditional on the values of all the other parameters.

(2) Relatively independent modes for parameters. If the optimal value of one parameter is completely independent of the other parameters values, then one round of coordinate descent will lead to the solution (assuming that each coordinate update finds the current mode). On the other hand, if the mode for a given parameter is very highly dependent on other parameter values, coordinate descent is very likely to inch along, with very small updates at each round.

Unfortunately, for most problems, (2) does not hold, so it is rare that coordinate descent does well compared alternative algorithms. I believe the reason it performs well for LASSO is that there are a lot of tricks one can use to enact condition (1).

For gradient descent, this algorithm will work well if the second derivative is relatively stable, a good $\alpha$ is selected and the off-diagonal of the Hessian is relatively small compared with the diagonal entries. These conditions are rare as well, so it generally performs worse than algorithms such as L-BFGS.

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