# Distributed Least Squares in Small Space via Sketching and Bias Reduction

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 8 May 2024.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [GIANT: Globally Improved Approximate Newton Method for Distributed Optimization](https://mlsanity.com/paper/1709.03528/) (2017)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023)
- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares](https://mlsanity.com/paper/1406.5986/) (2014)
- [Sparse sketches with small inversion bias](https://mlsanity.com/paper/2011.10695/) (2020)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Sampling from a k-DPP without looking at all items](https://mlsanity.com/paper/2006.16947/) (2020)
- [Distributed estimation of the inverse Hessian by determinantal averaging](https://mlsanity.com/paper/1905.11546/) (2019)
- [Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging](https://mlsanity.com/paper/1702.04837/) (2017)
- [Unbiased estimates for linear regression via volume sampling](https://mlsanity.com/paper/1705.06908/) (2017)
- [Precise expressions for random projections: Low-rank approximation and randomized Newton](https://mlsanity.com/paper/2006.10653/) (2020)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Asymptotic Analysis of Sampling Estimators for Randomized Numerical Linear Algebra Algorithms](https://mlsanity.com/paper/2002.10526/) (2020)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [Asymptotics of the Sketched Pseudoinverse](https://mlsanity.com/paper/2211.03751/) (2022)
- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [Input-Sparsity Low Rank Approximation in Schatten Norm](https://mlsanity.com/paper/2004.12646/) (2020)
- [A Bootstrap Method for Error Estimation in Randomized Matrix Multiplication](https://mlsanity.com/paper/1708.01945/) (2017)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)

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

- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Algorithmic Guarantees for Distilling Supervised and Offline RL Datasets](https://mlsanity.com/paper/2512.00536/) (2025)
- [Distributed Sketching on Data Partitions for OLS Regression](https://mlsanity.com/paper/2607.07888/) (2026)

## Abstract (arXiv)

Matrix sketching is a powerful tool for reducing the size of large data matrices. Yet there are fundamental limitations to this size reduction when we want to recover an accurate estimator for a task such as least square regression. We show that these limitations can be circumvented in the distributed setting by designing sketching methods that minimize the bias of the estimator, rather than its error. In particular, we give a sparse sketching method running in optimal space and current matrix multiplication time, which recovers a nearly-unbiased least squares estimator using two passes over the data. This leads to new communication-efficient distributed averaging algorithms for least squares and related tasks, which directly improve on several prior approaches. Our key novelty is a new bias analysis for sketched least squares, giving a sharp characterization of its dependence on the sketch sparsity. The techniques include new higher-moment restricted Bai-Silverstein inequalities, which are of independent interest to the non-asymptotic analysis of deterministic equivalents for random matrices that arise from sketching.