Distributed Block Coordinate Descent for Minimizing Partially Separable Functions

Abstract

In this work we propose a distributed randomized block coordinate descent method for minimizing a convex function with a huge number of variables/coordinates. We analyze its complexity under the assumption that the smooth part of the objective function is partially block separable, and show that the degree of separability directly influences the complexity. This extends the results in [Richtarik, Takac: Parallel coordinate descent methods for big data optimization] to a distributed environment. We first show that partially block separable functions admit an expected separable overapproximation (ESO) with respect to a distributed sampling, compute the ESO parameters, and then specialize complexity results from recent literature that hold under the generic ESO assumption. We describe several approaches to distribution and synchronization of the computation across a cluster of multi-core computers and provide promising computational results.

in Recent Developments in Numerical Analysis and Optimization, 2015

References in corpus (6)

• Communication-Efficient Distributed Dual Coordinate Ascent
• Stochastic Optimization with Importance Sampling
• Feature Clustering for Accelerating Parallel Coordinate Descent
• Accelerated, Parallel and Proximal Coordinate Descent
• Parallel coordinate descent methods for composite minimization: convergence analysis and error bounds
• Iteration complexity analysis of random coordinate descent methods for ${\ell }_0$ regularized convex problems

Cited by in corpus (22)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Adding vs. Averaging in Distributed Primal-Dual Optimization
• A Primer on Coordinate Descent Algorithms
• Distributed Mini-Batch SDCA
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Incremental Deep Learning for Robust Object Detection in Unknown Cluttered Environments
• A Low-Rank Coordinate-Descent Algorithm for Semidefinite Programming Relaxations of Optimal Power Flow
• Matrix Completion under Interval Uncertainty
• Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization?
• Make Workers Work Harder: Decoupled Asynchronous Proximal Stochastic Gradient Descent
• Partially separable convexly-constrained optimization with non-Lipschitzian singularities and its complexity
• Coordinate Descent Algorithms
• Parallel Stochastic Newton Method
• High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms
• A Stochastic Large-scale Machine Learning Algorithm for Distributed Features and Observations
• Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization
• Distributed stochastic optimization with large delays
• Avoiding communication in primal and dual block coordinate descent methods
• Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption