# Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 52 references that are in the map.
- First posted on arXiv 6 Jun 2022.

## Builds on (most cited first, 30 of 33)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [One-Bit Over-the-Air Aggregation for Communication-Efficient Federated Edge Learning: Design and Convergence Analysis](https://mlsanity.com/paper/2001.05713/) (2020)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [Learning Rate Optimization for Federated Learning Exploiting Over-the-air Computation](https://mlsanity.com/paper/2102.02946/) (2021)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [Communication-Computation Efficient Gradient Coding](https://mlsanity.com/paper/1802.03475/) (2018)
- [ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding](https://mlsanity.com/paper/1901.09671/) (2019)
- [Gradient Coding from Cyclic MDS Codes and Expander Graphs](https://mlsanity.com/paper/1707.03858/) (2017)
- [Fundamental Limits of Approximate Gradient Coding](https://mlsanity.com/paper/1901.08166/) (2019)
- [Improving Distributed Gradient Descent Using Reed-Solomon Codes](https://mlsanity.com/paper/1706.05436/) (2017)
- [Coded Federated Learning](https://mlsanity.com/paper/2002.09574/) (2020)
- [Approximate Gradient Coding via Sparse Random Graphs](https://mlsanity.com/paper/1711.06771/) (2017)
- [Gradient Coding with Clustering and Multi-message Communication](https://mlsanity.com/paper/1903.01974/) (2019)
- [Near-Optimal Straggler Mitigation for Distributed Gradient Methods](https://mlsanity.com/paper/1710.09990/) (2017)
- [A Survey of Coded Distributed Computing](https://mlsanity.com/paper/2008.09048/) (2020)
- [Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning](https://mlsanity.com/paper/2103.01206/) (2021)
- [Rateless Codes for Near-Perfect Load Balancing in Distributed Matrix-Vector Multiplication](https://mlsanity.com/paper/1804.10331/) (2018)
- [Speeding Up Distributed Gradient Descent by Utilizing Non-persistent Stragglers](https://mlsanity.com/paper/1808.02240/) (2018)
- [Gradient Coding Based on Block Designs for Mitigating Adversarial Stragglers](https://mlsanity.com/paper/1904.13373/) (2019)
- [Sample-based and Feature-based Federated Learning for Unconstrained and Constrained Nonconvex Optimization via Mini-batch SSCA](https://mlsanity.com/paper/2104.06011/) (2021)
- [An Optimization Framework for Federated Edge Learning](https://mlsanity.com/paper/2111.13526/) (2021)
- [Timely-Throughput Optimal Coded Computing over Cloud Networks](https://mlsanity.com/paper/1904.05522/) (2019)
- [Hierarchical Coded Matrix Multiplication](https://mlsanity.com/paper/1907.08818/) (2019)
- [Gradient Coding with Dynamic Clustering for Straggler Mitigation](https://mlsanity.com/paper/2011.01922/) (2020)

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

- [STSyn: Speeding Up Local SGD with Straggler-Tolerant Synchronization](https://mlsanity.com/paper/2210.03521/) (2022)

## Abstract (arXiv)

Gradient coding schemes effectively mitigate full stragglers in distributed learning by introducing identical redundancy in coded local partial derivatives corresponding to all model parameters. However, they are no longer effective for partial stragglers as they cannot utilize incomplete computation results from partial stragglers. This paper aims to design a new gradient coding scheme for mitigating partial stragglers in distributed learning. Specifically, we consider a distributed system consisting of one master and N workers, characterized by a general partial straggler model and focuses on solving a general large-scale machine learning problem with L model parameters using gradient coding. First, we propose a coordinate gradient coding scheme with L coding parameters representing L possibly different diversities for the L coordinates, which generates most gradient coding schemes. Then, we consider the minimization of the expected overall runtime and the maximization of the completion probability with respect to the L coding parameters for coordinates, which are challenging discrete optimization problems. To reduce computational complexity, we first transform each to an equivalent but much simpler discrete problem with NllL variables representing the partition of the L coordinates into N blocks, each with identical redundancy. This indicates an equivalent but more easily implemented block coordinate gradient coding scheme with N coding parameters for blocks. Then, we adopt continuous relaxation to further reduce computational complexity. For the resulting minimization of expected overall runtime, we develop an iterative algorithm of computational complexity O(N2) to obtain an optimal solution and derive two closed-form approximate solutions both with computational complexity O(N). For the resultant maximization of the completion probability, we develop an iterative algorithm of...