# Gradient Coding with Iterative Block Leverage Score Sampling

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 119 references that are in the map.
- First posted on arXiv 6 Aug 2023.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [DRACO: Byzantine-resilient Distributed Training via Redundant Gradients](https://mlsanity.com/paper/1803.09877/) (2018)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [A Statistical Perspective on Algorithmic Leveraging](https://mlsanity.com/paper/1306.5362/) (2013)
- [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [An Information-Theoretic Justification for Model Pruning](https://mlsanity.com/paper/2102.08329/) (2021)
- [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)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [CodedSketch: A Coding Scheme for Distributed Computation of Approximated Matrix Multiplication](https://mlsanity.com/paper/1812.10460/) (2018)
- [Toward a unified theory of sparse dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1311.2542/) (2013)
- [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)
- [Approximate Gradient Coding with Optimal Decoding](https://mlsanity.com/paper/2006.09638/) (2020)
- [Provable Deterministic Leverage Score Sampling](https://mlsanity.com/paper/1404.1530/) (2014)
- [Approximate Gradient Coding via Sparse Random Graphs](https://mlsanity.com/paper/1711.06771/) (2017)
- [Lecture Notes on Randomized Linear Algebra](https://mlsanity.com/paper/1608.04481/) (2016)
- [Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions](https://mlsanity.com/paper/2104.01101/) (2021)
- [OverSketch: Approximate Matrix Multiplication for the Cloud](https://mlsanity.com/paper/1811.02653/) (2018)
- [Solving Sparse Linear Systems Faster than Matrix Multiplication](https://mlsanity.com/paper/2007.10254/) (2020)
- [LSAR: Efficient Leverage Score Sampling Algorithm for the Analysis of Big Time Series Data](https://mlsanity.com/paper/1911.12321/) (2019)
- [Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning](https://mlsanity.com/paper/2103.01206/) (2021)
- [OverSketched Newton: Fast Convex Optimization for Serverless Systems](https://mlsanity.com/paper/1903.08857/) (2019)

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

- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Iterative Sketching for Secure Coded Regression](https://mlsanity.com/paper/2308.04185/) (2023)

## Abstract (arXiv)

We generalize the leverage score sampling sketch for ℓ2-subspace embeddings, to accommodate sampling subsets of the transformed data, so that the sketching approach is appropriate for distributed settings. This is then used to derive an approximate coded computing approach for first-order methods; known as gradient coding, to accelerate linear regression in the presence of failures in distributed computational networks, textiti.e. stragglers. We replicate the data across the distributed network, to attain the approximation guarantees through the induced sampling distribution. The significance and main contribution of this work, is that it unifies randomized numerical linear algebra with approximate coded computing, while attaining an induced ℓ2-subspace embedding through uniform sampling. The transition to uniform sampling is done without applying a random projection, as in the case of the subsampled randomized Hadamard transform. Furthermore, by incorporating this technique to coded computing, our scheme is an iterative sketching approach to approximately solving linear regression. We also propose weighting when sketching takes place through sampling with replacement, for further compression.