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

Parsa Moradi; Hanzaleh Akbarinodehi; Mohammad Ali Maddah-Ali

cs.LGOct 20, 2026

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

Authors: Parsa Moradi, Hanzaleh Akbarinodehi, Mohammad Ali Maddah-Ali

Organizations: University of Minnesota, Twin Cities, Minneapolis, MN, USA.

Abstract

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\geq 1$ adversarial workers among $N$ workers results in a worst-case error of order $\mathcal{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.

Figures & tables

u_{\textrm{enc}}^{\dagger}=\operatorname*{arg\,min}_{u\in\mathcal{H}^{2}\left(\Omega;\mathbb{R}^{d}\right)}\left\{\frac{1}{K}\sum_{k=1}^{K}\lVert u(\alpha_{k})-\mathbf{x}_{k}\rVert_{2}^{2}+\lambda_{\textrm{e}}\lVert u^{\prime\prime}\rVert_{{L}^{2}\left(\Omega;\mathbb{R}^{d}\right)}^{2}\right\},

Algorithm 1 General Coded Computing in the Adversarial Setting

Panel of Figure 2 — Fig. 2 : Approximation error as a function of the number of workers for adversarial budgets $q=\lfloor N^{\theta}\rfloor$ . The light solid curves show the empirical errors, the dark solid lines show the fitted empirical slopes, and the dashed lines show the convergence-rate predictions from Corollary 2 .

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 3

Hanzaleh Akbarinodehi 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 2018, respectively. His research interests include information theory and coding, blockchain technology, game theory, and decentralized systems.

Table 4

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.

Table 5

Adversarial Robustness

Adversarial robustness studies how well AI systems withstand deliberately crafted inputs, training-data corruption, and other attacks.

See all 481 papers

Aug 28, 2026

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

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})

Parsa Moradi, Behrooz Tahmasebi, Mohammad Ali Maddah-Ali

University of Minnesota, Twin Cities · Harvard University

Topic pending

Ask PDF

Sep 1, 2026

Manifold-Aware General Coded Computing for Straggler-Resilient Distributed Computing

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

Distributed Inference

Ask PDF

Jul 2, 2026

Privacy-Preserving and Verifiable Approximate Distributed Coded Computing

Distributed machine learning enables collaborative model training without centralizing data, but it also exposes learning processes to privacy leakage and malicious manipulation. Existing defenses typically address these threats in isolation and are often tailored to specific learning paradigms or model architectures, limiting their applicability in realistic deployments. In particular, federated learning and decentralized learning exhibit distinct adversarial surfaces that are rarely addressed within a unified framework. In this paper, we present a model-agnostic framework for adversary-resistant distributed learning that jointly addresses privacy preservation and malicious behavior across both federated and decentralized settings. Our approach combines paradigm-specific defense mechanisms with GPBACC, a privacy-enhancing coded computing technique applicable to arbitrary machine learning models. For federated learning, we integrate robust aggregation strategies to mitigate the impact of malicious participants, while for decentralized learning we employ approximate decode-and-compare and group testing techniques to enable lightweight verification and adversary isolation without relying on a trusted aggregator. Crucially, we evaluate the proposed framework through an explicit, attack-driven analysis. We implement representative privacy attacks and malicious behaviors, and empirically demonstrate that the combination of GPBACC with robust aggregation and verification mechanisms significantly reduces privacy leakage and improves resilience against active adversaries. These results suggest that privacy-enhancing coded computing, when combined with appropriate adversary-resistance strategies, provides a practical and deployable foundation for secure distributed machine learning.

Xavier Martínez-Luaña, Alba Gude-Santos, Manuel Fernández-Veiga +1

Galician Research and Development Center in Advanced Telecommunications (GRADIANT) Estrada do Vilar, 56-58, Vigo, 36214, Spain · atlanTTic, Information & Computing Lab (ICLAB), Telecommunication Engineering School, Universidade de Vigo Vigo, 36310, Spain

Byzantine-Robust Federated Learning Decentralized Learning Privacy-Preserving ML

Ask PDF

Abstract

Adversarial Robustness

Explore similar work

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

Manifold-Aware General Coded Computing for Straggler-Resilient Distributed Computing

Privacy-Preserving and Verifiable Approximate Distributed Coded Computing