@inproceedings{
tyurin2024on,
title={On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization},
author={Alexander Tyurin and Peter Richt{\'a}rik},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=IXRa8adMHX}
}
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 by constants. After that, we developed a new nearly optimal method, Fragile SGD, and a new optimal method, Amelie SGD, that converge with 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.
On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization
Alexander Tyurin Peter Richtárik