3
$\begingroup$

I knew about "Coordinate descent" and "Gradient descent" algorithms before; they are well-known and Wikipedia has articles for those. However I recently came across an algorithm called "Coordinate gradient descent".

How does this algorithm exactly work, and how does it relate to "Coordinate descent" and "Gradient descent"?

An example for usage of this term can be found on slide 7 at the link http://courses.cs.washington.edu/courses/cse546/12wi/slides/cse546wi12ClusteringEM.pdf. I think what K-means or EM does is "Coordinate gradient descent" (or "Coordinate gradient ascent", based on how you view the optimization), but I could not figure out the intuition behind the name.

$\endgroup$
1
$\begingroup$

The difference is that for Coordinate Descent, when you update a weight $w_i$, you update by setting the gradient of the function wrt $w_i$ to 0, then simply solving for $w_i^{new}$. If you have a convex differentiable function $F(\pmb{w})$, then updating $w_i$ attains a global minimum over the coordinate $w_i$ in a direction where all other points $w_j$ are held fixed. Once you've reached a point where $F(\pmb{w})$ is minimized along every coordinate and no further changes can be made, then you have reached a global minimum.

By contrast, with coordinate gradient descent (CGD), you basically follow gradient descent, but with respect to one weight. So an updated weight $w_i^{new}$ is defined at as $w_i^{new} = w_i^{old} - \eta u_i$, where $\eta$ is step size and $u_i$ is $\nabla F$ wrt $w_i$. The big difference is that you are not attaining a global minimum over the coordinate $w_i$ in a direction where all other points are held fixed (like in CD), but rather slowly descending in the direction of a global minimum of $F$, one point at a time. It's a step-wise version of gradient descent but doesn't converge at any faster rate.

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