HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

2011/06/28 by Feng Niu, Benjamin Recht, Niu, Feng +5 · 133 citations
Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.1106.5730

Abstract

Stochastic Gradient Descent (SGD) is a popular algorithm that can achieve state-of-the-art performance on a variety of machine learning tasks. Several researchers have recently proposed schemes to parallelize SGD, but all require performance-destroying memory locking and synchronization. This work aims to show using novel theoretical analysis, algorithms, and implementation that SGD can be implemented without any locking. We present an update scheme called HOGWILD! which allows processors access to shared memory with the possibility of overwriting each other's work. We show that when the associated optimization problem is sparse, meaning most gradient updates only modify small parts of the decision variable, then HOGWILD! achieves a nearly optimal rate of convergence. We demonstrate experimentally that HOGWILD! outperforms alternative schemes that use locking by an order of magnitude.

Citations

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• MapReduce

Cited by

• Performance and Stability of Barrier Mode Parallel Systems with Heterogeneous and Redundant Jobs
• A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications
• OLR-WAA: Adaptive and Drift-Resilient Online Regression with Dynamic Weighted Averaging
• CurvaDion: Curvature-Adaptive Distributed Orthonormalization
• SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm
• Federated Doubly Stochastic Kernel Learning for Vertically Partitioned Data
• Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Poincaré Embeddings for Learning Hierarchical Representations
• Stragglers Can Contribute More: Uncertainty-Aware Distillation for Asynchronous Federated Learning
• Asynchronous Decentralized Parallel Stochastic Gradient Descent
• Sync-Switch: Hybrid Parameter Synchronization for Distributed Deep Learning
• node2vec: Scalable Feature Learning for Networks
• Don't Decay the Learning Rate, Increase the Batch Size
• Parameter Database : Data-centric Synchronization for Scalable Machine\n Learning
• Recent Advances in Convolutional Neural Networks
• Parallel Stochastic Gradient Descent with Sound Combiners
• Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems
• Tell Me Something New: A New Framework for Asynchronous Parallel Learning
• Collaborative Similarity Embedding for Recommender Systems
• On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms
• Caffe con Troll: Shallow Ideas to Speed Up Deep Learning
• Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets
• Flexible numerical optimization with ensmallen
• ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding
• Accelerating SLIDE Deep Learning on Modern CPUs: Vectorization, Quantizations, Memory Optimizations, and More
• The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
• Probabilistic Synchronous Parallel
• Occupy the Cloud: Distributed Computing for the 99%
• Parallelizing Word2Vec in Multi-Core and Many-Core Architectures
• Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis
• ParMAC: distributed optimisation of nested functions, with application\n to learning binary autoencoders
• Stochastic Dual Ascent for Solving Linear Systems
• Federated Learning with Buffered Asynchronous Aggregation
• A machine-compiled macroevolutionary history of Phanerozoic life
• Optimizing Network Performance for Distributed DNN Training on GPU Clusters: ImageNet/AlexNet Training in 1.5 Minutes
• mvn2vec: Preservation and Collaboration in Multi-View Network Embedding
• Weighted SGD for ℓ_p Regression with Randomized Preconditioning
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays
• Variance Reduction in SGD by Distributed Importance Sampling
• LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning
• Cataloging the Visible Universe through Bayesian Inference at Petascale
• Large-scale Simple Question Answering with Memory Networks
• SparCML: High-Performance Sparse Communication for Machine Learning
• The Convergence of Sparsified Gradient Methods
• Optimization in Theory and Practice
• An Asynchronous Parallel Randomized Kaczmarz Algorithm
• Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding
• A Split-Client Approach to Second-Order Optimization
• Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
• Uncertainty Quantification for Online Learning and Stochastic Approximation via Hierarchical Incremental Gradient Descent
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Stochastic gradient descent methods for estimation with large data sets
• Laminar: A Scalable Asynchronous RL Post-Training Framework
• A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization
• Distributed Learning of Deep Neural Networks using Independent Subnet Training
• Sparsification as a Remedy for Staleness in Distributed Asynchronous SGD
• Neptune: Advanced ML Operator Fusion for Locality and Parallelism on GPUs
• Local SGD Converges Fast and Communicates Little
• Secure Distributed Training at Scale
• GT-SEER: Geo-Temporal SEquential Embedding Rank for Point-of-interest Recommendation
• Beyond Human-Level Accuracy: Computational Challenges in Deep Learning
• DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs
• Hybrid Dual-Batch and Cyclic Progressive Learning for Efficient Distributed Training
• Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learning
• YellowFin and the Art of Momentum Tuning
• Deep Learning with Limited Numerical Precision
• A Random Gossip BMUF Process for Neural Language Modeling
• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity
• Towards Adapting Federated & Quantum Machine Learning for Network Intrusion Detection: A Survey
• Neural SLAM: Learning to Explore with External Memory
• Vertex-Context Sampling for Weighted Network Embedding
• Asynchronous Coordinate Descent under More Realistic Assumptions
• A Parallel and Efficient Algorithm for Learning to Match
• Towards a Unified Architecture for in-RDBMS Analytics
• Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms
• Training Neural Networks with Fixed Sparse Masks
• Adaptive Elastic Training for Sparse Deep Learning on Heterogeneous Multi-GPU Servers
• Distributed deep learning on edge-devices: feasibility via adaptive\n compression
• CYCLADES: Conflict-free Asynchronous Machine Learning
• Deep Learning At Scale and At Ease
• Streaming Variational Bayes
• Graph Coloring for Multi-Task Learning
• BoostClean: Automated Error Detection and Repair for Machine Learning
• Graph Balancing for Distributed Subgradient Methods over Directed Graphs
• Learning a Predictive Model for Music Using PULSE
• Distributed Proximal Gradient Algorithm for Partially Asynchronous\n Computer Clusters
• L-XAIDS: A LIME-based eXplainable AI framework for Intrusion Detection Systems
• Gradient Diversity: a Key Ingredient for Scalable Distributed Learning
• A Multi-Batch L-BFGS Method for Machine Learning
• Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling
• DyNet: The Dynamic Neural Network Toolkit
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast\n Convergence
• Deep Learning Approaches for Image Retrieval and Pattern Spotting in\n Ancient Documents
• Tensor Comprehensions: Framework-Agnostic High-Performance Machine Learning Abstractions
• A Block Decomposition Algorithm for Sparse Optimization
• Analogical Inference for Multi-Relational Embeddings
• Deep Speech 2: End-to-End Speech Recognition in English and Mandarin
• Differential Equations for Modeling Asynchronous Algorithms
• Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent
• Swivel: Improving Embeddings by Noticing What's Missing
• Deep Leakage from Gradients
• Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization
• Deep Learning in Mobile and Wireless Networking: A Survey
• Adaptive Computation Time for Recurrent Neural Networks
• Backprop with Approximate Activations for Memory-efficient Network Training
• Near-Data Processing for Differentiable Machine Learning Models
• Homomorphic Parameter Compression for Distributed Deep Learning Training
• Keeping CALM: When Distributed Consistency is Easy
• Natural Compression for Distributed Deep Learning
• Parallel Coordinate Descent Newton Method for Efficient ℓ₁-Regularized Minimization
• High-Performance Distributed ML at Scale through Parameter Server Consistency Models
• Communication-Efficient Asynchronous Stochastic Frank-Wolfe over\n Nuclear-norm Balls
• Block Distributed Majorize-Minimize Memory Gradient Algorithm and its\n application to 3D image restoration
• Topic Modeling via Full Dependence Mixtures
• Heterogeneous Information Network Embedding for Meta Path based Proximity
• Asynchronous Complex Analytics in a Distributed Dataflow Architecture
• Structure Regularization for Structured Prediction: Theories and Experiments
• Energy Consumption in Parallel Neural Network Training
• Deep Determinantal Point Processes
• Fast, Accurate, and Scalable Method for Sparse Coupled Matrix-Tensor Factorization
• Toward Errorless Training ImageNet-1k
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and\n Interpolation
• Parallel training of linear models without compromising convergence
• A Forest Mixture Bound for Block-Free Parallel Inference
• DeepSpark: A Spark-Based Distributed Deep Learning Framework for Commodity Clusters
• Cooperative SGD: A unified Framework for the Design and Analysis of\n Communication-Efficient SGD Algorithms
• The End of Slow Networks: It's Time for a Redesign
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems

Related

• Consistent Lock-free Parallel Stochastic Gradient Descent for Fast and Stable Convergence
• Asynchronous Parallel Stochastic Gradient Descent - A Numeric Core for Scalable Distributed Machine Learning Algorithms
• The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
• Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
• Fast Asynchronous Parallel Stochastic Gradient Decent