PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent

By Cho-Jui Hsieh, Hsiang-Fu Yu, Inderjit S. Dhillon. 2015

109 citations recorded by the source corpus.

Stochastic Dual Coordinate Descent (DCD) is one of the most efficient ways to solve the family of l2-regularized empirical risk minimization problems, including linear SVM, logistic regression, and many others. The vanilla implementation of DCD is quite slow; however, by maintaining primal variables while updating dual variables, the time complexity of DCD can be significantly reduced. Such a strategy forms the core algorithm in the widely-used LIBLINEAR package. In this paper, we parallelize the DCD algorithms in LIBLINEAR. In recent research, several synchronized parallel DCD algorithms have been proposed, however, they fail to achieve good speedup in the shared memory multi-core setting. In this paper, we propose a family of parallel asynchronous stochastic dual coordinate descent algorithms (PASSCoDe). Each thread repeatedly selects a random dual variable and conducts coordinate updates using the primal variables that are stored in the shared memory. We analyze the convergence properties of DCD when different locking/atomic mechanisms are applied. For implementation with atomic operations, we show linear convergence under mild conditions. For implementation without any atomic operations or locking, we present a novel error analysis for PASSCoDe under the multi-core environment, showing that the converged solution is the exact solution for a primal problem with a perturbed regularizer. Experimental results show that our methods are much faster than previous parallel coordinate descent solvers.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, ML Systems & Hardware, Mathematical Optimization

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

In ML Systems & Hardware

In Mathematical Optimization

Citations in the corpus

Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, neutral): “[7] Cho-Jui Hsieh, Hsiang-Fu Yu, and Inderjit Dhillon.”
Sparsified SGD with Memory (2018, background): “creasingly common setting of a single multi-core machine or device, where locking and bandwidth of memory write operations for the common shared parameter x toften forms the main bottleneck, see e.g. [14, 18, 25]. A remedy to address these issues seems to enforce applying smaller and more efﬁcient u”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, background): “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].”
ASAGA: Asynchronous Parallel SAGA (2016, background): “An asynchronous variant of Sgd with constant step size called Hogwild was presented by Niu et al. (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 variant”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, methodology): “This paper provides a comprehensive and generic analysis to study the speedup property for a broad range of asynchronous parallel stochastic algorithms from the zeroth order to the first order methods.”
Distributed Optimization for Non-Strongly Convex Regularizers (2016, methodology): “In the case of proxCoCoA+, however, even though a speed-up is still provided by the algorithm during the initial rounds, the objective value experiences an oscillating behavior once it reaches a high enough accuracy; this behavior seems consistent with the convergence result from [7] for PASSCoDe-Wi”
Fast Asynchronous Parallel Stochastic Gradient Decent (2015, methodology): “Please note that our inconsistent reading scheme is different from that in [3] which adopts the atomic update strategy.”
Strategies and Principles of Distributed Machine Learning on Big Data (2015, background): “…∈ { 1 , . . . , V } is an integer representing one word out of a vocabulary of V words — for example, the phrase “machine learning algorithm” might be represented as [25 , 60 , 13] (the correspondence between words and integers is arbitrary, and has no bearing on the accuracy of the LDA algorithm).”
AdaBatch: Efficient Gradient Aggregation Rules for Sequential and Parallel Stochastic Gradient Methods (2017, background): “It does not require storing extra information and can be adapted to other algorithms such as SVRG or SAGA.”
Cyclades: Conflict-free Asynchronous Machine Learning (2016, background): “Additional work in ﬁrst order optimization and beyond [DJM13, WSD + 14, Hon14, HYD15, FAJ15], extending to parallel iterative linear solvers [LWS14, ADG14], has further demonstrated that linear speedups are generically possible in the asynchronous shared-memory setting.”
HogWild++: A New Mechanism for Decentralized Asynchronous Stochastic Gradient Descent (2016, methodology): “For example, [13], [6] developed asynchronous coordinate descent algorithms, [25] proposed a simple way to improve the convergence property of asynchronous coordinate descent.”
Salmon: fast and bias-aware quantification of transcript expression using dual-phase inference (2017, background): “However, due to the stochastic and additive nature of the updates, this has little-to-no detrimental effect [24].”
ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates (2015, methodology): “[30] proposed an async-parallel dual coordinate descent method for solving `2 regularized empirical risk minimization problems.”
A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization (2016, background): “For example, there are direct attempts to parallelize stochastic gradient descent (Recht et al., 2011; Zinkevich et al., 2010; Hsieh et al., 2015).”
On the Convergence of a Family of Robust Losses for Stochastic Gradient Descent (2016, background): “Therefore, many researchers have extensively studied and applied various SGD methods [3,4,5].”
Fast Asynchronous Parallel Stochastic Gradient Descent: A Lock-Free Approach with Convergence Guarantee (2016, background): “PASSCoDe (Hsieh, Yu, and Dhillon 2015) and CoCoA (Jaggi et al. 2014) are also asynchronous approaches for parallel SGD.”