An asynchronous parallel stochastic coordinate descent algorithm

By Ji Liu, Stephen J. Wright, Christopher R'e, Victor Bittorf, Srikrishna Sridhar. 2013

398 citations recorded by the source corpus.

We describe an asynchronous parallel stochastic coordinate descent algorithm for minimizing smooth unconstrained or separably constrained functions. The method achieves a linear convergence rate on functions that satisfy an essential 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(n1/2) in unconstrained optimization and O(n1/4) in the separable-constrained case, where n is the number of variables. We describe results from implementation on 40-core processors.

Subfields: Optimization & Training

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, background): “(2011); part of their framework of analysis was re-used and inspired most of the recent literature on asynchronous parallel optimization algorithms with convergence rates, including asynchronous variants of coordinate descent (Liu et al., 2015), Sdca (Hsieh et al.”
Optimization Methods for Large-Scale Machine Learning (2016, background): “ However, convergence of the method can be proved, and improves when one can bound the degree of staleness of each update. For further information and insight into these ideas, we refer the reader to [16,98]. 8 Methods for Regularized Models Our discussion of structural risk minimization (see x2.3) ”
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, background): “Related Work The large-scale nature of modern machine learning has spurred a great deal of novel research on distributed and parallel training algorithms and systems (Recht et al., 2011; Dean et al., 2012; Alistarh et al., 2017; Jaggi et al., 2014; Liu et al., 2014; Mania et al., 2015; Chen et al., ”
Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, methodology): “…and Duchi, 2011, Zhang et al., 2014, Feyzmahdavian et al., 2015, Paine et al., 2013], stochastic coordinate descent [Avron et al., 2014, Liu et al., 2014a], dual stochastic coordinate ascent [Tran et al., 2015], randomized Kaczmarz algorithm [Liu et al., 2014b], and ADMM [Zhang and Kwok, 2014].”
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].”
Factorized Q-learning for large-scale multi-agent systems (2018, methodology): “Since all the agents simultaneously carry out such coordinate descent updates in parallel at each time-step and the experience replay mechanism from DQN [15] is adopted, the concrete method to estimate the optimal joint action for each state is somewhat similar to the “asynchronous (parallel) stocha”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, background): “Several distributed variants of SGD have been proposed (Niu et al., 2011; Liu et al., 2014; Duchi et al., 2013).”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, background): “Work in parallel and distributed optimization has shown that these systems can obtain massive speed up gains in both convex and non-convex settings [9, 18, 19, 26, 34, 41].”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, methodology): “A large body of recent work has demonstrated that near-linear speedups are achievable, in theory and practice, on many common machine learning tasks [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13, 16].”
Communication-Efficient Distributed Dual Coordinate Ascent (2014, methodology): “For coordinate descent, the analogous approach was studied in [28].”
Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms (2015, neutral): “Many asynchronous versions of other stochastic algorithms have been individually analyzed, such as stochastic coordinate descent (SGD) [14, 15] and accelerated parallel proximal coordinate descent (APPROX) [6], producing rate results that are similar to those of HOGWILD! Recently, Gupta et al.”
Coordinate descent algorithms (2015, neutral): “se, we can choose smaller values of in (50), allowing graceful degradation of the convergence bounds while still obtaining fairly ecient parallel implementations. We note that an earlier analysis in [28] made a stronger assumption on ^xk | that it is equal to some earlier iterate xjof Algorithm 7, w”
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants (2015, methodology): “A different line of methods is that of (primal) coordinate descent methods, and their parallel and distributed variants [13, 14, 18, 21, 22].”
ASAGA: Asynchronous Parallel SAGA (2016, positive): “(2011); part of their framework of analysis was re-used and inspired most of the recent literature on asynchronous parallel optimization algorithms with convergence rates, including asynchronous variants of coordinate descent (Liu et al., 2015), Sdca (Hsieh et al.”