The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory

By Dan Alistarh, Christopher De Sa, Nikola Konstantinov. 2018

42 citations recorded by the source corpus.

Stochastic Gradient Descent (SGD) is a fundamental algorithm in machine learning, representing the optimization backbone for training several classic models, from regression to neural networks. Given the recent practical focus on distributed machine learning, significant work has been dedicated to the convergence properties of this algorithm under the inconsistent and noisy updates arising from execution in a distributed environment. However, surprisingly, the convergence properties of this classic algorithm in the standard shared-memory model are still not well-understood. In this work, we address this gap, and provide new convergence bounds for lock-free concurrent stochastic gradient descent, executing in the classic asynchronous shared memory model, against a strong adaptive adversary. Our results give improved upper and lower bounds on the "price of asynchrony'' when executing the fundamental SGD algorithm in a concurrent setting. They show that this classic optimization tool can converge faster and with a wider range of parameters than previously known under asynchronous iterations. At the same time, we exhibit a fundamental trade-off between the maximum delay in the system and the rate at which SGD can converge, which governs the set of parameters under which this algorithm can still work efficiently.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Communication trade-offs for synchronized distributed SGD with large step size (2019, neutral): “…Keuper and Pfreundt (2015); De and Goldstein (2015); Feyzmahdavian et al. (2015); Lian et al. (2015); Mania et al. (2015); Zhao and Li (2015); Duchi et al. (2015); Chen et al. (2016a); Lian et al. (2017a); Pedregosa et al. (2017); Lian et al. (2017b); Leblond et al. (2018); Alistarh et al. (2018).”
Don't Use Large Mini-Batches, Use Local SGD (2018, background): “This is still an active area of research (cf. also (Alistarh et al., 2018; Stich, 2018)).”
Sparsified SGD with Memory (2018, background): “For instance, we like to highlight that asynchronous SGD schemes [2, 25] could profit from the gradient sparsification.”
The Convergence of Sparsified Gradient Methods (2018, methodology): “Due to space constraints, the complete proofs are deferred to the full version of our paper [3].”
Robust Learning from Untrusted Sources (2019, background): “The worst-case performance of distributed SGD has also been studied in the context of asynchronous training (De Sa et al., 2015; Alistarh et al., 2018b).”
Distributed Hierarchical GPU Parameter Server for Massive Scale Deep Learning Ads Systems (2020, methodology): “We have to synchronize the parameters on different nodes to guarantee the model convergence (Ho et al., 2013; Chilimbi et al., 2014; Cui et al., 2016; Alistarh et al., 2018).”
PopSGD: Decentralized Stochastic Gradient Descent in the Population Model (2019, background): “[6] Dan Alistarh, Christopher De Sa, and Nikola Konstantinov.”