Asynchronous Distributed Optimization with Stochastic Delays

Abstract

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 $\tilde{O}\left(\left(n+\sqrt{m}\kappa \right)\log (1/\epsilon )\right)$ iterations, where $n$ is the number of component functions, and $\kappa$ is a condition number. This complexity sits squarely between the complexity $\tilde{O}\left(\left(n+\kappa \right)\log (1/\epsilon )\right)$ of SAGA \textit{without delays} and the complexity $\tilde{O}\left(\left(n+m\kappa \right)\log (1/\epsilon )\right)$ of parallel asynchronous algorithms where the delays are \textit{arbitrary} (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 $\tilde{O}(n^2\kappa \log (1/\epsilon ))$ 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.

arXiv commentarXiv admin note: substantial text overlap with arXiv:2006.09638

References in corpus (14)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Optimal Distributed Online Prediction using Mini-Batches
• Federated Optimization in Heterogeneous Networks
• Asynchronous Federated Optimization
• A Universal Catalyst for First-Order Optimization
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server
• A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates
• Advances in Asynchronous Parallel and Distributed Optimization
• Improving SAGA via a Probabilistic Interpolation with Gradient Descent

Cited by in corpus (1)

• Fast Federated Learning in the Presence of Arbitrary Device Unavailability