When Cyclic Coordinate Descent Outperforms Randomized Coordinate Descent
The coordinate descent (CD) method is a classical optimization algorithm that has seen a revival of interest because of its competitive performance in machine learning applications. A number of recent papers provided convergence rate estimates for their deterministic (cyclic) and randomized variants that differ in the selection of update coordinates. These estimates suggest randomized coordinate descent (RCD) performs better than cyclic coordinate descent (CCD), although numerical experiments do not provide clear justification for this comparison. In this paper, we provide examples and more generally problem classes for which CCD (or CD with any deterministic order) is faster than RCD in terms of asymptotic worst-case convergence. Furthermore, we provide lower and upper bounds on the amount of improvement on the rate of CCD relative to RCD, which depends on the deterministic order used. We also provide a characterization of the best deterministic order (that leads to the maximum improvement in convergence rate) in terms of the combinatorial properties of the Hessian matrix of the objective function.
In this paper, the authors analyze cyclic and randomized coordinate descent and show that despite the common assumption in the literature, cyclic CD can actually be much faster than randomized CD. The authors show that this is true for quadratic objectives when A is of a certain type (e.g., symmetric positive definite with diagonal entries of 1, irreducible M-matrix, A is consistently ordered, 2-cyclic matrix). 
Comments:
- There are more than 2 variants of CD selection rules: greedy selection is a very valid selection strategy for structured ML problems (see "Coordinate Descent Converges Faster with the Gauss-Southwell Rule than Random Selection, ICML 2015 by Nutini et. al.)
- The authors state that it is common perception that randomized CD always dominates cyclic CD. I don't agree with this statement. For example, if your matrix is diagonal, cyclic CD will clearly do better than randomized CD.
- The authors make several assumptions on the matrices considered in their analysis (e.g., M-matrix, 2-cyclic). It is not obvious to me that these matrices are common in machine learning applications when solving a quadratic problem. I think the authors need to do a better job at convincing the reader that these matrices are important in ML applications, e.g., precision matrix estimation https://arxiv.org/pdf/1404.6640.pdf "Estimation of positive definite M-matrices and structure learning for attractive Gaussian Markov Random fields" by Slawski and Hein, 2014.
- The authors should be citing "Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems" NIPS 2015 (Sun & Hong)
- I have several issues with the numerical results presented in this paper. The size of the problem n = 100 is small. As coordinate descent methods are primarily used in large-scale optimization, I am very curious why the authors selected such a small system to test. Also, it seems that because of the structure of the matrices considered, there is equal progress to be made regardless of the coordinate selected -- thus, it seems obvious that cyclic would work better than random, as random would suffer from re-selection of coordinates, while cyclic ensures updating every coordinate in each epoch. In other words, the randomness of random selection would be unhelpful (especially using a uniform distribution). Can the authors please justify these decisions.
Overall, I'm not convinced that the analysis in this paper is that informative. It seems that the assumptions on the matrix naturally lend to using cyclic selection as there is equal progress to be made by updating any coordinate. At least that is what the numerical results are showing. I think the authors need to further convince that this problem setting is important and realistic to ML application and that their numerical results emphasize again the *realistic* benefits of cyclic selection.
============
POST REBUTTAL
============
I have read the author rebuttal and I thank the authors for their details comments. My comment regarding "equal progress to be made" was with respect to the structure in the matrix A and the authors have address this concern, pointing my attention to the reference in [20]. I think with the inclusion of the additional references mentioned by the authors in the rebuttal that support the applicability of the considered types of matrices in ML applications, I can confidently recommend this paper for acceptance.