  We consider the decentralized stochastic asynchronous optimization setup,
where many workers asynchronously calculate stochastic gradients and
asynchronously communicate with each other using edges in a multigraph. For
both homogeneous and heterogeneous setups, we prove new time complexity lower
bounds under the assumption that computation and communication speeds are
bounded. We develop a new nearly optimal method, Fragile SGD, and a new optimal
method, Amelie SGD, that converge under arbitrary heterogeneous computation and
communication speeds and match our lower bounds (up to a logarithmic factor in
the homogeneous setting). Our time complexities are new, nearly optimal, and
provably improve all previous asynchronous/synchronous stochastic methods in
the decentralized setup.
