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

• 成果类型: Article
• 署名作者: Sun, Ruoyu; Ye, Yinyu
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; Stanford University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01437-5
• 发表日期: 2021
• 页码: 487-520
• 关键词: convergence; algorithms; parallel; transmission; minimization

摘要

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(n(4)kappa(CD) log 1/epsilon) operations, where kappa(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 complexityO(n(2)kappa(CD) log 1/epsilon). 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.