Robust Gradient Descent via Moment Encoding with LDPC Codes

Abstract

This paper considers the problem of implementing large-scale gradient descent algorithms in a distributed computing setting in the presence of {\em straggling} processors. To mitigate the effect of the stragglers, it has been previously proposed to encode the data with an erasure-correcting code and decode at the master server at the end of the computation. We, instead, propose to encode the second-moment of the data with a low density parity-check (LDPC) code. The iterative decoding algorithms for LDPC codes have very low computational overhead and the number of decoding iterations can be made to automatically adjust with the number of stragglers in the system. We show that for a random model for stragglers, the proposed moment encoding based gradient descent method can be viewed as the stochastic gradient descent method. This allows us to obtain convergence guarantees for the proposed solution. Furthermore, the proposed moment encoding based method is shown to outperform the existing schemes in a real distributed computing setup.

References in corpus (6)

• Speeding Up Distributed Machine Learning Using Codes
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Minimizing Latency for Secure Distributed Computing
• Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
• Approximate Gradient Coding via Sparse Random Graphs
• Coding Method for Parallel Iterative Linear Solver

Cited by in corpus (13)

• Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air
• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
• Computation Scheduling for Distributed Machine Learning with Straggling Workers
• Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding
• Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers
• Coded Computing for Distributed Graph Analytics
• Straggler-Resilient and Communication-Efficient Distributed Iterative Linear Solver
• Distributed Stochastic Gradient Descent Using LDGM Codes
• Coded Iterative Computing using Substitute Decoding
• A New Combinatorial Coded Design for Heterogeneous Distributed Computing
• MDS coding is better than replication for job completion times
• Heterogeneity-aware Gradient Coding for Straggler Tolerance
• A Practical Algorithm Design and Evaluation for Heterogeneous Elastic Computing with Stragglers