ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding

2019/01/28 by Hongyi Wang, Zachary Charles, Wang, Hongyi +3 · 2 citations
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.1901.09671

Abstract

We present ErasureHead, a new approach for distributed gradient descent (GD) that mitigates system delays by employing approximate gradient coding. Gradient coded distributed GD uses redundancy to exactly recover the gradient at each iteration from a subset of compute nodes. ErasureHead instead uses approximate gradient codes to recover an inexact gradient at each iteration, but with higher delay tolerance. Unlike prior work on gradient coding, we provide a performance analysis that combines both delay and convergence guarantees. We establish that down to a small noise floor, ErasureHead converges as quickly as distributed GD and has faster overall runtime under a probabilistic delay model. We conduct extensive experiments on real world datasets and distributed clusters and demonstrate that our method can lead to significant speedups over both standard and gradient coded GD.

Citations

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

Cited by

• LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning
• Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers

Related

• Distributed Gradient Descent with Coded Partial Gradient Computations
• CD-SGD: Distributed Stochastic Gradient Descent with Compression and Delay Compensation
• Speeding Up Distributed Gradient Descent by Utilizing Non-persistent Stragglers
• Improving Distributed Gradient Descent Using Reed-Solomon Codes
• Fundamental Limits of Approximate Gradient Coding