Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
arXiv:1403.3862
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 () on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is . We describe results from implementation on ten cores of a multicore processor.
arXiv commentarXiv admin note: text overlap with arXiv:1311.1873
References in corpus (8)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Parallel Coordinate Descent for L1-Regularized Loss Minimization
- Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- Feature Clustering for Accelerating Parallel Coordinate Descent
- On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
- Flexible Parallel Algorithms for Big Data Optimization
Cited by in corpus (6)
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- 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