# OverSketch: Approximate Matrix Multiplication for the Cloud

arXiv: https://arxiv.org/abs/1811.02653 · HTML: https://mlsanity.com/paper/1811.02653/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2018.

## Built on by (most cited first, 10 of 10)

- [LocalNewton: Reducing Communication Bottleneck for Distributed Learning](https://mlsanity.com/paper/2105.07320/) (2021)
- [ApproxIFER: A Model-Agnostic Approach to Resilient and Robust Prediction Serving Systems](https://mlsanity.com/paper/2109.09868/) (2021)
- [Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework](https://mlsanity.com/paper/2406.00300/) (2024)
- [General Coded Computing: Adversarial Settings](https://mlsanity.com/paper/2502.08058/) (2025)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [Randomized Polar Codes for Anytime Distributed Machine Learning](https://mlsanity.com/paper/2309.00682/) (2023)
- [A Learning-Based Approach to Approximate Coded Computation](https://mlsanity.com/paper/2205.09818/) (2022)
- [Optimal Approximate Matrix Multiplication over Sliding Windows](https://mlsanity.com/paper/2502.18830/) (2025)
- [High-Performance Serverless Computing: A Systematic Literature Review on Serverless for HPC, AI, and Big Data](https://mlsanity.com/paper/2601.09334/) (2026)
- [Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting](https://mlsanity.com/paper/2608.28910/) (2026)

## Abstract (arXiv)

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.