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(S3N−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(log1/p3(N)N−3).
Figures & tables
Fig. 1 : System model for coded computing with N worker nodes and K input tasks, where some nodes act as stragglers.
Fig. 2 : Performance comparison of GCC , natural spline interpolating GCC ( λe=λd=0 ), and BACC across varying numbers of stragglers ( S ). The top row displays results for the ViT architecture, while the bottom row shows results for LeNet5. Shaded regions denote the 95% confidence intervals.
Fig. 3 : Comparison of Mean Squared Error (MSE) between GCC and LCC for a polynomial task. (a) A zoomed-in view showing LCC ’s exact recovery prior to exceeding the recovery threshold. (b) The full evaluation showing LCC ’s instability beyond the threshold, contrasted with GCC ’s robustness.
Fig. 4 : Empirical validation of the asymptotic convergence rates as the number of worker nodes N increases. (a) Comparison of the MSE decay between BACC and GCC in a worst-case straggler environment. (b) The MSE decay for GCC under various probabilistic worker failure rates alongside a worst-case straggler setting, validating the theoretical upper bound of O(N−3log1/pN) .
Parsa Moradi is a Ph.D. candidate in the Department of Electrical and Computer Engineering at the University of Minnesota Twin Cities. He received his B.Sc. and M.Sc. degrees from the Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran, in 2016 and 2019, respectively. His research interests include deep learning, generative AI, distributed machine learning, and AI for healthcare.
Table 6
Behrooz Tahmasebi is a Postdoctoral Fellow in Applied Mathematics and Computer Science at Harvard University, working in the Geometric Machine Learning Laboratory. He received his Ph.D. in Electrical Engineering and Computer Science (EECS) from the Massachusetts Institute of Technology (MIT), where he conducted research at the Computer Science and Artificial Intelligence Laboratory (CSAIL) under the supervision of Prof. Stefanie Jegelka. His research focuses on geometric deep learning, symmetries, and invariances in machine learning. He received a Best Paper Award at the HiLD Workshop at ICML 2024 and co-presented a NeurIPS 2025 tutorial on geometric machine learning.
Table 7
Mohammad Ali Maddah-Ali (IEEE Fellow, 2023) is an Associate Professor at the University of Minnesota Twin Cities. He received his B.Sc. degree in Electrical Engineering from Isfahan University of Technology, his M.A.Sc. degree from the University of Tehran, and his Ph.D. in Electrical and Computer Engineering from the University of Waterloo, Canada, in 2007. From 2007 to 2008, he was with the Wireless Technology Laboratories at Nortel Networks, Ottawa, ON, Canada. He then held a Postdoctoral Fellowship at the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, from 2008 to 2010. From September 2010 to September 2020, he served as a Communication Research Scientist at Nokia Bell Labs, NJ, USA. Dr. Maddah-Ali is the recipient of several honors, including the NSERC Postdoctoral Fellowship (2007), the Best Paper Award at the IEEE International Conference on Communications (ICC) in 2014, the IEEE Communications Society and IEEE Information Theory Society Joint Paper Award in 2015, and the IEEE Information Theory Society Paper Award in 2016. He served as an Associate Editor for the IEEE Transactions on Information Theory (2019–2022) and as Lead Editor for the IEEE Journal on Selected Areas in Information Theory. He is currently a distinguished lecturer of the IEEE Information Theory Society.
Existing coded-computing designs do not explicitly exploit the intrinsic structure of the input data. In communication systems, statistical structure and redundancy are often removed through source coding (or compression) before channel coding is applied. This principle, however, does not transfer directly to coded computation. In many computational tasks, particularly in machine learning, the structure of the data is precisely what the computation seeks to exploit to infer outputs or learn meaningful patterns. Consequently, coded-computing schemes should preserve and leverage this structure in their code design, rather than ignoring or eliminating it through source coding. This observation motivates a different perspective on code construction. In many channel-coding schemes, such as Reed-Solomon codes, coded symbols are generated by evaluating a low-dimensional algebraic representation at selected points. In contrast, many high-dimensional datasets naturally concentrate near low-dimensional manifolds. In this paper, we exploit this intrinsic geometry by designing coded samples that follow the natural manifold of the data, rather than imposing an artificial low-dimensional structure unrelated to the data distribution. Inspired by graph-based manifold learning, we propose a manifold-aware encoding strategy for general coded computing (GCC). Experiments on neural network inference and high-dimensional polynomial evaluation demonstrate that the proposed strategy consistently and significantly reduces the mean squared recovery error under straggling compared with standard GCC.
Parsa Moradi, Mohammad Ali Maddah-Ali
University of Minnesota, Twin Cities Minneapolis, MN, USA
Adversarial workers pose a severe challenge in distributed computing systems by returning corrupted outputs that can substantially distort the recovered computations. Coded computing addresses this threat by introducing redundancy across worker assignments. Existing exact and approximate coded-computing methods typically handle adversarial outputs by explicitly locating and correcting or removing erroneous evaluations, which adds significant computational overhead at the master node. Moreover, existing analyses do not characterize how the recovery error scales with the number of workers and the adversarial budget. In this paper, we develop an adversarially robust extension of general coded computing (GCC), a learning-theoretic approximate coded-computing framework that designs the encoder and decoder by minimizing an upper bound on the end-to-end recovery error. Rather than identifying corrupted workers, the proposed method uses smoothness regularization to limit the influence of their outputs. The resulting encoder and decoder can be implemented using smoothing splines with linear master-side complexity. We derive a non-asymptotic bound on the worst-case end-to-end approximation error by decomposing it into three components: (1) the encoder approximation error, (2) the decoder reconstruction error under fully honest results, and (3) the adversarial perturbation error. For maximum of q≥1 adversarial workers among N workers results in a worst-case error of order O((q/N)6/5) with appropriate selection of smoothness parameter, demonstrating that the approximation error vanishes asymptotically whenever the number of adversaries grows sublinearly with the network size. Experiments on scalar computation and neural-network inference are consistent with the predicted convergence behavior.
Parsa Moradi, Hanzaleh Akbarinodehi, Mohammad Ali Maddah-Ali
University of Minnesota, Twin Cities, Minneapolis, MN, USA.
In large-scale machine learning, distributed training commonly involves multiple workers evaluating the gradients of the model on different dataset partitions. A common challenge is the presence of straggling workers, which may significantly slow down training. Traditional gradient coding (GC) addresses this by duplicating dataset partitions across workers, allowing for the replacement of missing gradients from stragglers. However, GC requires workers to evaluate gradients on multiple dataset partitions in each step, potentially increasing overall training time. In this paper, we propose to pipeline GC, such that gradient evaluation is segmented across multiple steps and each worker evaluates gradients on just a single dataset partition per step. We develop the pipelined version for fractional repetition (FR) and cyclic repetition (CR), two representative dataset placement schemes in GC, and prove convergence guarantees for both. Through extensive simulations and experiments on cloud infrastructure, our schemes not only significantly reduce training time but also accelerate convergence compared to GC and other baselines.
Xian Su, Jun Li
Department of Computer Science · Florida International University · Miami, FL, USA +3