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

3 Answers 3

9
$\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$
5
  • $\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, 2015 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, 2015 at 10:21
  • $\begingroup$ How come CD is faster than GD? It seems counter logic. $\endgroup$
    – Royi
    Jun 30, 2016 at 11:49
  • $\begingroup$ @Bar you can just increase coordinate descent's complexity when it fails to find new minimum by combining evaluation with other coordinates. This will increase number of test cases, but you don't have such conditions often in a hyperdimensional spaces like when training an ANN. An Ann with a few layers will have > 500 parameters, the probability of getting stuck is low and it will probably be at local minimum $\endgroup$
    – Nulik
    Apr 12, 2020 at 15:25
  • $\begingroup$ ista (the proximal gradient method) converges like $1/k$, not $1/k^2$, right? Accelerated proximal gradient methods such as FISTA converge like $1/k^2$. $\endgroup$
    – littleO
    Sep 9, 2020 at 6:26
9
$\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$
2
$\begingroup$

I realise that this is an old question and has some very good answers. I would like to share some practical personal experience.

When working with generative machine learning techniques, you are usually working with some sort of probabilities. An example may be the mixture probabilities of the $k$ components in a mixture model. They have the following constraints:

  • All probabilities must be positive.
  • All elements of the probability set must sum up to one

This is actually asking a lot. With gradient descent one usually deals with constraints via a penalty function. Here it will not work. As soon as a value violates one of these constraints, your code will typically raise a numerical error of sorts. So one has to deal with the constraints by never actually allowing the optimisation algorithm to traverse it.

There are numerous transformations that you can apply to your problem to satisfy the constraints in order to allows gradient descent. However, if you are looking for the easiest and most lazy way to implement this then coordinate descent is the way to go:

For each probability $p_i$:

  • $p_i^{k+1} = p_i^{k} - \eta \frac{\partial J}{\partial p_i}$
  • $p_i = \min(\max(p_i,0),1)$
  • Update all p_i: $\mathbf{P}^{j+1} = \mathbf{P}^j \cdot \frac{1}{\sum_{i=1}^n p_i} $

For someone like me that work in Python, this usually means that I have to use an additional for-loop which impacts performance quite negatively. Gradient descent allows me to use Numpy which is performance optimised. One can get very good speed with it, however, this is not achievable with coordinate descent so I usually use some transform technique.

So the conclusion really is that coordinate descent is the easiest option to deal with very strict constraints such as the rate parameter in the Poisson distribution. If its becomes negative, you code complains etc.

I hope this has added a bit of insight.

$\endgroup$
3
  • $\begingroup$ I don't understand this answer. I've never heard of coordinate descent dealing with probabilities, are you thinking of Bayesian learning? How could probabilities be negative? And what numerical errors are you talking about? I have never experienced this when training an ANN. $\endgroup$
    – Nulik
    Apr 12, 2020 at 17:16
  • 1
    $\begingroup$ @Nulik By 'probabilities', I believe the poster is referring to the 'weights' in mixture models. These weights are constrained to be positive, and have to sum to 1. For that reason, they are also referred to as probabilities. $\endgroup$
    – husB
    Aug 6, 2020 at 6:47
  • 1
    $\begingroup$ "This is actually asking a lot. With gradient descent one usually deals with constraints via a penalty function." We often deal with constraints by using the projected gradient method, which works well in the case that the optimization variables are constrained to belong to the probability simplex, because projecting onto the probability simplex is an operation that can be performed efficiently. $\endgroup$
    – littleO
    Sep 9, 2020 at 6:33

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.