Two Symmetrized Coordinate Descent Methods Can Be $O(n^2)$ Times Slower Than the Randomized Version

Block decomposition algorithms decompose the variable vector into multiple blocks and update a single block with other blocks fixed at each iteration. In each epoch, the blocks are updated according to a certain update order. There are at least two classes of deterministic update orders: nonsymmetric and symmetric. A basic nonsymmetric update order is the cyclic order ($1, 2,\ldots, n$); i.e., the first, second, $\ldots,$ $n$th blocks are updated sequentially in each round. A typical symmetric update order is the symmetric Gauss--Seidel rule ($1, 2, \ldots, n-1, n, n-1, \ldots, 1$). Another example is the Gaussian back substitution rule which starts with the natural order ($1, 2, \ldots, n$) as a prediction step and is followed by a correction step. Recently, coordinate descent with cyclic order was shown to be $\mathcal{O}(n^2)$ times slower than randomized versions in the worst case. A natural question arises: can the symmetrized update orders achieve faster convergence rates than the cyclic order or even get close to the randomized versions? In this paper, we give a negative answer to this question. We show that both Gaussian back substitution and symmetric Gauss--Seidel orders suffer from the same slow convergence issue as the cyclic order in the worst case. In particular, we prove that for unconstrained problems, coordinate descent with these two symmetric update orders can be $\mathcal{O}(n^2)$ times slower than randomized coordinate descent. Besides unconstrained problems, we also empirically study linearly constrained problems with a quadratic objective: we empirically demonstrate that the convergence speed of alternating direction method of multipliers (ADMM) algorithms with these two update orders can be roughly $\mathcal{O}(n^2)$ times slower than randomly permuted ADMM on some problem instances.