Coordinate descent

Definition

Coordinate descent refers to a method for optimization of a function of multiple variables where each iterative step involves optimization in a particular coordinate using some type of line search. The choice of coordinate changes from step to step.

Different coordinate descent algorithms differ in the following respects:

• The manner in which we choose the coordinate to optimize along at each stage. The simple version is cyclic coordinate descent, where we simply cycle through the coordinates in a predetermined order (and therefore return to the first coordinate after having completed a full cycle). In the case of adaptive coordinate descent algorithms, the choice of coordinate depends on information obtained during previous steps of execution of the algorithm.
• Parallelization: Parallel coordinate descent involves simultaneously moving in multiple coordinate directions. There are some perils of this approach.
• The method of line search used for the optimization along each coordinate in the coordinate descent.

Coordinate descent can be contrasted with gradient descent, where the direction of descent is carefully chosen based on first-order information about the function as a whole, as being along the gradient vector.

Coordinate descent is an example of hill-climbing optimization, a subclass of local search.