Speeding Up Distributed Machine Learning Using Codes

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 $\log n$. 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 +\frac{1}{n})\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)\simeq n$ 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.

This work is published in IEEE Transactions on Information Theory and presented in part at the NIPS 2015 Workshop on Machine Learning Systems and the IEEE ISIT 2016

References in corpus (16)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• MLlib: Machine Learning in Apache Spark
• Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction
• XORing Elephants: Novel Erasure Codes for Big Data
• Why Random Reshuffling Beats Stochastic Gradient Descent
• Distributed Delayed Stochastic Optimization
• Minimizing Latency for Secure Distributed Computing
• Optimal Repair of MDS Codes in Distributed Storage via Subspace Interference Alignment
• Codes with Local Regeneration
• Provably Delay Efficient Data Retrieving in Storage Clouds
• MDS Array Codes with Optimal Rebuilding
• A Fundamental Tradeoff between Computation and Communication in Distributed Computing
• Fundamental Limits of Distributed Caching in D2D Wireless Networks
• Codes Can Reduce Queueing Delay in Data Centers
• A Pliable Index Coding Approach to Data Shuffling
• Gradient Coding

Cited by in corpus (150)

• Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
• An Exact Quantized Decentralized Gradient Descent Algorithm
• Coded Computing for Low-Latency Federated Learning over Wireless Edge Networks
• Coded Sparse Matrix Multiplication
• Minimizing Latency for Secure Distributed Computing
• Coded Federated Learning
• Computation Scheduling for Distributed Machine Learning with Straggling Workers
• Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
• OverSketch: Approximate Matrix Multiplication for the Cloud
• CSAFL: A Clustered Semi-Asynchronous Federated Learning Framework
• Straggler-aware Distributed Learning: Communication Computation Latency Trade-off
• Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• On Delay-Optimal Scheduling in Queueing Systems with Replications
• Boomerang: Redundancy Improves Latency and Throughput in Payment-Channel Networks
• Fundamental Limits of Coded Linear Transform
• Hierarchical Coded Matrix Multiplication
• Robust Gradient Descent via Moment Encoding with LDPC Codes
• Stochastic Learning under Random Reshuffling with Constant Step-sizes
• Adaptive Verifiable Coded Computing: Towards Fast, Secure and Private Distributed Machine Learning
• A Fundamental Tradeoff between Computation and Communication in Distributed Computing
• FLeet: Online Federated Learning via Staleness Awareness and Performance Prediction
• Communication-Efficient Edge AI: Algorithms and Systems
• Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks
• Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier
• Private and Secure Distributed Matrix Multiplication Schemes for Replicated or MDS-Coded Servers
• Cross Subspace Alignment Codes for Coded Distributed Batch Computation
• A Survey of Coded Distributed Computing
• CodedReduce: A Fast and Robust Framework for Gradient Aggregation in Distributed Learning
• Coded Computation across Shared Heterogeneous Workers with Communication Delay
• A Unified Coding Framework for Distributed Computing with Straggling Servers
• Straggler Mitigation with Tiered Gradient Codes
• Optimal Server Selection for Straggler Mitigation
• Bivariate Polynomial Coding for Efficient Distributed Matrix Multiplication
• Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers
• Bivariate Polynomial Codes for Secure Distributed Matrix Multiplication
• Coded Computing for Distributed Graph Analytics
• Joint Device Scheduling and Resource Allocation for Latency Constrained Wireless Federated Learning
• On the Fundamental Limits of Coded Data Shuffling for Distributed Machine Learning
• Straggler-Resilient and Communication-Efficient Distributed Iterative Linear Solver
• Gradient Coding via the Stochastic Block Model
• Federated Optimization of Smooth Loss Functions
• A Systematic Approach towards Efficient Private Matrix Multiplication
• Hierarchical coded elastic computing
• Secure Coded Multi-Party Computation for Massive Matrix Operations
• Parity Models: A General Framework for Coding-Based Resilience in ML Inference
• Coded Computing for Federated Learning at the Edge
• The Optimal Memory-Rate Trade-off for the Non-uniform Centralized Caching Problem with Two Files under Uncoded Placement
• Combating Computational Heterogeneity in Large-Scale Distributed Computing via Work Exchange
• Robust and Communication-Efficient Collaborative Learning
• A locality-based approach for coded computation
• Coding Method for Parallel Iterative Linear Solver
• Coded Fourier Transform
• Wireless for Machine Learning
• Distributed Stochastic Gradient Descent Using LDGM Codes
• DxPU: Large Scale Disaggregated GPU Pools in the Datacenter
• Coded Federated Computing in Wireless Networks with Straggling Devices and Imperfect CSI
• Private Secure Coded Computation
• Rateless Codes for Private Distributed Matrix-Matrix Multiplication
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning
• The Capacity of 3 User Linear Computation Broadcast
• A New Combinatorial Coded Design for Heterogeneous Distributed Computing
• Coded FFT and Its Communication Overhead
• A Sequential Approximation Framework for Coded Distributed Optimization
• Serverless Straggler Mitigation using Local Error-Correcting Codes
• Exploiting Computation Replication for Mobile Edge Computing: A Fundamental Computation-Communication Tradeoff Study
• MDS coding is better than replication for job completion times
• Latency optimal storage and scheduling of replicated fragments for memory-constrained servers
• Diversity/Parallelism Trade-off in Distributed Systems with Redundancy
• Communication-Aware Scheduling of Serial Tasks for Dispersed Computing
• Distributed Averaging Methods for Randomized Second Order Optimization
• Wireless Map-Reduce Distributed Computing with Full-Duplex Radios and Imperfect CSI
• CodeNet: Training Large Scale Neural Networks in Presence of Soft-Errors
• Wireless MapReduce Distributed Computing
• Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation
• Improved Constructions for Secure Multi-Party Batch Matrix Multiplication
• GCSA Codes with Noise Alignment for Secure Coded Multi-Party Batch Matrix Multiplication
• Composite Optimization with Coupling Constraints via Dual Proximal Gradient Method with Applications to Asynchronous Networks
• Distributed Machine Learning for Wireless Communication Networks: Techniques, Architectures, and Applications
• Edge Computing in the Dark: Leveraging Contextual-Combinatorial Bandit and Coded Computing
• Transition Waste Optimization for Coded Elastic Computing
• Coded Computing for Master-Aided Distributed Computing Systems
• Parity-Checked Strassen Algorithm
• On Large-Cohort Training for Federated Learning
• $C^{3}LES$: Codes for Coded Computation that Leverage Stragglers
• Distributed Task Replication for Vehicular Edge Computing: Performance Analysis and Learning-based Algorithm
• Optimal Load Allocation for Coded Distributed Computation in Heterogeneous Clusters
• Storage, Computation, and Communication: A Fundamental Tradeoff in Distributed Computing
• Optimizing Redundancy Levels in Master-Worker Compute Clusters for Straggler Mitigation
• Anytime Stochastic Gradient Descent: A Time to Hear from all the Workers
• A Scalable Framework for Wireless Distributed Computing
• Heterogeneity-aware Gradient Coding for Straggler Tolerance
• Cascaded Coded Distributed Computing Schemes Based on Placement Delivery Arrays
• Straggler-resistant distributed matrix computation via coding theory
• Adaptive Gradient Coding
• A Practical Algorithm Design and Evaluation for Heterogeneous Elastic Computing with Stragglers
• Timely-Throughput Optimal Coded Computing over Cloud Networks
• Heterogeneous Coded Computation across Heterogeneous Workers
• Cuboid Partitioning for Hierarchical Coded Matrix Multiplication
• Rateless Codes for Low-Latency Distributed Inference in Mobile Edge Computing
• Asynchronous Distributed Optimization with Redundancy in Cost Functions
• Incentive Mechanism Design for Distributed Coded Machine Learning
• Redundancy Scheduling in Systems with Bi-Modal Job Service Time Distribution
• LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning
• Load balancing policies without feedback using timed replicas
• A Droplet Approach Based on Raptor Codes for Distributed Computing With Straggling Servers
• Coded Alternating Least Squares for Straggler Mitigation in Distributed Recommendations
• Price of Precision in Coded Distributed Matrix Multiplication: A Dimensional Analysis
• Coded Elastic Computing on Machines with Heterogeneous Storage and Computation Speed
• Harmonic Coding: An Optimal Linear Code for Privacy-Preserving Gradient-Type Computation
• On the Capacity of Computation Broadcast
• Storage Codes with Flexible Number of Nodes
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing
• Compressed Coded Distributed Computing
• Coded Elastic Computing
• Erasure coding for distributed matrix multiplication for matrices with bounded entries
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping
• Coding for Distributed Multi-Agent Reinforcement Learning
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Anytime Minibatch with Delayed Gradients
• On Locally Decodable Index Codes
• Folded Polynomial Codes for Coded Distributed $A{A}^{\top }$-Type Matrix Multiplication
• Linear Operator Approximate Message Passing (OpAMP)
• Fault-Tolerant Strassen-Like Matrix Multiplication
• Jointly Optimize Coding and Node Selection for Distributed Computing over Wireless Edge Networks
• Capacity-achieving Polar-based LDGM Codes
• An Umbrella Converse for Data Exchange: Applied to Caching, Computing, and Shuffling
• Coded-InvNet for Resilient Prediction Serving Systems
• Coded Computing and Cooperative Transmission for Wireless Distributed Matrix Multiplication
• Modeling Performance and Energy trade-offs in Online Data-Intensive Applications
• Optimization-based Block Coordinate Gradient Coding
• Decentralized Learning of Tree-Structured Gaussian Graphical Models from Noisy Data
• Coded Computing for Secure Boolean Computations
• Optimal Coding Scheme and Resource Allocation for Distributed Computation with Limited Resources
• Taming Time-Varying Information Asymmetry in Fresh Status Acquisition
• Creating Robust Deep Neural Networks With Coded Distributed Computing for IoT Systems
• Multi-Agent Reinforcement Learning Based Coded Computation for Mobile Ad Hoc Computing
• Improved Computation-Communication Trade-Off for Coded Distributed Computing using Linear Dependence of Intermediate Values
• GraphFederator: Federated Visual Analysis for Multi-party Graphs
• A Fundamental Storage-Communication Tradeoff for Distributed Computing with Straggling Nodes
• Heterogeneous Computation Assignments in Coded Elastic Computing
• Coded Distributed Computing over Packet Erasure Channels
• Coded Matrix Multiplication on a Group-Based Model
• Coded Computation Against Distributed Straggling Channel Decoders in the Cloud for Gaussian Uplink Channels
• On Model Coding for Distributed Inference and Transmission in Mobile Edge Computing Systems
• Coded State Machine -- Scaling State Machine Execution under Byzantine Faults
• Subspace-Aware Index Codes