Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
arXiv:1406.0238 · doi:10.1007/978-3-319-17689-5_11
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.
arXiv commentin Recent Developments in Numerical Analysis and Optimization, 2015
References in corpus (14)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Distributed Coordinate Descent Method for Learning with Big Data
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- Communication-Efficient Distributed Dual Coordinate Ascent
- Parallel Coordinate Descent Methods for Big Data Optimization
- Stochastic Optimization with Importance Sampling
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- Feature Clustering for Accelerating Parallel Coordinate Descent
- Accelerated, Parallel and Proximal Coordinate Descent
- Inexact Coordinate Descent: Complexity and Preconditioning
- On the Finite Time Convergence of Cyclic Coordinate Descent Methods
- On Optimal Probabilities in Stochastic Coordinate Descent Methods
- Parallel coordinate descent methods for composite minimization: convergence analysis and error bounds
- Iteration complexity analysis of random coordinate descent methods for regularized convex problems
Cited by in corpus (23)
- 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?
- Partially separable convexly-constrained optimization with non-Lipschitzian singularities and its complexity
- Make Workers Work Harder: Decoupled Asynchronous Proximal Stochastic Gradient Descent
- Parallel Stochastic Newton Method
- Coordinate Descent Algorithms
- Parallel Coordinate Descent Newton Method for Efficient -Regularized Minimization
- High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms
- Avoiding communication in primal and dual block coordinate descent methods
- Distributed stochastic optimization with large delays
- Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization
- A Stochastic Large-scale Machine Learning Algorithm for Distributed Features and Observations
- Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption