# Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 18 Mar 2022.

## Builds on (most cited first, 21 of 21)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [EMNIST: an extension of MNIST to handwritten letters](https://mlsanity.com/paper/1702.05373/) (2017)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [GIANT: Globally Improved Approximate Newton Method for Distributed Optimization](https://mlsanity.com/paper/1709.03528/) (2017)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [Randomized Sketches of Convex Programs with Sharp Guarantees](https://mlsanity.com/paper/1404.7203/) (2014)
- [Differentially Private Distributed Optimization](https://mlsanity.com/paper/1401.2596/) (2014)
- [Occupy the Cloud: Distributed Computing for the 99%](https://mlsanity.com/paper/1702.04024/) (2017)
- [Ridge Regression: Structure, Cross-Validation, and Sketching](https://mlsanity.com/paper/1910.02373/) (2019)
- [Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging](https://mlsanity.com/paper/1702.04837/) (2017)
- [Privacy-Utility Trade-off of Linear Regression under Random Projections and Additive Noise](https://mlsanity.com/paper/1902.04688/) (2019)
- [Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization](https://mlsanity.com/paper/2007.01327/) (2020)
- [Lecture Notes on Randomized Linear Algebra](https://mlsanity.com/paper/1608.04481/) (2016)
- [Private Approximations of the 2nd-Moment Matrix Using Existing Techniques in Linear Regression](https://mlsanity.com/paper/1507.00056/) (2015)
- [Faster Least Squares Optimization](https://mlsanity.com/paper/1911.02675/) (2019)
- [Statistical properties of sketching algorithms](https://mlsanity.com/paper/1706.03665/) (2017)
- [Distributed Newton Methods for Deep Neural Networks](https://mlsanity.com/paper/1802.00130/) (2018)
- [Lower Bounds and a Near-Optimal Shrinkage Estimator for Least Squares using Random Projections](https://mlsanity.com/paper/2006.08160/) (2020)
- [Utility-based Resource Allocation and Pricing for Serverless Computing](https://mlsanity.com/paper/2008.07793/) (2020)

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

- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches](https://mlsanity.com/paper/2505.24603/) (2025)
- [Concentration Inequalities for Exchangeable Tensors and Matrix-valued Data](https://mlsanity.com/paper/2601.20152/) (2026)
- [Iterative Sketching for Secure Coded Regression](https://mlsanity.com/paper/2308.04185/) (2023)
- [Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions](https://mlsanity.com/paper/2605.24955/) (2026)
- [Distributed Sketching on Data Partitions for OLS Regression](https://mlsanity.com/paper/2607.07888/) (2026)

## Abstract (arXiv)

We consider distributed optimization methods for problems where forming the Hessian is computationally challenging and communication is a significant bottleneck. We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems. We derive novel approximation guarantees for classical sketching methods and establish tight concentration results that serve as both upper and lower bounds on the error. We then extend our analysis to the accuracy of parameter averaging for distributed sketches. Furthermore, we develop unbiased parameter averaging methods for randomized second order optimization for regularized problems that employ sketching of the Hessian. Existing works do not take the bias of the estimators into consideration, which limits their application to massively parallel computation. We provide closed-form formulas for regularization parameters and step sizes that provably minimize the bias for sketched Newton directions. Additionally, we demonstrate the implications of our theoretical findings via large scale experiments on a serverless cloud computing platform.