Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms

By Christopher De Sa, Ce Zhang, Kunle Olukotun, Christopher R'e. 2015

210 citations recorded by the source corpus.

Stochastic gradient descent (SGD) is a ubiquitous algorithm for a variety of machine learning problems. Researchers and industry have developed several techniques to optimize SGD’s runtime performance, including asynchronous execution and reduced precision. Our main result is a martingale-based analysis that enables us to capture the rich noise models that may arise from such techniques. Specifically, we use our new analysis in three ways: (1) we derive convergence rates for the convex case (Hogwild!) with relaxed assumptions on the sparsity of the problem; (2) we analyze asynchronous SGD algorithms for non-convex matrix problems including matrix completion; and (3) we design and analyze an asynchronous SGD algorithm, called Buckwild!, that uses lower-precision arithmetic. We show experimentally that our algorithms run efficiently for a variety of problems on modern hardware.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training, Signal Processing

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 Computer Networks and Communications

In Optimization & Training

In Signal Processing

Citations in the corpus

Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, background): “• In contrast to the Hogwild analysis from Niu et al. (2011); De Sa et al. (2015), our proof technique handles inconsistent reads and a non-uniform processing speed across fi’s.”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, methodology): “To mitigate synchronization delay, asynchronous SGD method are studied in [28, 8, 19].”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Some of the work in this direction can be found in Zhang et al. (2017); Wen et al. (2017); Wangni et al. (2017); Sa et al. (2015); Na et al. (2017); Gupta et al. (2015); Alistarh et al. (2016); Khirirat et al. (2018).”
QSGD: Communication-Optimal Stochastic Gradient Descent, with Applications to Training Neural Networks (2016, background): “Buckwild! [9] was the first to consider the theoretical guarantees of low-precision SGD.”
Opportunities and obstacles for deep learning in biology and medicine (2017, background): “There now exist a number of algorithms [375,392,393], tools [394–396], and high-level libraries [397,398] for deep learning in a distributed environment, and it is possible to train very complex networks with limited infrastructure [399].”
Sparsified SGD with Memory (2018, methodology): “Several papers consider approaches that limit the number of bits to represent floating point numbers [13, 24, 31].”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, background): “Modern large-scale machine learning applications require scaling stochastic optimization algorithms [30, 28, 15, 11] to distributed computational architectures [10, 39, 12, 20, 19, 38] or multicore systems [26, 9, 22, 25].”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, neutral): “Partially initiated by a 1-bit implementation of SGD by Microsoft in [5], a large number of recent studies revisited the idea of low-precision training as a means to reduce communication [13, 14, 15, 16, 17, 18, 19, 17, 20, 21].”
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].”
The Convergence of Sparsified Gradient Methods (2018, methodology): “, [18, 9, 7], as updates are not discarded, but delayed.”
Demystifying Parallel and Distributed Deep Learning (2018, background): “Compression Quantization [Alistarh et al. 2017; Chen et al. 2014; Courbariaux and Bengio 2016; Courbariaux et al. 2015; Dettmers 2015; Gupta et al. 2015; Han et al. 2016; Hubara et al. 2016; Köster et al. 2017; Li and Liu 2016; Rastegari et al. 2016; Sa et al. 2015; Seide et al. 2014a; Wen et al. 20”
ASAGA: Asynchronous Parallel SAGA (2016, background): “…with convergence rates, including asynchronous variants of coordinate descent (Liu et al., 2015), Sdca (Hsieh et al., 2015), Sgd for non-convex problems (De Sa et al., 2015; Lian et al., 2015), Sgd for stochastic optimization (Duchi et al., 2015) and Svrg (Reddi et al., 2015; Zhao and Li, 2016).”
Asynchrony begets momentum, with an application to deep learning (2016, background): “Recent work includes results in the dense case, for general convex problems asymptotically [9], and specifically for matrix completion problems [10].”
High-Accuracy Low-Precision Training (2018, methodology): “While the use of SVRG allowed us to reach this minimum level of accuracy more quickly (at a linear rate, in fact) compared with low-precision SGD [9], it has not let us surpass this minimum.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “Improved analysis of asynchronous SGD was also presented in [41], simultaneously with a version that uses lower-precision arithmetic was introduced without sacrificing performance, which is a trend that might find use in other parts of machine learning in the following years.”