Speeding Up Distributed Machine Learning Using Codes

DOI10.1109/TIT.2017.2736066MaRDI QIDQ4566725zbMATH OpenFDO

Authors Kangwook Lee, Maximilian Lam, Ramtin Pedarsani, Dimitris S. Papailiopoulos, Kannan Ramchandran

Publication date 27 June 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.02673

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Learning and adaptive systems in artificial intelligence (68T05) Linear codes (general theory) (94B05)

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 work, we provide theoretical insights on how coded solutions can achieve significant gains compared to 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 $logn$. For data shuffling, we use codes to reduce communication bottlenecks, exploiting the excess in storage. We show that when a constant fraction $alpha$ of the data matrix can be cached at each worker, and $n$ is the number of workers, emph{coded shuffling} reduces the communication cost by a factor of $(alpha+frac1n)gamma(n)$ compared to uncoded shuffling, where $gamma(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, $gamma(n)simeqn$ if multicasting a message to $n$ users is as cheap as unicasting a message to one user. We also provide experiment results, corroborating our theoretical gains of the coded algorithms.

Cited in

(7)

• MDS coding is better than replication for job completion times
• Coded Computing: Mitigating Fundamental Bottlenecks in Large-Scale Distributed Computing and Machine Learning
• Near Optimal Coded Data Shuffling for Distributed Learning
• Redundancy techniques for straggler mitigation in distributed optimization and learning
• Composite optimization with coupling constraints via dual proximal gradient method with applications to asynchronous networks
• Linear operator approximate message passing (OpAMP)
• Near-optimal fault tolerance for efficient batch matrix multiplication via an additive combinatorics lens

This page was built for publication: Speeding Up Distributed Machine Learning Using Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566725)