OverSketch: Approximate Matrix Multiplication for the Cloud
arXiv:1811.02653 · doi:10.1109/BigData.2018.8622139
Abstract
We propose OverSketch, an approximate algorithm for distributed matrix multiplication in serverless computing. OverSketch leverages ideas from matrix sketching and high-performance computing to enable cost-efficient multiplication that is resilient to faults and straggling nodes pervasive in low-cost serverless architectures. We establish statistical guarantees on the accuracy of OverSketch and empirically validate our results by solving a large-scale linear program using interior-point methods and demonstrate a 34% reduction in compute time on AWS Lambda.
Published in Proc. IEEE Big Data 2018. Updated version provides details of distributed sketching and highlights other advantages of OverSketch
References in corpus (10)
- Speeding Up Distributed Machine Learning Using Codes
- Sketching as a Tool for Numerical Linear Algebra
- Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
- Fast approximation of matrix coherence and statistical leverage
- numpywren: serverless linear algebra
- Serverless Computing: Current Trends and Open Problems
- OverSketch: Approximate Matrix Multiplication for the Cloud
- Occupy the Cloud: Distributed Computing for the 99%
- A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
- Randomized sketches for kernels: Fast and optimal non-parametric regression
Cited by in corpus (8)
- Function-as-a-Service Performance Evaluation: A Multivocal Literature Review
- OverSketch: Approximate Matrix Multiplication for the Cloud
- A Survey of Coded Distributed Computing
- Secure Coded Multi-Party Computation for Massive Matrix Operations
- Serverless Straggler Mitigation using Local Error-Correcting Codes
- LocalNewton: Reducing Communication Bottleneck for Distributed Learning
- Parity-Checked Strassen Algorithm
- Utility-based Resource Allocation and Pricing for Serverless Computing