Iteration Complexity Analysis of Block Coordinate Descent Methods

Abstract

In this paper, we provide a unified iteration complexity analysis for a family of general block coordinate descent (BCD) methods, covering popular methods such as the block coordinate gradient descent (BCGD) and the block coordinate proximal gradient (BCPG), 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 (BCM) where each block is minimized exactly, we establish the sublinear convergence rate of $O(1/r)$ without per block strong convexity assumption. Further, we show that when there are only two blocks of variables, a special BSUM algorithm with Gauss-Seidel rule can be accelerated to achieve an improved rate of $O(1/r^2)$.

References in corpus (1)

• A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization

Cited by in corpus (17)

• Energy-Efficient Packet Scheduling with Finite Blocklength Codes: Convexity Analysis and Efficient Algorithms
• Photovoltaic Inverter Controllers Seeking AC Optimal Power Flow Solutions
• Coordinate Friendly Structures, Algorithms and Applications
• A Primer on Coordinate Descent Algorithms
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data
• A globally convergent algorithm for nonconvex optimization based on block coordinate update
• Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version
• Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems
• Large-scale randomized-coordinate descent methods with non-separable linear constraints
• Pathwise Coordinate Optimization for Sparse Learning: Algorithm and Theory
• Extended ADMM and BCD for Nonseparable Convex Minimization Models with Quadratic Coupling Terms: Convergence Analysis and Insights
• Block stochastic gradient iteration for convex and nonconvex optimization
• On Faster Convergence of Cyclic Block Coordinate Descent-type Methods for Strongly Convex Minimization
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
• Randomized block proximal damped Newton method for composite self-concordant minimization
• On the Linear Convergence of the Approximate Proximal Splitting Method for Non-Smooth Convex Optimization