Speeding up Distributed Machine Learning Using Codes

Jump to other IT Society Websites:

Speeding up Distributed Machine Learning Using Codes

Author(s):

Creation Date: Aug 04, 2017

Published In: Mar 2018

Paper Type: Journal Article

Book Title: IEEE Transactions on Information Theory

Abstract:

Codes are widely used in many engineering applications to offer robustness against noise. In large-scale systems, there are several types of noise that can affect the performance of distributed machine learning algorithms-straggler nodes, system failures, or communication bottlenecks-but there has been little interaction cutting across codes, machine learning, and distributed systems. In this paper, we provide theoretical insights on how coded solutions can achieve significant gains compared with uncoded ones. We focus on two of the most basic building blocks of distributed learning algorithms: matrix multiplication and data shuffling. For matrix multiplication, we use codes to alleviate the effect of stragglers and show that if the number of homogeneous workers is n, and the runtime of each subtask has an exponential tail, coded computation can speed up distributed matrix multiplication by a factor of log n. For data shuffling, we use codes to reduce communication bottlenecks, exploiting the excess in storage. We show that when a constant fraction α of the data matrix can be cached at each worker, and n is the number of workers, coded shuffling reduces the communication cost by a factor of (α+ n/1)y (n) compared with uncoded shuffling, where y (n) is the ratio of the cost of unicasting n messages to n users to multicasting a common message (of the same size) to n users. For instance, y (n) ≃ n if multicasting a message to n users is as cheap as unicasting a message to one user. We also provide experimental results, corroborating our theoretical gains of the coded algorithms.

IEEE Explore link: https://ieeexplore.ieee.org/document/8002642

Award(s) Received:

COVID-19 Updates

Read important changes and updates to the 2020 activities of the IEEE Information Theory Society due to the COVID-19 pandemic at:

https://www.itsoc.org/covid

 

Table of Contents

IEEE TechNav