When should one use Coordinate descent vs. gradient descent?

Question

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?

Answer 1

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. https://tibshirani.su.domains/comparison.txt.

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

Answer 2

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.

Answer 3

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.