# Iterative Sketching for Secure Coded Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 38 of its 95 references that are in the map.
- First posted on arXiv 8 Aug 2023.

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

- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [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)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [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)
- [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)
- [CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning](https://mlsanity.com/paper/1902.00641/) (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)
- [Approximate Gradient Coding with Optimal Decoding](https://mlsanity.com/paper/2006.09638/) (2020)
- [Privacy-Utility Trade-off of Linear Regression under Random Projections and Additive Noise](https://mlsanity.com/paper/1902.04688/) (2019)
- [Coded Computation over Heterogeneous Clusters](https://mlsanity.com/paper/1701.05973/) (2017)
- [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)
- [Lecture Notes on Randomized Linear Algebra](https://mlsanity.com/paper/1608.04481/) (2016)
- [LSAR: Efficient Leverage Score Sampling Algorithm for the Analysis of Big Time Series Data](https://mlsanity.com/paper/1911.12321/) (2019)
- [Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning](https://mlsanity.com/paper/1803.05397/) (2018)
- [OverSketched Newton: Fast Convex Optimization for Serverless Systems](https://mlsanity.com/paper/1903.08857/) (2019)
- [A Practical Guide to Randomized Matrix Computations with MATLAB Implementations](https://mlsanity.com/paper/1505.07570/) (2015)
- [Coded Distributed Computing with Partial Recovery](https://mlsanity.com/paper/2007.02191/) (2020)
- [Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds](https://mlsanity.com/paper/2203.09755/) (2022)
- [Gradient Coding Based on Block Designs for Mitigating Adversarial Stragglers](https://mlsanity.com/paper/1904.13373/) (2019)
- [Numerically Stable Binary Gradient Coding](https://mlsanity.com/paper/2001.11449/) (2020)
- [Age-Based Coded Computation for Bias Reduction in Distributed Learning](https://mlsanity.com/paper/2006.01816/) (2020)

## Abstract (arXiv)

Linear regression is a fundamental and primitive problem in supervised machine learning, with applications ranging from epidemiology to finance. In this work, we propose methods for speeding up distributed linear regression. We do so by leveraging randomized techniques, while also ensuring security and straggler resiliency in asynchronous distributed computing systems. Specifically, we randomly rotate the basis of the system of equations and then subsample blocks, to simultaneously secure the information and reduce the dimension of the regression problem. In our setup, the basis rotation corresponds to an encoded encryption in an approximate gradient coding scheme, and the subsampling corresponds to the responses of the non-straggling servers in the centralized coded computing framework. This results in a distributive iterative stochastic approach for matrix compression and steepest descent.