The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory

DOI10.1145/3212734.3212763MaRDI QIDQ5197680zbMATH OpenOpenAlexFDO

Authors Dan Alistarh, Christopher de Sa, Nikola Konstantinov

Publication date 19 September 2019

Published in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.08841

zbMATH Keywords

distributed optimizationlower boundsshared memorystochastic gradient descent

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Distributed algorithms (68W15)

Abstract: 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.

Recommendations

• Convergence of Asynchronous Distributed Gradient Methods Over Stochastic Networks
• Asynchronous stochastic coordinate descent: parallelism and convergence properties
• On the parallelization upper bound for asynchronous stochastic gradients descent in non-convex optimization
• On the convergence analysis of asynchronous SGD for solving consistent linear systems
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• A sharp convergence rate for a model equation of the asynchronous stochastic gradient descent
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• On the Rate of Convergence of a Partially Asynchronous Gradient Projection Algorithm
• Parallel stochastic asynchronous coordinate descent: tight bounds on the possible parallelism

Cited in

(7)

• On the Rate of Convergence of a Partially Asynchronous Gradient Projection Algorithm
• scientific article; zbMATH DE number 7307474 (Why is no real title available?)
• A brief tutorial on distributed and concurrent machine learning
• Asynchronous Gradient Push
• Asynchronous fully-decentralized SGD in the cluster-based model
• Optimization Algorithms for Distributed Machine Learning
• Asynchronous fully-decentralized SGD in the cluster-based model

This page was built for publication: The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5197680)