Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
arXiv:1705.10464
Abstract
We consider a large-scale matrix multiplication problem where the computation is carried out using a distributed system with a master node and multiple worker nodes, where each worker can store parts of the input matrices. We propose a computation strategy that leverages ideas from coding theory to design intermediate computations at the worker nodes, in order to efficiently deal with straggling workers. The proposed strategy, named as \emph{polynomial codes}, achieves the optimum recovery threshold, defined as the minimum number of workers that the master needs to wait for in order to compute the output. Furthermore, by leveraging the algebraic structure of polynomial codes, we can map the reconstruction problem of the final output to a polynomial interpolation problem, which can be solved efficiently. Polynomial codes provide order-wise improvement over the state of the art in terms of recovery threshold, and are also optimal in terms of several other metrics. Furthermore, we extend this code to distributed convolution and show its order-wise optimality.
References in corpus (3)
Cited by in corpus (48)
- FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
- Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy
- Coded Sparse Matrix Multiplication
- 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
- Straggler-aware Distributed Learning: Communication Computation Latency Trade-off
- Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding
- Learning a Code: Machine Learning for Approximate Non-Linear Coded Computation
- Fundamental Limits of Coded Linear Transform
- Robust Gradient Descent via Moment Encoding with LDPC Codes
- On the Capacity of Secure Distributed Matrix Multiplication
- Adaptive Verifiable Coded Computing: Towards Fast, Secure and Private Distributed Machine Learning
- Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier
- Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks
- Cross Subspace Alignment Codes for Coded Distributed Batch Computation
- Double Blind -Private Information Retrieval
- On the Capacity of Secure Distributed Batch Matrix Multiplication
- Bivariate Polynomial Codes for Secure Distributed Matrix Multiplication
- Straggler-Resilient and Communication-Efficient Distributed Iterative Linear Solver
- A Systematic Approach towards Efficient Private Matrix Multiplication
- Parity Models: A General Framework for Coding-Based Resilience in ML Inference
- Secure Coded Multi-Party Computation for Massive Matrix Operations
- Coded Computing for Federated Learning at the Edge
- Robust and Communication-Efficient Collaborative Learning
- Coded Fourier Transform
- Coded Iterative Computing using Substitute Decoding
- Efficient Recovery of a Shared Secret via Cooperation: Applications to SDMM and PIR
- A Sequential Approximation Framework for Coded Distributed Optimization
- Coded FFT and Its Communication Overhead
- Diversity/Parallelism Trade-off in Distributed Systems with Redundancy
- Private Coded Computation for Machine Learning
- Collage Inference: Using Coded Redundancy for Low Variance Distributed Image Classification
- Optimal Load Allocation for Coded Distributed Computation in Heterogeneous Clusters
- Edge Computing in the Dark: Leveraging Contextual-Combinatorial Bandit and Coded Computing
- Improved Constructions for Secure Multi-Party Batch Matrix Multiplication
- Transition Waste Optimization for Coded Elastic Computing
- GCSA Codes with Noise Alignment for Secure Coded Multi-Party Batch Matrix Multiplication
- Cascaded Coded Distributed Computing Schemes Based on Placement Delivery Arrays
- LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning
- Adaptive Gradient Coding
- Coded Elastic Computing
- Compressed Coded Distributed Computing
- Optimum Transmission Delay for Function Computation in NFV-based Networks: the role of Network Coding and Redundant Computing
- Low-bandwidth recovery of linear functions of Reed-Solomon-encoded data
- Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication
- Coded Computing for Secure Boolean Computations
- A Fundamental Storage-Communication Tradeoff for Distributed Computing with Straggling Nodes