2024/05/25 by Alexander Tyurin, Peter Richtárik, Tyurin, Alexander +1 · 5 citations
Business, Management and Accounting · Engineering · #Advanced Queuing Theory Analysis #FOS: Mathematics #Optimization and Control (math.OC) #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2405.16218
openalex publication_date 2024/05/25 · openalex created_date 2024/05/29 · openalex updated_date 2026/07/28
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.