## Abstract

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, Kaczmarz method and projection onto convex sets (POCS) in this simple setting. We observe that the known provable complexity of C-CD can be O(n^{2}) times slower than randomized coordinate descent (R-CD), but no example was 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κCDlog1ϵ) operations, where κ_{CD} 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(n^{2}) times slower than R-CD, which has complexity O(n2κCDlog1ϵ). Note that for this example, the gap exists for any fixed update order, not just a particular order. An immediate consequence is that for Gauss–Seidel method, Kaczmarz method and POCS, there is also an O(n^{2}) gap between the cyclic versions and randomized versions (for solving linear systems). One difficulty with the analysis is that the spectral radius of a non-symmetric iteration matrix does not necessarily constitute a lower bound for the convergence rate. Finally, we design some numerical experiments to show that the size of the off-diagonal entries is an important indicator of the practical performance of C-CD.

Original language | English (US) |
---|---|

Pages (from-to) | 487-520 |

Number of pages | 34 |

Journal | Mathematical Programming |

Volume | 185 |

Issue number | 1-2 |

DOIs | |

State | Published - Jan 2021 |

## ASJC Scopus subject areas

- Software
- General Mathematics

## Fingerprint

Dive into the research topics of 'Worst-case complexity of cyclic coordinate descent: O(n^{2}) gap with randomized version'. Together they form a unique fingerprint.