Cyclades: Conflict-free Asynchronous Machine Learning
By Xinghao Pan, Maximilian Lam, Stephen Tu, Dimitris Papailiopoulos, Ce Zhang, Michael I. Jordan, Kannan Ramchandran, Christopher R'e, B. Recht. 2016
63 citations recorded by the source corpus.
We present CYCLADES, a general framework for parallelizing stochastic optimization algorithms in a shared memory setting. CYCLADES is asynchronous during shared model updates, and requires no memory locking mechanisms, similar to HOGWILD!-type algorithms. Unlike HOGWILD!, CYCLADES introduces no conflicts during the parallel execution, and offers a black-box analysis for provable speedups across a large family of algorithms. Due to its inherent conflict-free nature and cache locality, our multi-core implementation of CYCLADES consistently outperforms HOGWILD!-type algorithms on sufficiently sparse datasets, leading to up to 40% speedup gains compared to the HOGWILD! implementation of SGD, and up to 5x gains over asynchronous implementations of variance reduction algorithms.
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
- Simon Lacoste-Julien
- Fabian Pedregosa
- Rémi Leblond
- Peter Richtárik
- Francis R. Bach
- Alexandre D'efossez
- Soham De
- Sebastian U. Stich
Citations in the corpus
- Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, methodology): “This is confirmed by Pan et al. (2016), where the authors tried to implement a parallel version of the lagged updates scheme and had to alter the algorithm to succeed, obtaining an algorithm with suboptimal performance as a result.”
- Semantics-Preserving Parallelization of Stochastic Gradient Descent (2018, background): “Given the number of frequent features in our datasets (Column NFNZ in Table II), it is not possible to use the Cyclades approach for our datasets.”
- Efficient Distributed SGD with Variance Reduction (2015, background): “We consider a centralized setting, where the clients can only communicate with the central server, and our goal is to derive stochastic algorithms that scale linearly to high p, while remaining stable even under low communication frequencies between local and central nodes.”
- AdaBatch: Efficient Gradient Aggregation Rules for Sequential and Parallel Stochastic Gradient Methods (2017, background): “Cyclades [16] builds on Hogwild!, assigning training samples to specific workers using graph theory results to remove conflicts.”