Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version

Ruoyu Sun, Yinyu Ye

This paper concerns the worst-case complexity of cyclic coordinate descent (C-CD) for minimizing a convex quadratic function, which is equivalent to Gauss-Seidel method and can be…