# Randomized Polar Codes for Anytime Distributed Machine Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 1 Sep 2023.

## Builds on (most cited first, 19 of 19)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing](https://mlsanity.com/paper/2009.08327/) (2020)
- [Fundamental Limits of Approximate Gradient Coding](https://mlsanity.com/paper/1901.08166/) (2019)
- [Coded Computation over Heterogeneous Clusters](https://mlsanity.com/paper/1701.05973/) (2017)
- [OverSketch: Approximate Matrix Multiplication for the Cloud](https://mlsanity.com/paper/1811.02653/) (2018)
- [Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier](https://mlsanity.com/paper/2001.05101/) (2020)
- [OverSketched Newton: Fast Convex Optimization for Serverless Systems](https://mlsanity.com/paper/1903.08857/) (2019)
- [Rateless Codes for Near-Perfect Load Balancing in Distributed Matrix-Vector Multiplication](https://mlsanity.com/paper/1804.10331/) (2018)
- [Block-Diagonal and LT Codes for Distributed Computing With Straggling Servers](https://mlsanity.com/paper/1712.08230/) (2017)
- [Low rank approximation and decomposition of large matrices using error correcting codes](https://mlsanity.com/paper/1512.09156/) (2015)
- [Utility-based Resource Allocation and Pricing for Serverless Computing](https://mlsanity.com/paper/2008.07793/) (2020)
- [Distributed Computations with Layered Resolution](https://mlsanity.com/paper/2208.01437/) (2022)
- [Distributed Black-Box Optimization via Error Correcting Codes](https://mlsanity.com/paper/1907.05984/) (2019)
- [Computational Polarization: An Information-theoretic Method for Resilient Computing](https://mlsanity.com/paper/2109.03877/) (2021)

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

- [Successive Refinement in Large-Scale Computation: Advancing Model Inference Applications](https://mlsanity.com/paper/2402.07229/) (2024)

## Abstract (arXiv)

We present a novel distributed computing framework that is robust to slow compute nodes, and is capable of both approximate and exact computation of linear operations. The proposed mechanism integrates the concepts of randomized sketching and polar codes in the context of coded computation. We propose a sequential decoding algorithm designed to handle real valued data while maintaining low computational complexity for recovery. Additionally, we provide an anytime estimator that can generate provably accurate estimates even when the set of available node outputs is not decodable. We demonstrate the potential applications of this framework in various contexts, such as large-scale matrix multiplication and black-box optimization. We present the implementation of these methods on a serverless cloud computing system and provide numerical results to demonstrate their scalability in practice, including ImageNet scale computations.