  Variants of the coordinate descent approach for minimizing a nonlinear
function are distinguished in part by the order in which coordinates are
considered for relaxation. Three common orderings are cyclic (CCD), in which we
cycle through the components of $x$ in order; randomized (RCD), in which the
component to update is selected randomly and independently at each iteration;
and random-permutations cyclic (RPCD), which differs from CCD only in that a
random permutation is applied to the variables at the start of each cycle.
Known convergence guarantees are weaker for CCD and RPCD than for RCD, though
in most practical cases, computational performance is similar among all these
variants. There is a certain type of quadratic function for which CCD is
significantly slower than for RCD; a recent paper by \cite{SunY16a} has
explored the poor behavior of CCD on functions of this type. The RPCD approach
performs well on these functions, even better than RCD in a certain regime.
This paper explains the good behavior of RPCD with a tight analysis.

Optimization and Control