CYCLADES: Conflict-free Asynchronous Machine Learning

Abstract

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.

References in corpus (16)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• GraphLab: A New Framework For Parallel Machine Learning
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• Slow Learners are Fast
• Factoring nonnegative matrices with linear programs
• Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Parallel Coordinate Descent Methods for Big Data Optimization
• An Asynchronous Parallel Randomized Kaczmarz Algorithm
• Parallel Correlation Clustering on Big Graphs
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• NOMAD: Non-locking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion
• Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation

Cited by in corpus (6)

• Accuracy-Efficiency Trade-Offs and Accountability in Distributed ML Systems
• Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers
• Orchestrating the Development Lifecycle of Machine Learning-Based IoT Applications: A Taxonomy and Survey
• A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection
• Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees
• HAMSI: A Parallel Incremental Optimization Algorithm Using Quadratic Approximations for Solving Partially Separable Problems