2023/09/01 by Burak Bartan, Bartan, Burak, Mert Pilancı +1
Computer Science · Engineering · #Distributed #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Parallel #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2309.00682
openalex publication_date 2023/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.