Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

By B. Recht, Christopher R'e, Stephen J. Wright, Feng Niu. 2011

2,372 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

Adaptive Computation Time for Recurrent Neural Networks (2016, methodology): “Most of the training parameters were fixed for all experiments: Adam [18] was used for optimisation with a learning rate of 10−4, the Hogwild! algorithm [24] was used for asynchronous training with 16 threads; the initial halting unit bias bh mentioned in Equation (5) was 1; the term from Equation (”
One weird trick for parallelizing convolutional neural networks (2014, methodology): “In [Paine et al., 2013], the authors implement asynchronous SGD [Niu et al., 2011, Dean et al., 2012] on a GPU cluster with fast interconnects and use it to train the convolutional neural net of [Krizhevsky et al., 2012] using model parallelism and data parallelism.”
Beyond human-level accuracy: computational challenges in deep learning (2019, background): “ain image and language applications quickly using data-parallel scaling to reduce per-accelerator activation memory requirements [14, 26, 40]. Prior work also explores other forms of data parallelism [20, 23, 28], and there are opportunities to reduce data communication overheads of parallelism [5, ”
Don't Decay the Learning Rate, Increase the Batch Size (2017, methodology): “clude K-FAC in their study), while our work reduces the gap in convergence speed. Asynchronous-SGD is another popular strategy, which enables the use of multiple GPUs even when batch sizes are small (Recht et al., 2011; Dean et al., 2012). We do not consider asynchronous-SGD in this work, since the ”
Enriching Word Vectors with Subword Information (2016, methodology): “We carry out the optimization in parallel, by resorting to Hogwild (Recht et al., 2011).”
A Review of Sparse Expert Models in Deep Learning (2022, background): “The ﬁeld is still uncovering properties of sparse expert models, including much improved calibration (Srivastava et al., 2022); others remain unknown including their dynamics under asynchronous training (Recht et al., 2011) or their memorization abilities (Carlini et al., 2020).”
Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets (2015, neutral): “5, 15, 23, 31]. In the recent years, a lot of progress has been made in scaling up learning algorithms, by either using alternative hardware such as GPUs [10] or by taking advantage of large clusters [29]. While improving computational efﬁciency of the existing methods is important to deploy the mod”
PyTorch: An Imperative Style, High-Performance Deep Learning Library (2019, methodology): “ronize gradients using all-reduce style primitives. Another unique feature of this system is that it transparently handles sharing of CUDA tensors, making it easy to implement techniques like Hogwild [42]. 5.5 Reference counting Users often design their models to utilize all memory available during ”
TensorFlow: A system for large-scale machine learning (2016, neutral): “le beneﬁt. There is no need to make every write to the parameter state durable, because we can recompute any update from the input data, and many learning algorithms do not require strong consistency [62]. Although we do not use strong consistency for the training state, we rely on a system like Chu”
Asynchronous Methods for Deep Reinforcement Learning (2016, methodology): “se any locking in order to maximize throughput when using a large number of threads. Momentum SGD: The implementation of SGD in an asynchronous setting is relatively straightforward and well studied [Recht et al., 2011]. Let be the parameter vector that is shared across all threads and let ibe the ”
node2vec: Scalable Feature Learning for Networks (2016, methodology): “essing for computing transition probabilities for our walk (negligibly small) and simulation of random walks. The optimization phase is made efﬁcient using negative sampling [22] and asynchronous SGD [26]. Many ideas from prior work serve as useful pointers in making the sampling procedure computati”
DeepWalk: online learning of social representations (2014, methodology): “adient descent (ASGD), in the multi-worker case. Given that our updates are sparse and we do not acquire a lock to access the model shared parameters, ASGD will achieve an optimal rate of convergence [36]. While we run experiments on one machine using multiple threads, it has been demonstrated that ”
TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems (2016, methodology): “Some TensorFlow uses allow some ﬂexibil-ity in terms of the consistency of parameter updates, and we can easily express and take advantage of these relaxed synchronization requirements in some of our larger de-ployments.”
Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, neutral): “…SGD relied on bounded gradient ( E (cid:107)∇ f i ( x ) (cid:107) 2 ≤ c ) or bounded variance assumptions ( E (cid:107)∇ f i ( x ) − ∇ f ( x ) (cid:107) 2 ≤ c ) [Recht et al., 2011, Hazan and Kale, 2014, Rakhlin et al., 2012] or growth condition ( E (cid:107)∇ f i ( x ) 2 ≤ c 1 (cid:107)∇ f ( x )…”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, background): “Besides smoothness and convexity, several papers (Shamir and Zhang, 2013; Recht et al., 2011; Hazan and Kale, 2014; Rakhlin et al., 2012) assume that the variance of the stochastic gradient is bounded; that is there exists a c such that Ei‖∇fi(x)‖(2) ≤ c.”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, background): “Definition 7 (Sparsity) As in Niu et al. (2011), we introduce ∆r := maxv=1.”
Training Neural Networks with Fixed Sparse Masks (2021, background): “The standard and straightforward approach to dealing with stale gradients it to simply apply updates in the “wrong” order, which can be effective in practice [11, 42].”