Research map / Learning theory and algorithms / Prediction and decision losses
Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LeTCC, a learning-theoretic coded computing framework that fits smoothing-spline encoder/decoder regressions (second-order Sobolev RKHS) to tolerate stragglers, deriving O(S^3 N^-3) and O(S^{8/5} N^{-3/5}) error rates and beating Berrut coded computing (BACC) on LeNet5, RepVGG, and ViT.
Problem
Coded computing for distributed ML inference relies on algebraic coding theory, which restricts computation functions to polynomials, is unstable for real-valued data, and has recovery thresholds; the paper seeks a learning-theoretic foundation for straggler-resilient coded computation of general (n
Approach
Bounds the end-to-end MSE by a decoder generalization term plus an encoder training-error term, then uses smoothing splines (kernel ridge regression in second-order Sobolev RKHS) for both encoder and decoder, deriving optimal forms and convergence rates for noiseless and noisy computation.
Key results
- LeTCC lowers RMSE vs BACC by about 15% (LeNet5), 17% (RepVGG), and 9% (ViT) on average.
- Theoretical end-to-end MSE rates are O(S^3 N^-3) in noiseless and O(S^{8/5} N^{-3/5}) in noisy computation, faster than BACC.
- Relative accuracy improves by about 2%, 5%, and 4% for LeNet5, RepVGG, and ViT respectively.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace BACC with LeTCC | LeNet5 inference · LeNet5 inference | RMSE: 2.55± 0.43 -> 2.18± 0.51 | Helped |
| Replace BACC with LeTCC | LeNet5 inference · LeNet5 inference | RelAcc: 0.92± 0.04 -> 0.94± 0.04 | Helped |
| Replace BACC with LeTCC | RepVGG inference · RepVGG inference | RMSE: 2.44± 0.38 -> 2.04± 0.42 | Helped |
| Replace BACC with LeTCC | RepVGG inference · RepVGG inference | RelAcc: 0.83± 0.05 -> 0.87± 0.05 | Helped |
| Replace BACC with LeTCC | ViT inference · ViT inference | RMSE: 0.68± 0.13 -> 0.62± 0.11 | Helped |
| Replace BACC with LeTCC | ViT inference · ViT inference | RelAcc: 0.90± 0.07 -> 0.94± 0.06 | Helped |
| Vary the smoothing parameter (ablation) | LeTCC · Inference tasks across model architectures | performance | No clear effect |
Limitations
- Analysis restricted to one-dimensional functions and inputs in the main text; extension to vector outputs is deferred to appendix.
- Focuses only on straggler mitigation; Byzantine robustness and privacy left to future work.
- Evaluation limited to three pretrained networks with a single BACC baseline in the main text.
Experimental setup
Datasets: MNIST CIFAR-10 ImageNet-1K
Benchmarks: MNIST CIFAR-10 ImageNet-1K
Metrics: RMSE relative accuracy
Baselines: BACC Lagrange coded computing
Builds on: Berrut approximate coded computing (BACC) Lagrange coded computing smoothing splines kernel ridge regression
Closest papers by meaning
- Coded Distributed Computing for Inverse Problems (NeurIPS 2017 · similarity 0.87)
- Leveraging partial stragglers within gradient coding (NeurIPS 2024 · similarity 0.87)
- Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers (NeurIPS 2025 · similarity 0.87)
- Flag Aggregator: Scalable Distributed Training under Failures and Augmented Losses using Convex Optimization (ICLR 2024 · similarity 0.85)
- Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity (AAAI 2025 · similarity 0.85)
- Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.