A sharp convergence rate for a model equation of the asynchronous stochastic gradient descent

DOI10.4310/CMS.2021.V19.N3.A13MaRDI QIDQ2057038zbMATH OpenOpenAlexFDO

Authors Yuhua Zhu, Lexing Ying

Publication date 8 December 2021

Published in Communications in Mathematical Sciences (Search for Journal in Brave)

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

zbMATH Keywords

asynchronous stochastic gradient descentdistributed learningstochastic modified equations

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Distributed algorithms (68W15) Randomized algorithms (68W20) Stochastic programming (90C15)

Abstract: We give a sharp convergence rate for the asynchronous stochastic gradient descent (ASGD) algorithms when the loss function is a perturbed quadratic function based on the stochastic modified equations introduced in [An et al. Stochastic modified equations for the asynchronous stochastic gradient descent, arXiv:1805.08244]. We prove that when the number of local workers is larger than the expected staleness, then ASGD is more efficient than stochastic gradient descent. Our theoretical result also suggests that longer delays result in slower convergence rate. Besides, the learning rate cannot be smaller than a threshold inversely proportional to the expected staleness.

Recommendations

• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• New Convergence Aspects of Stochastic Gradient Algorithms
• On the parallelization upper bound for asynchronous stochastic gradients descent in non-convex optimization
• Convergence and convergence rate of stochastic gradient search in the case of multiple and non-isolated extrema

Cited in

(7)

• On the Rate of Convergence of a Partially Asynchronous Gradient Projection Algorithm
• Stochastic modified equations for the asynchronous stochastic gradient descent
• Group stochastic gradient descent: a tradeoff between straggler and staleness
• The error-feedback framework: SGD with delayed gradients
• The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• Asynchronous SGD with stale gradient dynamic adjustment for deep learning training

This page was built for publication: A sharp convergence rate for a model equation of the asynchronous stochastic gradient descent

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