Parallel coordinate descent methods for composite minimization: convergence analysis and error bounds

Abstract

In this paper we propose a distributed version of a randomized block-coordinate descent method for minimizing the sum of a partially separable smooth convex function and a fully separable non-smooth convex function. Under the assumption of block Lipschitz continuity of the gradient of the smooth function, this method is shown to have a sublinear convergence rate. Linear convergence rate of the method is obtained for the newly introduced class of generalized error bound functions. We prove that the new class of generalized error bound functions encompasses both global/local error bound functions and smooth strongly convex functions. We also show that the theoretical estimates on the convergence rate depend on the number of blocks chosen randomly and a natural measure of separability of the objective function.

43 pages, 3 figures, 1 table, October 2013, University Politehnica Bucharest

References in corpus (1)

• Parallel Coordinate Descent for L1-Regularized Loss Minimization

Cited by in corpus (6)

• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Stochastic Dual Ascent for Solving Linear Systems
• Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption
• On the Linear Convergence of the Approximate Proximal Splitting Method for Non-Smooth Convex Optimization