Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties

Abstract

We describe an asynchronous parallel stochastic proximal coordinate descent algorithm for minimizing a composite objective function, which consists of a smooth convex function plus a separable convex function. In contrast to previous analyses, our model of asynchronous computation accounts for the fact that components of the unknown vector may be written by some cores simultaneously with being read by others. Despite the complications arising from this possibility, the method achieves a linear convergence rate on functions that satisfy an optimal strong convexity property and a sublinear rate ($1/k$) on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is $O(n^{1/4})$. We describe results from implementation on ten cores of a multicore processor.

arXiv admin note: text overlap with arXiv:1311.1873

References in corpus (4)

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• Feature Clustering for Accelerating Parallel Coordinate Descent
• Flexible Parallel Algorithms for Big Data Optimization

Cited by in corpus (5)

• PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
• Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption
• Asynchrony and Acceleration in Gossip Algorithms