Iteration complexity analysis of block coordinate descent methods

Mingyi Hong, Xiangfeng Wang, Meisam Razaviyayn, Zhi Quan Luo

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

Abstract

In this paper, we provide a unified iteration complexity analysis for a family of general block coordinate descent methods, covering popular methods such as the block coordinate gradient descent and the block coordinate proximal gradient, under various different coordinate update rules. We unify these algorithms under the so-called block successive upper-bound minimization (BSUM) framework, and show that for a broad class of multi-block nonsmooth convex problems, all algorithms covered by the BSUM framework achieve a global sublinear iteration complexity of O(1 / r) , where r is the iteration index. Moreover, for the case of block coordinate minimization where each block is minimized exactly, we establish the sublinear convergence rate of O(1/r) without per block strong convexity assumption.

Original languageEnglish (US)
Pages (from-to)85-114
Number of pages30
JournalMathematical Programming
Volume163
Issue number1-2
DOIs
StatePublished - May 1 2017

Bibliographical note

Funding Information:
Mingyi Hong: This author is supported by National Science Foundation (NSF) Grant CCF-1526078 and by Air Force Office of Scientific Research (AFOSR) Grant 15RT0767. Xiangfeng Wang: This author is supported by NSFC, Grant No.11501210, and by Shanghai YangFan, Grant No. 15YF1403400. Zhi-Quan Luo: This research is supported by NSFC, Grant No. 61571384, and by the Leading Talents of Guang Dong Province program, Grant No. 00201510.

Keywords

  • 49-90

Fingerprint Dive into the research topics of 'Iteration complexity analysis of block coordinate descent methods'. Together they form a unique fingerprint.

Cite this