Approximate Distributed Coded Computing: Polynomial Codes and Randomized Sketching

• URL: http://arxiv.org/abs/2605.16744v1
• Date: Sat, 16 May 2026 01:50:27 GMT
• Title: Approximate Distributed Coded Computing: Polynomial Codes and Randomized Sketching
• Abstract summary: Coded computing is a distributed paradigm that uses coding theory to introduce textitredundancy and overcome bottlenecks in large-scale systems.<n>In the same vein, randomized numerical linear algebra employs probabilistic methods to textitcompress and accelerate linear algebraic operations.<n>This article reviews the foundations of both fields and presents distributed schemes that combine techniques from both to speed up optimization and machine learning algorithms.
• Score: 22.19006991194303
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Coded computing is a distributed paradigm that uses coding theory to introduce \textit{redundancy} and overcome bottlenecks in large-scale systems. In the same vein, randomized numerical linear algebra employs probabilistic methods to \textit{compress} and accelerate linear algebraic operations, addressing challenges in high-dimensional data analysis. This article reviews the foundations of both fields and presents distributed schemes that combine techniques from both to speed up optimization and machine learning algorithms, in the presence of slow or non-responsive servers. Along the way, we touch on various related topics and mathematical concepts.

Related papers

• Kernel Methods for Learning Operators with Multiple Inputs and Outputs [0.5249805590164902]
  We introduce a kernel-based encoder-decoder framework for operator learning that separates observation, representation, learning, and reconstruction.<n>We develop this framework for multi-input, multi-output operator learning, where operators map between products of potentially distinct function spaces.<n>We specialize the approach to multiple operator learning by introducing KernelMO, a family of kernel methods with complementary operator-valued and product-space formulations.
  arXiv  Detail & Related papers  (2026-08-12T09:15:20Z)
• Topology Identification and Inference over Graphs [61.06365536861156]
  Topology identification and inference of processes evolving over graphs arise in timely applications involving brain, transportation, financial, power, as well as social and information networks.<n>This chapter provides an overview of graph topology identification and statistical inference methods for multidimensional data.
  arXiv  Detail & Related papers  (2025-12-11T00:47:09Z)
• Scalable Gaussian Processes: Advances in Iterative Methods and Pathwise Conditioning [0.26107298043931204]
  This dissertation focuses on the powerful combination of iterative methods and pathwise conditioning to develop methodological contributions.<n>By combining these two techniques, expensive computations are expressed as solutions to systems of linear equations and obtained by leveraging iterative linear system solvers.<n>This drastically reduces memory requirements, facilitating application to significantly larger amounts of data, and introduces matrix multiplication as the main computational operation.
  arXiv  Detail & Related papers  (2025-07-09T13:39:37Z)
• Similarity-based fuzzy clustering scientific articles: potentials and challenges from mathematical and computational perspectives [0.0]
  Fuzzy clustering plays a vital role in analyzing publication data.<n>This problem can be formulated as a constrained optimization model, where the goal is to minimize the discrepancy between the similarity observed from data and the similarity derived from a predicted distribution.<n>We analyze potentials and challenges of the approach from both mathematical and computational perspectives.
  arXiv  Detail & Related papers  (2025-06-04T15:10:31Z)
• Optimal Transport for Machine Learners [23.03787751696068]
  Optimal Transport is a foundational mathematical theory that connects optimization, partial differential equations, and probability.<n>These course notes cover the fundamental mathematical aspects of OT, including the Monge and Kantorovich formulations.<n> Applications in machine learning include topics like training neural networks via gradient flows, token dynamics in transformers, and the structure of GANs and diffusion models.
  arXiv  Detail & Related papers  (2025-05-10T10:35:03Z)
• Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning [49.0767291348921]
  Randomized Numerical Linear Algebra (RandNLA) is an area which uses randomness to develop improved algorithms for ubiquitous matrix problems. This article provides a self-contained overview of RandNLA, in light of these developments.
  arXiv  Detail & Related papers  (2024-06-17T02:30:55Z)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  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. We propose a sequential decoding algorithm designed to handle real valued data while maintaining low computational complexity for recovery. We demonstrate the potential applications of this framework in various contexts, such as large-scale matrix multiplication and black-box optimization.
  arXiv  Detail & Related papers  (2023-09-01T18:02:04Z)
• Linear Self-Attention Approximation via Trainable Feedforward Kernel [77.34726150561087]
  In pursuit of faster computation, Efficient Transformers demonstrate an impressive variety of approaches. We aim to expand the idea of trainable kernel methods to approximate the self-attention mechanism of the Transformer architecture.
  arXiv  Detail & Related papers  (2022-11-08T08:14:11Z)
• A Learning-Based Approach to Approximate Coded Computation [22.886991943938703]
  We propose AICC, an AI-aided learning approach that is inspired by LCC but also uses deep neural networks (DNNs) It is appropriate for coded computation of more general functions.
  arXiv  Detail & Related papers  (2022-05-19T19:43:53Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• A Survey on Large-scale Machine Learning [67.6997613600942]
  Machine learning can provide deep insights into data, allowing machines to make high-quality predictions. Most sophisticated machine learning approaches suffer from huge time costs when operating on large-scale data. Large-scale Machine Learning aims to learn patterns from big data with comparable performance efficiently.
  arXiv  Detail & Related papers  (2020-08-10T06:07:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.