Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties

By Ji Liu, Stephen J. Wright. 2014

269 citations recorded by the source corpus.

We describe an asynchronous parallel stochastic proximal coordinate descent algorithm for minimizing a composite objective function, which consists of a smooth convex function added to 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 10 cores of a multicore processor.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “Eﬀect of asynchrony has been explored and partially theoretically understood in the works of [56, 55].”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, background): “The above class of problems includes many standard problems of wide interest in machine learning, statistics and signal processing, including Support Vector Machines, as well as regularized linear and logistic regression, ordinal regression, and others.”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, methodology): “, [5, 21,30]).”
An asynchronous parallel stochastic coordinate descent algorithm (2013, methodology): “ly weaker. The AsySCD algorithm described in this paper was extended to solve the composite objective function consisting of a smooth convex function plus a separable convex function in a later work (Liu and Wright, 2014), which pays particular attention to the inconsistentread case. 3. Algorithm In”
Coordinate descent algorithms (2015, background): “The main results in [27] apply to composite functions (2), (3), but for simplicity here we state the result in terms of the problem (1), where f is convex and continuously differentiable, with nonempty solution set S and optimal objective value f∗.”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, neutral): “The value of τmax is an indicator of potential asynchronism in the algorithm, as it is closely related to the number of the processors involved in the computation [32]–[34].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Effect of asynchrony has been explored and partially theoretically understood in the works of [102, 101].”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, background): “3.1 Asynchronous Stochastic Coordinate Descent (ASCD) We apply Theorem 1 to study the asynchronous SCD algorithm by taking Y = 1 and σ = 0.”
Cyclades: Conflict-free Asynchronous Machine Learning (2016, methodology): “…study parallel asynchronous iterative algorithms on the computational model used by [NRRW11], and similar to the partially asynchronous model of [BT89]: a number of cores have access to the same shared memory, and each of them can read and update components of x in parallel from the shared memory.”
More Iterations per Second, Same Quality - Why Asynchronous Algorithms may Drastically Outperform Traditional Ones (2017, unknown): “This was extended in [16] to composite objective functions.”
An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization (2016, unknown): “Substituting these iteration counts into the guaranteed bounds provided by Theorems 2 and 3 together with assuming that τmax is roughly proportional to p [24]–[26], we can derive upper bounds on the expected optimization accuracy of each algorithm afterNt time-units (cf.”
Fast Stochastic Methods for Nonsmooth Nonconvex Optimization (2016, background): “It subsumes strongly convex functions, covers g ( a i x ) with only g being strongly convex, and includes functions that satisfy a optimal strong convexity property [12].”
Staleness-Aware Async-SGD for Distributed Deep Learning (2015, result): “, 2013] and recent work by [Liu and Wright, 2015], [Lian et al.”