Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting

• URL: http://arxiv.org/abs/2608.28910v1
• Date: Fri, 28 Aug 2026 22:18:22 GMT
• Title: Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting
• Abstract summary: Coded computing has emerged as a powerful paradigm for mitigating the impact of straggling workers in distributed computing systems.<n>General Coded Computing (GCC) formulates coded computing through a natural end-to-end mean-squared error loss.<n>We establish theoretical performance under two complementary straggler regimes.
• Score: 21.347076448562863
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Coded computing has emerged as a powerful paradigm for mitigating the impact of straggling workers in distributed computing systems. However, existing coded-computing schemes are predominantly designed for the exact recovery of highly structured computations, such as polynomial evaluation and matrix multiplication, and typically rely on strict recovery thresholds. These assumptions significantly limit their applicability to modern machine-learning workloads, particularly deep neural networks (DNNs), whose computations generally lack rigid algebraic structure and, in many applications, require only accurate approximations rather than exact recovery. To address this gap, we revisit coded computing from a learning-theoretic perspective and introduce General Coded Computing (GCC). Rather than adopting existing algebraic tools, GCC formulates coded computing through a natural end-to-end mean-squared error loss that directly measures the discrepancy between the desired computations and their recovered estimates. By deriving suitable upper bounds and restricting the encoder and decoder to a reproducing kernel Hilbert space (RKHS) with mild smoothness constraints, we show that both the encoder and decoder admit specific representations as linear combinations of RKHS kernel functions. This representation allows the corresponding coefficients to be computed efficiently. Moreover, this framework enables us to establish theoretical performance guarantees for GCC under two complementary straggler regimes. In the worst-case setting with $N$ worker nodes, and at most $S$ stragglers, we show that the end-to-end loss decays at least at rate $O(S^3N^{-3})$ for standard configurations. We then study a probabilistic setting in which each worker independently straggles with probability $p$. We prove that the expected loss can still converge at rate $O(\log_{1/p}^3(N)N^{-3})$.

Related papers

• Search as Computation Allocation [52.080489413778]
  Many algorithms spend an internal resource before returning a decision and are evaluated only by the quality of that terminal output.<n>We formalize such procedures as terminal computation-allocation problems.<n>Bellman equations characterize optimal allocation under fixed budgets, priced computation, and exact certification.
  arXiv  Detail & Related papers  (2026-07-30T08:45:14Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Riemannian Optimization in Modular Systems [0.006486143522483092]
  The backpropagation algorithm is instrumental in the success of neural networks.<n>Despite its empirical success, a strong theoretical understanding of it is lacking.<n>We develop a framework of composable Riemannian modules'' whose convergence properties can be quantified.
  arXiv  Detail & Related papers  (2026-03-04T00:47:29Z)
• General Coded Computing: Adversarial Settings [15.839621757142597]
  This paper lays the foundation for general coded computing, which extends the applicability of coded computing to handle a wide class of computations.<n>We show that within a general framework, the proposed scheme achieves optimal adversarial robustness, in terms of maximum number of adversarial servers it can tolerate.
  arXiv  Detail & Related papers  (2025-02-12T01:50:12Z)
• General Coded Computing in a Probabilistic Straggler Regime [15.960546024967327]
  Recently, new coded computing schemes for general computing functions, where exact computation is replaced with approximate computation, have emerged.<n>This paper addresses the practically important scenario in the context of general coded computing, where each server may become a straggler with a probability $p$, independently from others.<n>We show that the average approximation error for two existing general coded computing schemes converges to zero with the rate of at least $mathcalO(log3_frac1p(N)cdotN-3)$.
  arXiv  Detail & Related papers  (2025-02-02T03:24:05Z)
• Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework [15.703073293718953]
  We propose a novel foundation for coded computing, integrating the principles of learning theory, and developing a framework that seamlessly adapts with machine learning applications. We show that in the proposed solution, the mean squared error of the estimation decays with the rate of $mathcalO(S3 N-3)$ and $mathcalO(Sfrac85Nfrac-35)$ in noiseless and noisy computation settings.
  arXiv  Detail & Related papers  (2024-06-01T05:01:25Z)
• 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)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  An ideal set of kernels should: admit a linear parameterization (for tractability); dense in the set of all kernels (for accuracy) Previous algorithms for optimization of kernels were limited to classification and relied on computationally complex Semidefinite Programming (SDP) algorithms. We propose a SVD-QCQPQP algorithm which dramatically reduces the computational complexity as compared with previous SDP-based approaches.
  arXiv  Detail & Related papers  (2023-04-15T04:57:37Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• Random Alloy Codes and the Fundamental Limits of Coded Distributed Tensors [1.8130068086063333]
  Stragglers and other failures can severely impact the overall completion time. Recent works in coded computing provide a novel strategy to mitigate stragglers with coded tasks. We show that this strict definition does not directly optimize the probability of failure.
  arXiv  Detail & Related papers  (2022-02-07T19:20:00Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing [34.69732430310801]
  We propose Berrut Approximated Coded Computing (BACC) as an alternative approach to deal with stragglers effect. BACC is proven to be numerically stable with low computational complexity. In particular, BACC is used to train a deep neural network on a cluster of servers.
  arXiv  Detail & Related papers  (2020-09-17T14:23:38Z)
• Predictive Coding Approximates Backprop along Arbitrary Computation Graphs [68.8204255655161]
  We develop a strategy to translate core machine learning architectures into their predictive coding equivalents. Our models perform equivalently to backprop on challenging machine learning benchmarks. Our method raises the potential that standard machine learning algorithms could in principle be directly implemented in neural circuitry.
  arXiv  Detail & Related papers  (2020-06-07T15:35:47Z)

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.