# Straggler Mitigation in Distributed Optimization Through Data Encoding

arXiv: https://arxiv.org/abs/1711.04969 · HTML: https://mlsanity.com/paper/1711.04969/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2017.

## Built on by (most cited first, 26 of 26)

- [CodedPaddedFL and CodedSecAgg: Straggler Mitigation and Secure Aggregation in Federated Learning](https://mlsanity.com/paper/2112.08909/) (2021)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Towards Demystifying Serverless Machine Learning Training](https://mlsanity.com/paper/2105.07806/) (2021)
- [Approximate, Adapt, Anonymize (3A): a Framework for Privacy Preserving Training Data Release for Machine Learning](https://mlsanity.com/paper/2307.01875/) (2023)
- [Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework](https://mlsanity.com/paper/2406.00300/) (2024)
- [Distributed Principal Subspace Analysis for Partitioned Big Data: Algorithms, Analysis, and Implementation](https://mlsanity.com/paper/2103.06406/) (2021)
- [Coding for Straggler Mitigation in Federated Learning](https://mlsanity.com/paper/2109.15226/) (2021)
- [General Coded Computing: Adversarial Settings](https://mlsanity.com/paper/2502.08058/) (2025)
- [Straggler-Resilient Distributed Machine Learning with Dynamic Backup Workers](https://mlsanity.com/paper/2102.06280/) (2021)
- [Straggler-Resilient Differentially-Private Decentralized Learning](https://mlsanity.com/paper/2212.03080/) (2022)
- [Straggler-Resilient Decentralized Learning via Adaptive Asynchronous Updates](https://mlsanity.com/paper/2306.06559/) (2023)
- [Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2208.03134/) (2022)
- [General Coded Computing in a Probabilistic Straggler Regime](https://mlsanity.com/paper/2502.00645/) (2025)
- [Reducing Training Time in Cross-Silo Federated Learning using Multigraph Topology](https://mlsanity.com/paper/2207.09657/) (2022)
- [Adaptive Coded Federated Learning: Privacy Preservation and Straggler Mitigation](https://mlsanity.com/paper/2403.14905/) (2024)
- [DP-CDA: An Algorithm for Enhanced Privacy Preservation in Dataset Synthesis Through Randomized Mixing](https://mlsanity.com/paper/2411.16121/) (2024)
- [Efficient AllReduce with Stragglers](https://mlsanity.com/paper/2505.23523/) (2025)
- [Near-Optimal Private Linear Regression via Iterative Hessian Mixing](https://mlsanity.com/paper/2601.07545/) (2026)
- [Distributed Optimization using Heterogeneous Compute Systems](https://mlsanity.com/paper/2110.08941/) (2021)
- [Utilizing Redundancy in Cost Functions for Resilience in Distributed Optimization and Learning](https://mlsanity.com/paper/2110.10858/) (2021)
- [Impact of Redundancy on Resilience in Distributed Optimization and Learning](https://mlsanity.com/paper/2211.08622/) (2022)
- [Randomized Kaczmarz in Adversarial Distributed Setting](https://mlsanity.com/paper/2302.14615/) (2023)
- [Fast and Straggler-Tolerant Distributed SGD with Reduced Computation Load](https://mlsanity.com/paper/2304.08589/) (2023)
- [Approximate Gradient Coding for Privacy-Flexible Federated Learning with Non-IID Data](https://mlsanity.com/paper/2404.03524/) (2024)
- [A Dynamic Weighting Strategy to Mitigate Worker Node Failure in Distributed Deep Learning](https://mlsanity.com/paper/2409.09242/) (2024)
- [Manifold-Aware General Coded Computing for Straggler-Resilient Distributed Computing](https://mlsanity.com/paper/2609.00552/) (2026)

## Abstract (arXiv)

Slow running or straggler tasks can significantly reduce computation speed in distributed computation. Recently, coding-theory-inspired approaches have been applied to mitigate the effect of straggling, through embedding redundancy in certain linear computational steps of the optimization algorithm, thus completing the computation without waiting for the stragglers. In this paper, we propose an alternate approach where we embed the redundancy directly in the data itself, and allow the computation to proceed completely oblivious to encoding. We propose several encoding schemes, and demonstrate that popular batch algorithms, such as gradient descent and L-BFGS, applied in a coding-oblivious manner, deterministically achieve sample path linear convergence to an approximate solution of the original problem, using an arbitrarily varying subset of the nodes at each iteration. Moreover, this approximation can be controlled by the amount of redundancy and the number of nodes used in each iteration. We provide experimental results demonstrating the advantage of the approach over uncoded and data replication strategies.