CS Paper Radar

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

Parsa Moradi, Behrooz Tahmasebi, Mohammad Ali Maddah-Ali

cs.LG ·submitted 2026-08-28 22:18 UTC · v1
theory

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

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG cs.DC ·2026-10-20 ·Parsa Moradi, Hanzaleh Akbarinodehi, Mohammad Ali Maddah-Ali
theory similarity 0.79
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.

0.10

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

cs.LG cs.IT ·2026-09-01 ·Parsa Moradi, Mohammad Ali Maddah-Ali
similarity 0.63
Abstract · 5 pages, 4 figures

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.

0.25

Multiple-Function Approximated Coded Computing: Constructions and Error Bounds

cs.IT ·2026-10-12 ·Rimpi Borah, Wilton Kim, J. Harshan, Stanislav Kruglik, Han Mao Kiah
similarity 0.62
Abstract · 11 pages in two-column format. This updated version contains proofs of Theorem 1, Theorem 2 and Lemma 1 in Appendix

Coded computing mitigates stragglers in distributed computation. While Lagrange coded computing (LCC) enables exact polynomial computation over finite fields, Berrut approximated coded computing (BACC) enables approximate computation of arbitrary, including non-polynomial, functions in the analog domain. In applications such as multi-task learning and inference, multiple functions must be evaluated over different subsets of a common dataset, making single-round computation desirable to reduce communication overhead. An existing LCC approach addresses this requirement but is restricted to polynomial functions over finite fields, leaving single-round multi-function computation in the analog domain an open problem. In this work, we develop a single-round construction for computing multiple arbitrary functions using BACC. We first extend the existing multi-function computation approach in LCC to the BACC setting and derive an approximation-error bound. Building on this, we propose a construction based on Berrut basis functions for computing multiple arbitrary functions and derive its approximation-error bound. We analyze the scaling of both bounds with the number of functions and the number of data points per function, and numerically compare the two constructions over a wide range of arbitrary functions. The results demonstrate that the proposed construction achieves lower relative errors than the existing approach in the tested settings.

0.27

Binary Sparse Codes: Where are we on Energy Efficient Representations?

cs.LG ·2026-10-30 ·Jose Miguel Ramos, Luis SaCouto, Andreas Wichert
similarity 0.58
Abstract · 38 pages, 8 figures

Biological neural systems achieve impressive computational capabilities under tight metabolic constraints, relying on sparse cortical representations that minimise total neural activity. This combination of efficiency and representational power has motivated growing interest in sparse coding as a computational strategy for artificial systems. Artificial models designed to produce binary sparse codes span three broad paradigms, theoretical methods grounded in efficient coding, deep learning methods trained via backpropagation, and biologically plausible methods that learn through local Hebbian rules, each yielding codes whose quality depends not only on achieving low activation density but also on preserving the informational structure of the input. The latter property, however, lacks an agreed-upon quantitative definition, leaving the field without a principled basis for comparing methods. We propose a set of metrics that formalise information preservation as similarity preservation, measuring how faithfully a binary sparse code reproduces the relational geometry of the input space, and apply this framework to compare four representative methods under matched conditions. The results reveal a consistent trade-off in which models that achieve high information preservation do so at the cost of sparsity, while models approaching the uniformity of an optimal random sparse code tend to sacrifice it. Competitive Sparse Codes, a biologically plausible approach, is the only architecture to occupy a region of near-maximal sparsity while retaining meaningful information preservation. These findings frame the simultaneous satisfaction of both factors as an open challenge for the field and provide a reusable evaluation framework for measuring progress toward it.

0.33

Error-Based Bidirectional Predictive Coding Enables Deep, 4-Bit Predictive Coding Networks

cs.LG ·2026-10-11 ·Garrett Kinman, Zeljko Zilic
similarity 0.58
Abstract

Predictive coding networks (PCNs) promise properties not offered by backpropagation-trained networks: learning from purely local information, a single network that both discriminates and generates, and flexible inference by energy minimization. However, their iterative inference is expensive, making hardware acceleration desirable, and a useful, efficient accelerator needs both depth and aggressive quantization. Canonical state-based PC delivers neither: its inference signal decays exponentially with depth, so deep models fail to train, and low precision makes it worse. We show that pairing two recent methods carries the full PCN property set into the deep, 4-bit regime: bidirectional PC (bPC), which unifies discrimination and generation, and the error-based reparameterization (ePC), which optimizes prediction errors rather than states during inference. Error optimization delivers the output signal to every layer in a single backward pass, removing the signal decay; one additional element, global-norm clipping of the error gradients, stabilizes the error dynamics at depth. The resulting ePC+bPC model trains stably up to at least eight layers and retains its full-precision accuracy and clean class-conditional generation under W4A4E4 quantization-aware training, across FP4 and three posit formats. On six-layer networks, where state-based bPC collapses to chance, ePC+bPC classifies more than 50 accuracy points above it after one epoch of training, with class-conditional generations 5-9x better in RMSE. 4-bit quantization is nearly free: full-precision and 4-bit accuracies differ by at most ~5 points, and by under two in the best-performing formats. We characterize the two failure modes the method overcomes, bounded signal decay in state-based PC and error divergence in unregularized error optimization, and discuss implications for a 4-bit-native PCN accelerator.

0.25

On the Limits of Maximal Coding Rate Reduction for Out-of-Distribution Generalisation

cs.LG ·2026-09-17 ·Menghui Zhou, Gaoshan Bi, Vitaveska Lanfranchi, Po Yang
similarity 0.57
Abstract · 31 pages, 8 figures, including appendices

Substantial efforts have been devoted to making deep learning objectives, representations, and architectures interpretable, with the goal of improving the safety, robustness, and generalisation of learning systems in diverse real-world applications. The recently proposed maximal coding rate reduction ($\mathrm{MCR}^{2}$) offers a promising information-theoretic framework for learning structured, discriminative representations of class-wise submanifolds and has inspired interpretable white-box architectures. However, we observe that $\mathrm{MCR}^{2}$ can completely fail under distribution shift, motivating our study of its out-of-distribution (OOD) generalisation limits. We establish two limitations of $\mathrm{MCR}^{2}$ for OOD generalisation. First, the $\mathrm{MCR}^{2}$ objective alone can admit complete prediction failure: a representation based entirely on unstable environmental features can achieve the global coding optimum yet fail completely after correlation reversal, despite an available perfectly stable feature. This exact-optimum example includes test inputs that cannot occur during training. Even when every possible test input can also occur during training, coding quality can be arbitrarily close to optimal while prediction error is arbitrarily close to 100%. Second, directly incorporating the invariance principle underlying widely successful invariant risk minimisation (IRM) and risk extrapolation (REx) does not eliminate this failure. The failing representation admits the same optimal coding operator across training environments, showing that shared coding optimality does not ensure stable prediction. Reliable OOD guarantees for $\mathrm{MCR}^{2}$ therefore require additional new assumptions or learning principles that establish stable predictive relationships across environments.

0.22

Resolution-Independent Analysis of Encoder--Decoder Operator Learning via Limiting Kernels

cs.LG stat.MLmath.FAmath.NA ·2026-09-12 ·Lei Shi, Jia-Qi Yang, Ding-Xuan Zhou
similarity 0.57
Abstract · 69 pages

Operator learning is formulated on function spaces, but training data are typically available only through finite-dimensional representations. In encoder--decoder architectures, a matrix-valued kernel on the encoded space induces an operator-valued kernel on the original function spaces, and the corresponding reproducing kernel Hilbert spaces are isometrically isomorphic. As the input and output resolutions increase, the induced kernels converge to a limiting kernel, in the sense of operator-norm convergence of their associated integral operators, allowing regularity assumptions to be stated independently of the encoding resolution. For regularized stochastic gradient descent, we establish upper bounds for decreasing and fixed step sizes, separating the encoding and regularization terms from optimization terms of order \(t^{-θ}\) and \(T^{-θ'}\), respectively, for any \(θ,θ'\in(0,1)\). We further prove lower bounds showing that these encoding-induced terms are generally unavoidable. The analysis is further extended to encoder--decoder neural networks through the limiting neural tangent kernel (NTK), yielding error bounds with an additional finite-width term and polynomial parameter and sample complexity guarantees when the encoding errors decay algebraically. The framework covers matrix-valued kernels constructed from radial and dot product kernels, NTKs arising from wide encoder--decoder neural networks, and encoder--decoder pairs based on Fourier, Legendre polynomial, wavelet, PCA, or pointwise sampling representations.

0.30

Sample-efficient learning with Dense Associative Memories

cs.LG ·2026-10-19 ·Andrew Lucas, Dmitry Krotov
similarity 0.57
Abstract

We analytically study the evolution of the energy function of Dense Associative Memories (DenseAMs) as they train on randomly sampled codewords of random expander low-density parity-check codes (a.k.a. solutions of random XORSAT problems). We identify two distinct regimes and a transition between them, reminiscent of grokking in neural networks. A regime of small training set size is where the model memorizes a few training examples but cannot discover the underlying rules of the entire codeword dictionary generative process. The opposite regime, corresponding to a larger training set size, is where the model has uncovered the sparse constraints that generated the entire data set after seeing only polynomially many patterns. We also design a novel class of DenseAMs with a thresholding learning rule, and show that any amount of thresholding enables the model to perform simplified sparse Hamiltonian learning, which exponentially reduces the number of training examples needed to learn the true underlying data set. In this regime, the model learns how to discover $\exp[\mathrm{O}(n)]$ solutions from only $\mathrm{O}(\log n)$ training samples, which is asymptotically optimal for any learning algorithm. When training on codewords of certain random codes, the model can even learn the underlying code when a small O(1) fraction of bits are latent variables. These latent variables are not shown to the model during learning, but will be discovered by sparsifying observed higher-order correlations. For certain random codes, we show that a simple and conservative algorithm learns a minimal latent representation for the data set. This provides a transparent, physics-motivated, and analytically tractable toy model for how deep latent representations emerge in an associative memory training.

0.25