PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Parsa Moradi, Behrooz Tahmasebi, Mohammad Ali Maddah-Ali

arXiv:2608.28910v1cs.LG

TL;DR

Existing coded computing is optimized for exact recovery of structured computations, limiting its direct fit to general and approximate workloads. GCC addresses this gap with an end-to-end loss and RKHS-based encoder and decoder designs, establishing convergence guarantees in worst-case and probabilistic straggler settings.

  • Problem

    Classical coded computing focuses on algebraically structured tasks and strict exact-recovery thresholds, whereas general workloads such as DNNs may require approximate recovery.

  • Method

    GCC formulates coded computing as end-to-end loss minimization and restricts encoder and decoder functions to a second-order Sobolev RKHS with tractable upper bounds.

  • Results

    GCC establishes function-recovery and convergence guarantees under both worst-case and probabilistic straggler regimes.

  • Takeaways & Limitations

    The framework supports resilient execution of complex nonlinear workloads, including deep neural networks, beyond rigid algebraic coded-computing schemes.

  • Takeaways & Limitations

    The encoder and decoder designs rely on membership in a second-order Sobolev space; alternative smoothness assumptions remain a future extension.

Abstract

from arXiv · show

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

I. INTRODUCTION

Classical coded computing mitigates stragglers but is tailored to structured computations and exact recovery thresholds. GCC instead formulates general coded computing as end-to-end approximation and provides learning-theoretic designs and guarantees.

  • Stragglers can bottleneck naive distributed computation because workers may be delayed or fail to return results by the deadline.
  • Classical coded-computing schemes target algebraic tasks and may fail entirely when non-stragglers fall below a strict recovery threshold.
  • GCC introduces an explicit end-to-end loss for approximating target function values from outputs returned by a subset of workers.
  • GCC restricts encoder and decoder functions to a second-order Sobolev RKHS and derives tractable upper bounds for their design.
  • GCC is evaluated on structured functions and complex DNNs, with experiments reporting lower reconstruction error and faster convergence than existing coded-computing schemes.

IV. WORST-CASE STRAGGLER SETTING

The worst-case design handles any non-straggler set with at least N−S workers by replacing an infinite-dimensional joint optimization with a tractable decomposed upper bound.

  • At most S of N worker nodes may straggle, and the encoder and decoder are optimized for the resulting non-straggler set F.
  • The design replaces the intractable joint optimization over infinite-dimensional function spaces with a structured upper bound.
  • The upper bound separates decoder approximation error from encoder approximation error.
  • Decoder error measures reconstruction of the target computation from returned worker outputs, whereas encoder error measures failure to reproduce the original inputs.
  • The two error terms remain coupled because both depend on the encoder, including the decoder’s reconstruction of the composite function f ◦ u_enc.
  • A nested optimization first minimizes decoder error for a fixed encoder, then minimizes the resulting upper-bound objective over the encoder.

1) Decoder Design:

GCC constructs the decoder from returned worker outputs using a regularized cubic smoothing-spline objective, then evaluates it at the encoder design points to estimate the target computations. The decoder has a finite-dimensional kernel representation and supports worst-case error bounds under smoothness assumptions.

  • GCC Scheme: The decoder is evaluated at encoder design points to produce estimates of the original function values.This evaluation targets the points associated with the input batch rather than only the worker design points.
  • Decoder objective: The decoder minimizes empirical MSE on available worker outputs while penalizing the L2 norm of its second derivative.This regularization balances fidelity to returned outputs with smoothness.
  • Decoder construction: A cubic smoothing spline reconstructs the decoder from the available pairs of decoder design points and worker outputs.For positive smoothing, the solution is piecewise cubic with continuous first and second derivatives.
  • Decoder construction: The decoder optimization separates across output dimensions, yielding one scalar smoothing-spline problem for each component.Each component uses the scalar responses f_j(u_enc(β_v)) from the non-straggling workers.
  • RKHS representation: A finite-dimensional RKHS representation expresses each decoder component using kernel functions centered at returned worker points and the null space span{1, t}.The vector-valued representation includes linear coefficients and coefficient vectors associated with returned outputs.
  • Theoretical guarantee: Under twice-differentiability and uniform gradient and Hessian bounds, the decoder admits a non-asymptotic worst-case upper bound.The bound applies to every non-straggler set with at least N−S workers and uses ψ(t)=t+4t^2.

3) GCC Scheme:

The practical GCC scheme combines smoothing-spline encoder and decoder constructions whose coefficients are efficiently computable. Its master-side overhead is linear in the principal dimensions and scales linearly with workers and data points.

  • GCC Scheme: GCC uses representer-theorem structure for its encoder and decoder, enabling efficient computation of their coefficients.The resulting optimization problems have special spline structure summarized by the algorithm.
  • GCC Scheme: The master constructs a coded-input encoder, sends encoded points to workers, fits a decoder from returned outputs, and evaluates it at target points.The encoder and decoder are prescribed functional forms rather than products of iterative training.
  • Decoder Complexity: O((K + N)d) is the total efficient encoding overhead, becoming O(Nd) when N ≥K.The efficient encoder is constructed in O(Kd) operations and evaluated at N decoder points in O(Nd) operations.
  • Decoder Complexity: O((K + N)d) + O((|F| + K)m) is GCC’s overall master-side complexity with the efficient encoder.The first term covers encoding and the second covers decoding.
  • Decoder Complexity: GCC scales linearly with input dimension d, output dimension m, worker count, and input-data-point count.This summarizes the dependence of the efficient master-side implementation.

3) Comparison with existing schemes:

GCC is compared with existing coded-computing schemes through master-side complexity and asymptotic straggler-loss analyses. The framework provides smooth approximation behavior in both worst-case and probabilistic straggler settings.

  • Comparison with existing schemes: GCC has lower encoding and decoding overhead than Lagrange Coded Computing and Berrut Approximation Coded Computing.LCC has super-linear dependence on input points and workers, while BACC uses direct costs O(NKd) and O(K|F|·m).
  • C. Asymptotic Analysis: O(S^3N^-3) is the worst-case end-to-end loss rate for standard equidistant and Chebyshev design points.For these configurations, γ2=1 and the loss converges to zero whenever S=o(N).
  • C. Asymptotic Analysis: GCC produces an approximation from any valid non-straggler set, with error degrading smoothly as the number of stragglers increases.This contrasts with exact schemes that may fail below a recovery threshold.
  • Probabilistic straggler setting: In the probabilistic setting, the loss criterion averages over independently generated non-straggler sets rather than maximizing over sets within a deterministic straggler budget.The encoder and decoder are designed as in the worst-case setting after the realized set is known.
  • Probabilistic straggler setting: The probabilistic decoder bound depends on RF+1, where RF is the longest consecutive run of stragglers in the realized failure pattern.This replaces the deterministic factor S+1 used in the worst-case analysis.

2) Encoder Design:

The probabilistic straggler analysis selects the encoder by minimizing a surrogate upper bound and preserves the same efficient spline-based design used in the worst-case setting. Its expected loss converges for fixed failure probability because independent straggler patterns are governed by logarithmic longest runs rather than the total number of stragglers.

  • Probabilistic encoder design: The expected loss is upper-bounded through a probabilistic factor Γp,N derived by combining the preceding bounds.
  • Probabilistic encoder design: The encoder is chosen as a minimizer of the surrogate upper bound, and any minimizer has a finite-dimensional representer-theorem representation.
  • Efficient encoder design: The efficient probabilistic encoder replaces the nonlinear regularizer with a quadratic smoothing-spline surrogate and is computed by the same linear-system method as in the worst-case setting.
  • Computational overhead: The probabilistic setting leaves master-side computations unchanged for a realized non-straggler set, with overhead O((K + N)d) + O((|F| + K)m).
  • Computational overhead: Because E[|F|] = (1−p)N = O(N), expected master-side overhead is O((K + N)d) + O((N + K)m), preserving linear scaling.
  • Probabilistic convergence: The probabilistic result is explained by the longest consecutive straggler run growing logarithmically with N, while worst-case-dominating patterns occur rarely under independent failures.
  • Probabilistic convergence: For fixed p ∈(0, 1), the expected loss converges to zero, with standard design points yielding a logarithmic-factor convergence rate.

B. Proof of Theorem 3

The proof of Theorem 3 controls the encoder's Sobolev norm and uses loss bounds to justify an efficient smoothing-spline surrogate for encoder optimization.

  • Encoder norm control: The encoder minimizer remains in a fixed Sobolev ball uniformly over the smoothing parameter.
  • Encoder norm control: The loss decomposition and prior bounds produce an upper bound involving ΓS,N and ψ(·) for every admissible encoder.
  • Efficient surrogate: Setting m1 := 1 and m2 := 4 yields the surrogate regularization form used in the efficient encoder design.
  • Efficient surrogate: The resulting comparison bounds the worst-case encoder objective by the performance of a suitable reference encoder.

C. Proof of Theorem 4

The proof of Theorem 4 transfers smoothing-spline and encoder approximation bounds to the worst-case straggler geometry, where missing workers enlarge the largest node gap.

  • Encoder comparison: The encoder objective is bounded using a natural cubic spline interpolant that matches the fixed input data at the encoder design points.
  • Convergence conclusion: For S = o(N^γ2), the same convergence rate follows after combining the competing encoder constructions and taking the infimum over admissible encoders.
  • Worst-case geometry: The decoder design points are controlled by the largest consecutive straggler run, which is at most S + 1 in the worst-case setting.

F. Proof of Theorem 6

Theorem 6 proves the probabilistic bound by replacing worst-case straggler counts with the longest consecutive straggler run and controlling its moments under independent failures.

  • Non-asymptotic bound: The proof begins from the non-asymptotic bound and controls the random factor involving (RF + 1)^4.
  • Run-length reduction: For a realized non-straggler set, RF is the maximum number of consecutive stragglers, and the proof replaces the worst-case S + 1 geometry by RF.
  • Run-length moments: The longest-run estimate for an independent Bernoulli straggler sequence provides the required moment control for RF.
  • Efficient encoder: The efficient probabilistic encoder uses λe = Γp,N(m1 + m2Re), with Re, m1, and m2 independent of N.
  • Conclusion: The proof concludes by substituting the run-length expectation bound into the probabilistic loss bound, establishing Corollary 2.

VII. EXPERIMENTAL RESULTS

GCC is evaluated on DNN and polynomial workloads against BACC and LCC, with experiments examining reconstruction accuracy, classification performance, straggler robustness, and convergence. Across these evaluations, GCC supports accurate approximation under broader straggler conditions and exhibits convergence behavior consistent with the theoretical bounds.

  • Experimental Setup: GCC is evaluated on LeNet-5, ViT-B/16, and high-dimensional multivariate polynomial tasks using MSE and Relative Accuracy.LeNet-5 has approximately 6×10^4 parameters, while ViT-B/16 has approximately 80 million parameters; Relative Accuracy compares approximated and exact model prediction accuracy.
  • DNN Performance under Stragglers: GCC with tuned parameters and its natural-spline variant achieve lower MSE and higher RelAcc than BACC across nearly all straggler configurations.The comparison uses varying numbers of stragglers in LeNet-5 and ViT-B/16 experiments, with results averaged over independently sampled straggler realizations and input batches.
  • DNN Performance under Stragglers: Tuned smoothing parameters provide a clear advantage over the interpolating GCC variant in high-straggler regimes.The two GCC variants perform similarly when the number of stragglers is relatively small.
  • Polynomial Computation: When non-stragglers meet the threshold deg(f)(K −1) + 1 = 13, LCC achieves zero reconstruction error, while GCC incurs approximation error of order O(10^-3).This occurs for the evaluated polynomial task when S ≤7.
  • Polynomial Computation: Below LCC’s recovery threshold, GCC continues to provide accurate polynomial approximations while LCC’s reconstruction error increases sharply.The experiment contrasts GCC’s approximation behavior with LCC’s loss of its exact-recovery guarantee when too few workers remain available.
  • Asymptotic Convergence: GCC’s empirical MSE decay is consistent with O(N^-3) in the worst-case configuration and with O(log_{1/p}^3(N)N^-3) under probabilistic failures.With fixed S = 5, probabilistic-setting error increases with p but continues to decrease as N grows; GCC also decreases more rapidly with N than BACC.

APPENDIX A DEFINITIONS

This appendix defines weak derivatives, Lp and Sobolev spaces, and interpolation inequalities used to control function norms. It establishes that the relevant W2,2 setting supports the inequalities needed later.

  • Definitions: Weak derivatives are defined through integrals against smooth test functions and coincide with classical derivatives when those exist.Higher-order weak derivatives are defined recursively, including component-wise for vector-valued functions.
  • Definitions: Lp spaces contain measurable vector-valued functions with finite component-wise p-norms, while local Lp membership requires this property on every compact subset.
  • Interpolation inequalities: The Gagliardo-Nirenberg interpolation inequality bounds an Lr norm using an Lq norm and derivative Lp norm under stated exponent conditions.The appendix specializes the result to obtain a supremum-norm bound from L2 norms.
  • Application to W2,2: The interpolation results apply to the encoded functions because W2,2 functions and their derivatives satisfy the required integrability properties.The appendix shows that W2,2 functions belong locally to W1,1, enabling the interpolation inequalities in the proposed setting.

A. Sobolev Equivalent Norms

This section develops equivalent Sobolev norms and RKHS representations used for smoothing-spline construction. It also verifies the smoothness of compositions involving the encoder.

  • Equivalent norms: Equivalent Sobolev norms can replace the standard norm when positive constants bound each norm above and below.The paper selects a specific equivalent norm for its analysis.
  • RKHS structure: The selected Sobolev spaces are reproducing kernel Hilbert spaces, enabling kernel-based finite-dimensional representations.
  • Smoothing splines: The smoothing-spline solution is linear in the observed data and can be represented using natural-spline basis functions associated with the design knots.The kernel decomposes into a penalty-null-space polynomial component and a complementary reproducing-kernel component.
  • Composition smoothness: The encoder composition belongs to H2 when its function and first two weak derivatives have bounded L2 norms.The proof uses Lipschitz and derivative bounds together with one-dimensional Sobolev embedding.

B. Proof of Lemma 2

This section proves properties of the decoder error and derives spline-based representations and norm bounds for the encoder optimization.

  • Decoder error: The decoder error function has at least one zero on the domain when at least one non-straggling worker is available.For positive smoothing, a constant shift would otherwise reduce the objective; the zero-smoothing case follows from interpolation.
  • Decoder error: The decoder error satisfies the stated norm bound by combining the zero property with the interpolation inequality.
  • Encoder representation: The encoder minimizer may be chosen in the natural cubic-spline space because interpolation preserves the fitting term and does not increase the second-derivative penalty.
  • Encoder representation: The resulting coordinate-wise optimization is quadratic, yielding linear equations whose matrix is controlled by positive-semidefinite spline terms.The proof then translates bounds at design points into Sobolev-norm bounds.

F. Proof of Lemma 6

This proof bounds the fourth moment of the longest run of non-stragglers using a tail decomposition. The resulting moment grows polylogarithmically with the worker count.

  • Moment decomposition: The longest-run variable is analyzed through its survival function, splitting the fourth-moment sum into core and tail components.The split point is chosen as m = floor(µ) + 2 so the tail probability bound applies with a positive deviation.
  • Tail bound: The tail probability decays geometrically as Pr(X >= m + t) < C3p^t for t >= 1.This follows by centering the longest-run variable at its expectation and applying the upper-tail bound.
  • Tail summation: The fourth-power increment expands into a cubic polynomial in the split point and tail index, producing convergent arithmetico-geometric series.
  • Asymptotic bound: E[(X + 1)^4] = O(log_1/p((1 − p)N)^4) for sufficiently large N.The result uses the logarithmic upper bound on the expected longest run and absorbs the residual asymptotic term into a constant.
Loading 2608.28910v1…