Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers

Abstract

We consider the setting where a master wants to run a distributed stochastic gradient descent (SGD) algorithm on $n$ workers each having a subset of the data. Distributed SGD may suffer from the effect of stragglers, i.e., slow or unresponsive workers who cause delays. One solution studied in the literature is to wait at each iteration for the responses of the fastest $k<n$ workers before updating the model, where $k$ is a fixed parameter. The choice of the value of $k$ presents a trade-off between the runtime (i.e., convergence rate) of SGD and the error of the model. Towards optimizing the error-runtime trade-off, we investigate distributed SGD with adaptive $k$. We first design an adaptive policy for varying $k$ that optimizes this trade-off based on an upper bound on the error as a function of the wall-clock time which we derive. Then, we propose an algorithm for adaptive distributed SGD that is based on a statistical heuristic. We implement our algorithm and provide numerical simulations which confirm our intuition and theoretical analysis.

arXiv commentAccepted to IEEE ICASSP 2020

References in corpus (17)

• Speeding Up Distributed Machine Learning Using Codes
• Revisiting Distributed Synchronous SGD
• Don't Decay the Learning Rate, Increase the Batch Size
• Optimal Distributed Online Prediction using Mini-Batches
• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Communication-Computation Efficient Gradient Coding
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Minimizing Latency for Secure Distributed Computing
• Straggler Mitigation in Distributed Optimization Through Data Encoding
• Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
• Approximate Gradient Coding via Sparse Random Graphs
• Robust Gradient Descent via Moment Encoding with LDPC Codes
• CYCLADES: Conflict-free Asynchronous Machine Learning
• Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD
• Anytime Stochastic Gradient Descent: A Time to Hear from all the Workers

Cited by in corpus (1)

• Taming Momentum in a Distributed Asynchronous Environment