Iteration complexity analysis of block coordinate descent methods |
| |
| Authors: | Mingyi Hong Xiangfeng Wang Meisam Razaviyayn Zhi-Quan Luo |
| |
| Institution: | 1.Department of Industrial and Manufacturing Systems Engineering,Iowa State University,Ames,USA;2.Shanghai Key Laboratory of Trustworthy Computing, School of Computer Science and Software Engineering,East China Normal University,Shanghai,China;3.Department of Electrical Engineering,Stanford University,Palo Alto,USA;4.School of Science and Engineering,The Chinese University of Hong Kong,Shenzhen,China;5.Department of Electrical and Computer Engineering,University of Minnesota,Minneapolis,USA |
| |
| 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 \(\mathcal{{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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
