# ℓp-Regression in the Arbitrary Partition Model of Communication

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 11 Jul 2023.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Optimal Principal Component Analysis in Distributed and Streaming Models](https://mlsanity.com/paper/1504.06729/) (2015)
- [Toward a unified theory of sparse dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1311.2542/) (2013)
- [Dimensionality Reduction for Tukey Regression](https://mlsanity.com/paper/1905.05376/) (2019)
- [The Communication Complexity of Optimization](https://mlsanity.com/paper/1906.05832/) (2019)
- [Online Active Regression](https://mlsanity.com/paper/2207.05945/) (2022)
- [Principal Component Analysis and Higher Correlations for Distributed Data](https://mlsanity.com/paper/1304.3162/) (2013)
- [Exponentially Improved Dimensionality Reduction for ℓ1: Subspace Embeddings and Independence Testing](https://mlsanity.com/paper/2104.12946/) (2021)
- [Tight Bounds for ℓp Oblivious Subspace Embeddings](https://mlsanity.com/paper/1801.04414/) (2018)
- [Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions](https://mlsanity.com/paper/2207.07417/) (2022)
- [Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching](https://mlsanity.com/paper/1504.01076/) (2015)
- [The ℓp-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines](https://mlsanity.com/paper/2211.07132/) (2022)

## Abstract (arXiv)

We consider the randomized communication complexity of the distributed ℓp-regression problem in the coordinator model, for p∈ (0,2]. In this problem, there is a coordinator and s servers. The i-th server receives Ai∈-M, -M+1, ldots, Mn× d and bi∈-M, -M+1, ldots, Mn and the coordinator would like to find a (1+ε)-approximate solution to minx∈ℝn |(sumi Ai)x - (sumi bi)|p. Here M ≤ poly(nd) for convenience. This model, where the data is additively shared across servers, is commonly referred to as the arbitrary partition model. We obtain significantly improved bounds for this problem. For p = 2, i.e., least squares regression, we give the first optimal bound of tildeTheta(sd2 + sd/ε) bits. For p ∈ (1,2),we obtain an tildeO(sd2/ε + sd/poly(ε)) upper bound. Notably, for d sufficiently large, our leading order term only depends linearly on 1/ε rather than quadratically. We also show communication lower bounds of Omega(sd2 + sd/ε2) for p∈ (0,1] and Omega(sd2 + sd/ε) for p∈ (1,2]. Our bounds considerably improve previous bounds due to (Woodruff et al. COLT, 2013) and (Vempala et al., SODA, 2020).