Worst-case complexity of cyclic coordinate descent: O(n2) gap with randomized version

Ruoyu Sun, Yinyu Ye

Research output: Contribution to journalArticlepeer-review

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(n2) 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(n2) 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(n2) 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 languageEnglish (US)
JournalMathematical Programming
DOIs
StateAccepted/In press - 2019

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Worst-case complexity of cyclic coordinate descent: O(n<sup>2</sup>) gap with randomized version'. Together they form a unique fingerprint.

Cite this