Asynchronous Distributed Optimization with Stochastic Delays

We study asynchronous finite sum minimization in a distributed-data setting with a central parameter server. While asynchrony is well understood in parallel settings where the data is accessible by all machines -- e.g., modifications of variance-reduced gradient algorithms like SAGA work well -- little is known for the distributed-data setting. We develop an algorithm ADSAGA based on SAGA for the distributed-data setting, in which the data is partitioned between many machines. We show that with m machines, under a natural stochastic delay model with an mean delay of m, ADSAGA converges in tildeOleft(left(n + √mkapparight)log(1/ε)right) iterations, where n is the number of component functions, and kappa is a condition number. This complexity sits squarely between the complexity tildeOleft(left(n + kapparight)log(1/ε)right) of SAGA textitwithout delays and the complexity tildeOleft(left(n + mkapparight)log(1/ε)right) of parallel asynchronous algorithms where the delays are textitarbitrary (but bounded by O(m)), and the data is accessible by all. Existing asynchronous algorithms with distributed-data setting and arbitrary delays have only been shown to converge in tildeO(n2kappalog(1/ε)) iterations. We empirically compare on least-squares problems the iteration complexity and wallclock performance of ADSAGA to existing parallel and distributed algorithms, including synchronous minibatch algorithms. Our results demonstrate the wallclock advantage of variance-reduced asynchronous approaches over SGD or synchronous approaches.