Skip to main content
Article
Iteration complexity analysis of block coordinate descent methods
Mathematical Programming
  • Mingyi Hong, Iowa State University
  • Xiangfeng Wang, East China Normal University
  • Mesiam Razaviyayn, Stanford University
  • Zhi-Quan Luo, University of Minnesota - Twin Cities
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
8-19-2016
DOI
10.1007/s10107-016-1057-8
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)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">O(1/r)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.

Comments

This is a manuscript of an article from Mathematical Programming (2016): The final publication is available at Springer via http://dx.doi.org/0.1007/s10107-016-1057-8.

Copyright Owner
Springer Verlag
Language
en
File Format
application/pdf
Citation Information
Mingyi Hong, Xiangfeng Wang, Mesiam Razaviyayn and Zhi-Quan Luo. "Iteration complexity analysis of block coordinate descent methods" Mathematical Programming (2016)
Available at: http://works.bepress.com/mingyi_hong/23/