# Worst-case Complexity of Cyclic Coordinate Descent: O(n2) Gap with Randomized Version

arXiv: https://arxiv.org/abs/1604.07130 · HTML: https://mlsanity.com/paper/1604.07130/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2016.

## Built on by (most cited first, 6 of 6)

- [How catastrophic can catastrophic forgetting be in linear regression?](https://mlsanity.com/paper/2205.09588/) (2022)
- [Provable Adaptivity of Adam under Non-uniform Smoothness](https://mlsanity.com/paper/2208.09900/) (2022)
- [Cyclic Coordinate Dual Averaging with Extrapolation](https://mlsanity.com/paper/2102.13244/) (2021)
- [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023)
- [On a Faster R-Linear Convergence Rate of the Barzilai-Borwein Method](https://mlsanity.com/paper/2101.00205/) (2021)
- [Fast Online Node Labeling for Very Large Graphs](https://mlsanity.com/paper/2305.16257/) (2023)

## Abstract (arXiv)

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 transformed to Kaczmarz method and projection onto convex sets (POCS). We observe that the known provable complexity of C-CD can be O(n2) times slower than randomized coordinate descent (R-CD), but no example was rigorously proven to exhibit such a large gap. In this paper we show that the gap indeed exists. We prove that there exists an example for which C-CD takes at least O(n4 kappaCD logfrac1ε) operations, where kappaCD is related to Demmel's condition number and it determines the convergence rate of R-CD. It implies that in the worst case C-CD can indeed be O(n2) times slower than R-CD, which has complexity O( n2 kappaCD logfrac1ε). Note that for this example, the gap exists for any fixed update order, not just a particular order. Based on the example, we establish several almost tight complexity bounds of C-CD for quadratic problems. One difficulty with the analysis is that the spectral radius of a non-symmetric iteration matrix does not necessarily constitute a textitlower bound for the convergence rate. An immediate consequence is that for Gauss-Seidel method, Kaczmarz method and POCS, there is also an O(n2)  gap between the cyclic versions and randomized versions (for solving linear systems). We also show that the classical convergence rate of POCS by Smith, Solmon and Wager [1] is always worse and sometimes can be infinitely times worse than our bound.