  We analyze asynchronous-type algorithms for distributed SGD in the
heterogeneous setting, where each worker has its own computation and
communication speeds, as well as data distribution. In these algorithms,
workers compute possibly stale and stochastic gradients associated with their
local data at some iteration back in history and then return those gradients to
the server without synchronizing with other workers. We present a unified
convergence theory for non-convex smooth functions in the heterogeneous regime.
The proposed analysis provides convergence for pure asynchronous SGD and its
various modifications. Moreover, our theory explains what affects the
convergence rate and what can be done to improve the performance of
asynchronous algorithms. In particular, we introduce a novel asynchronous
method based on worker shuffling. As a by-product of our analysis, we also
demonstrate convergence guarantees for gradient-type algorithms such as SGD
with random reshuffling and shuffle-once mini-batch SGD. The derived rates
match the best-known results for those algorithms, highlighting the tightness
of our approach. Finally, our numerical evaluations support theoretical
findings and show the good practical performance of our method.
