A better convergence analysis of the block coordinate descent method for large scale machine learning

2016/08/17 by Shi, Ziqiang, Liu, Rujie
#FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1608.04826

Abstract

This paper considers the problems of unconstrained minimization of large scale smooth convex functions having block-coordinate-wise Lipschitz continuous gradients. The block coordinate descent (BCD) method are among the first optimization schemes suggested for solving such problems \citenesterov2012efficiency. We obtain a new lower (to our best knowledge the lowest currently) bound that is 16p³ times smaller than the best known on the information-based complexity of BCD method based on an effective technique called Performance Estimation Problem (PEP) proposed by Drori and Teboulle \citedrori2012performance recently for analyzing the performance of first-order black box optimization methods. Numerical test confirms our analysis.

Related

• Let's Make Block Coordinate Descent Converge Faster: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence
• On the Worst-Case Analysis of Cyclic Block Coordinate Descent type Algorithms
• Iteration Complexity Analysis of Block Coordinate Descent Methods
• Block Coordinate Descent Methods for Structured Nonconvex Optimization with Nonseparable Constraints: Optimality Conditions and Global Convergence
• On the Complexity Analysis of Randomized Block-Coordinate Descent Methods